玩转数据结构2-栈和队列

1. 栈 Stack

1.1 栈的特点
  • 栈是一种线性结构
  • 只能从一端添加元素，也只能从同一端（栈顶）取出元素
  • 后进先出(Last In First Out，LIFO)
1.2 栈的应用

  • 无处不在的撤销操作(Undo)

  • 程序调用的系统栈

  • 括号匹配("{}[]()[()]")

      import java.util.Stack;

  class Solution {
  	public boolean isValid(String s) {
  		Stack<Character>  stack = new Stack<>();
  		if(s == null) 
  			return false;
  		for(int i = 0;i<s.length();i++) {
  			char c = s.charAt(i);
  			if(c == '(' || c == '[' || c=='{') {
  				stack.push(c);
  			}
  			else {
  				if(stack.isEmpty()) {
  					return false;
  				}
  				if(c == ')' && stack.pop() != '(') 
  					return false;
  				if(c == ']' && stack.pop() != '[')
  					return false;
  				if(c=='}' && stack.pop() != '{')
  					return false;
  			}
  		}
  		
  		return stack.isEmpty();
  	}
  	
  	public static void main(String[] args) {
  		System.out.println(new Solution().isValid("[]{}()"));
  		System.out.println(new Solution().isValid("[()]{}()"));
  	}
  }
1.3 栈的实现

  • 栈应该具有的功能：
    1）入栈, void push(E,e)
    2）出栈, E pop()
    3）返回栈顶元素, E peek()
    4）判断栈是否为空, boolean isEmpty()
    5）返回栈中元素个数, int getSize()

  • 定义支持泛型的栈接口

      public interface Stack<E> {
  	
  	int getSize();
  	boolean isEmpty();
  	
  	E peek();
  	E pop();
  	void push(E e);

  • 定义动态数组以存储栈内元素：

      public class DynamicArray<E> {
  	private E[] data;
  	private int size;
  	
  	// 构造函数，传入数组的容量
  	public DynamicArray(int capacity) {
  		data = (E[])new Object[capacity];
  		size = 0;
  	}
  	
  	// 空构造，默认数组容量capacity=10
  	public DynamicArray() {
  		this(10);
  	}
  	
  	// 获取数组的容量
  	public int getCapacity(){
  		return data.length;
  	}
  	
  	// 获取数组中元素个数
  	public int getSize(){
  		return size;
  	}
  	
  	// 返回数组是否为空
  	public boolean isEmpty() {
  		return size == 0;
  	}
  	
  	// 向所有元素后添加一个新元素
  	public void addLast(E e) {
  //		if(size == data.length) {
  //			throw new IllegalArgumentException("AddLast failed. Array is full.");
  //		}
  //		
  //		data[size] = e;
  //		size++;
  		
  		add(size,e);
  	}
  	
  	// 向所有元素前添加一个新元素
  	public void addFirst(E e) {
  		add(0,e);
  	}
  	
  	// 向指定位置插入一个新元素e
  	public void add(int index,E e) {
  		
  		if(index<0 || index > size) {
  			throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");			
  		}
  		
  		// 如果存储数据长度已超过数组容量，则扩容
  		if(size == data.length) 
  			resize(2*data.length);
  			
  		for(int i = size - 1;i>=index;i--) {
  			data[i+1] = data[i];
  		}
  		
  		data[index] = e;
  		size ++;
  	}
  	
  	private void resize(int newCapacity) {
  		E newData[] = (E[])new Object[newCapacity];
  		for(int i = 0;i<size;i++) {
  			newData[i] = data[i];
  		}
  		data = newData;
  	}

  	// 获取index索引位置的元素
  	public E get(int index) {
  		if(index <0 || index >=size) {
  			throw new IllegalArgumentException("Get failed. Index is illegal.");
  		}
  		return data[index];
  	}
  	
  	// 修改index索引位置的元素为e
  	public void set(int index,E e) {
  		if(index <0 || index >=size) {
  			throw new IllegalArgumentException("Set failed. Index is illegal.");
  		}
  		data[index] = e;
  	}
  	
  	// 查找数组中是否包含元素e
  	public boolean contains(E e) {
  		for(int i = 0;i<size;i++) {
  			if (data[i].equals(e))
  				return true;
  		}
  		return false;
  	}
  	
  	// 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
  	public int find(E e) {
  		for(int i = 0;i<size;i++) {
  			if (data[i].equals(e))
  				return i;
  		}
  		return -1;		
  	}
  	
  	// 从数组中删除index索引位置的元素，返回删除的元素
  	public E remove(int index) {
  		if(index<0 || index > size) {
  			throw new IllegalArgumentException("Remove failed. Index is illegal.");
  		}
  		E ret = data[index];
  		for(int i = index + 1;i<size;i++) {
  			data [i - 1] = data[i]; 
  		}
  		size--;
  		data[size] = null;
  		// 如果存储数据的个数已小于容量的一半，则缩减容量
  		// 惰性，如果存储数据的个数已小于容量的1/4，则缩减一半容量
  		if(size==data.length/4) {
  			resize(data.length/2);
  		}
  		return ret;
  	}
  	
  	// 从数组中删除第一个元素，返回删除的元素
  	public E removeFirst() {
  		return remove(0);
  	}
  	
  	// 从数组中删除最后元素，返回删除的元素
  	public E removeLast() {
  		return remove(size-1);
  	}
  	
  	// 从数组删除元素e
  	public void removeElement(E e) {
  		int index = find(e);
  		if(index != -1)
  			remove(index);
  	}
  	
  	@Override
  	public String toString() {
  		StringBuilder res = new StringBuilder();
  		res.append(String.format("Array: size = %d, capacity = %d 
", size,data.length));
  		res.append('[');
  		for(int i = 0;i<size;i++) {
  			res.append(data[i]);
  			if(i!=size -1)
  				res.append(",");
  		}
  		res.append(']');
  		return res.toString();
  	}

  	public E getLast() {
  		return get(size-1);
  	}
  	public E getFirst() {
  		return get(0);
  	}
  	
  }

  • 基于动态数组，实现数组栈

      public class ArrayStack<E> implements Stack<E> {
  	DynamicArray<E> Array;
  	
  	public ArrayStack(int capacity) {
  		Array = new DynamicArray<>(capacity);
  	}
  	
  	public ArrayStack() {
  		Array = new DynamicArray<>();
  	}
  	
  	
  	@Override
  	public int getSize() {
  		return Array.getSize();
  	}
  	
  	@Override
  	public boolean isEmpty() {
  		return Array.isEmpty();
  	}
  	
  	@Override
  	public void push(E e) {
  		Array.addLast(e);		
  	}
  	
  	@Override
  	public E peek() {
  		return Array.getLast();
  	}
  	
  	@Override
  	public E pop() {
  		return Array.removeLast();
  	}
  	
  	@Override
  	public String toString() {
  		StringBuilder res = new StringBuilder();
  		res.append("Stack: ");
  		res.append("[");
  		for(int i = 0;i<Array.getSize();i++) {
  			res.append(Array.get(i));
  			if(i != Array.getSize() - 1)
  				res.append(",");
  		}
  		res.append("] top");
  		return res.toString();
  	}

  }

  • 测试

      public class Main {

  	public static void main(String[] args) {
  		ArrayStack<Integer> stack = new ArrayStack<>(); 
  		for(int i = 0;i<5;i++) {
  			stack.push(i);
  			System.out.println(stack);
  			// Stack: [0] top
  			// Stack: [0,1] top
  			// Stack: [0,1,2] top
  			// Stack: [0,1,2,3] top
  			// Stack: [0,1,2,3,4] top
  		}
  		stack.pop();
  		System.out.println(stack);
  		// Stack: [0,1,2,3] top
  	}
  }
1.4 栈的复杂度分析
  • void push(E) // O(1)，均摊复杂度（可能触发resize操作）
  • E pop() // O(1)，均摊复杂度（可能触发resize操作）
  • E peek() // O(1)，返回栈顶元素即可
  • int getSize() // O(1)
  • boolean isEmpty() // O(1)

2. 队列 Queue

2.1 队列特点
  • 一种先进先出的数据结构
  • 只能从一端(队尾)添加元素，从另一端（队首）取出元素
  • First In First Out (FIFO)
  • 在实际生活中应用广泛（排队）
2.2 数组队列的实现

  • 基本功能

    1） 入队，void enqueue(E e)
    2） 出队，E dequeue()
    3） 取出队首元素，E getFront()
    4） 返回队列大小，int getSize()
    5） 判断队列是否为空，boolean isEmpty()

  • 定义支持泛型的队列接口

      public interface Queue<E> {
  	int getSize();
  	boolean isEmpty();
  	void enqueue(E e);
  	E getFront();
  	E dequeue();
  }

  • 利用定义的动态数组实现数组队列

      public class ArrayQueue<E> implements Queue<E> {
  	
  	private DynamicArray<E> array; 
  	public ArrayQueue(int capacity) {
  		array = new DynamicArray<>(capacity);
  	}
  	public ArrayQueue() {
  		array = new DynamicArray<>();
  	}
  	
  	@Override
  	public int getSize() {
  		return array.getSize();
  	}
  	
  	@Override
  	public boolean isEmpty() {
  		return array.isEmpty();
  	}
  	
  	@Override
  	public void enqueue(E e) {
  		array.addLast(e);
  	}
  	
  	@Override
  	public E dequeue(){
  		return array.removeFirst();
  	}
  	
  	@Override
  	public E getFront() {
  		return array.getFirst();
  	}

  	@Override
  	public String toString() {
  		StringBuilder res = new StringBuilder();
  		res.append("Queue: ");
  		res.append("front "+"[");
  		for(int i = 0;i<array.getSize();i++) {
  			res.append(array.get(i));
  			if(i != array.getSize() - 1)
  				res.append(",");
  		}
  		res.append("] tail");
  		return res.toString();
  	}
  	
  	public static void main(String[] args) {
  		ArrayQueue<Integer> queue = new ArrayQueue<>();
  		for(int i = 0;i<10;i++) {
  			queue.enqueue(i);
  			System.out.println(queue);
  			if(i%3==2) {
  				queue.dequeue();
  				System.out.println(queue);
  			}
  		}
  	}
  }
2.3 数组队列复杂度分析
  • void enqueue(E) // O(1)，均摊复杂度（可能触发resize操作）
  • E dequeue() // O(n)
  • E getFront() // O(1)，返回队首元素即可
  • int getSize() // O(1)
  • boolean isEmpty() // O(1)
2.4 循环队列

数组队列在出队时，总是需要遍历队列，将队列所有元素向前移一位，复杂度比较高，因此一个解决办法就是循环队列：

  • 关键点1: 定义front,tail记录队首及队尾所在位置,入队时 tail = (tail+1)%length,出队时front = (front+1) % length
  • 关键点2: 当front == tail时表示队列为空
  • 关键点3: 当front == (tail+1) % length时表示队列已满，需要扩容

实现过程：

  • 泛型接口

      public interface Queue<E> {
  	int getSize();
  	boolean isEmpty();
  	void enqueue(E e);
  	E getFront();
  	E dequeue();
  }

  • 定义包含静态数组成员变量、实现泛型接口的动态循环队列

      public class LoopQueue<E> implements Queue<E> {
  	private E[] data;
  	private int size;
  	private int front,tail;
  	
  	public LoopQueue(int capacity) {
  		data = (E[])new Object[capacity + 1];//循环队列要预留一个空间
  		front = 0;
  		tail = 0;
  		size = 0;
   	}
  	// 缺省构造
  	public LoopQueue() {
  		this(10);
  	}
  	
  	@Override
  	public boolean isEmpty() {
  		return front == tail;
  	}
  	
  	@Override
  	public int getSize() {
  		return size;
  	}
  	
  	public int getCapacity() {
  		return data.length - 1;
  	}
  	
  	@Override
  	public void enqueue(E e) {
  		// 如果队列已满，扩容
  		if(front == (tail + 1)%data.length) {
  			resize(getCapacity()*2);
  		}
  		// 将元素添加到队尾
  		data[tail] = e;
  		// tail 向后移一位，循环移位
  		tail = (tail + 1) % data.length;
  		size++;
  		
  	}
  	private void resize(int newCapacity) {
  		E[] newData = (E[])new Object[newCapacity + 1];
  		for(int i =0 ; i<size;i++) {
  			// 新队列的首位存储旧队列的front
  			newData[i] = data[(i+front)%data.length];
  		}
  		data = newData;
  		front = 0;
  		tail = size;
  	}
  	
  	@Override
  	public E dequeue() {
  		if(isEmpty()) {
  			throw new IllegalArgumentException("Dequeue failed. Queue is empty.");
  		}
  		// 取出队首元素，并将队首置空
  		E res = data[front];
  		data[front] = null;
  		// front 向后移一位，循环
  		front = (front + 1)%data.length;
  		size--;
  		
  		// 当队列元素等于容量的1/4时，缩小一半队列容量
  		if(size == getCapacity() / 4 && getCapacity() / 2 != 0){
  			resize(getCapacity() / 2);
  		}
  		return res;
  	}
  	
  	@Override
  	public E getFront() {
  		if(isEmpty()) {
  			throw new IllegalArgumentException("Queue is empty.");
  		}
  		return data[front];
  	}
  	
  	@Override
  	public String toString() {
  		StringBuilder res = new StringBuilder();
  		res.append(String.format("LoopQueue: size = %d , capacity = %d
", size, getCapacity()));
  		res.append("front "+"[");
  		// 从队首开始循环，直到队尾结束
  		for(int i = front; i != tail ;i = (i+1)%data.length) {
  			res.append(data[i]);
  			// 未达到队尾时，添加间隔符
  			if((i+1)%data.length != tail)
  				res.append(",");
  		}
  		res.append("] tail");
  		return res.toString();
  	}
  }

  • 测试

      public static void main(String[] args) {
  	LoopQueue<Integer> queue = new LoopQueue<>();
  	for(int i = 0;i<10;i++) {
  		queue.enqueue(i);
  		System.out.println(queue);
  		if(i%3==2) {
  			queue.dequeue();
  			System.out.println(queue);
  		}
  	}
  	/*
  		LoopQueue: size = 1 , capacity = 10
  		front [0] tail
  		LoopQueue: size = 2 , capacity = 10
  		front [0,1] tail
  		LoopQueue: size = 3 , capacity = 10
  		front [0,1,2] tail
  		LoopQueue: size = 2 , capacity = 5
  		front [1,2] tail
  		LoopQueue: size = 3 , capacity = 5
  		front [1,2,3] tail
  		LoopQueue: size = 4 , capacity = 5
  		front [1,2,3,4] tail
  		LoopQueue: size = 5 , capacity = 5
  		front [1,2,3,4,5] tail
  		LoopQueue: size = 4 , capacity = 5
  		front [2,3,4,5] tail
  	*/
  }
2.5 循环队列时间复杂度分析
  • void enqueue(E) // O(1)，均摊复杂度（可能触发resize操作）
  • E dequeue() // O(1)，均摊复杂度（可能触发resize操作）
  • E getFront() // O(1)，返回队首元素即可
  • int getSize() // O(1)
  • boolean isEmpty() // O(1)

3. 数组队列与循环队列对比

import java.util.Random;

public class Main {
	public static double costTime(Queue<Integer> queue,int nCount) {
		
		Random random = new Random();
		long startTime = System.nanoTime();
		for(int i = 0;i<nCount;i++) {
			queue.enqueue(random.nextInt(Integer.MAX_VALUE));
		}
		for(int i = 0;i<nCount;i++) {
			queue.dequeue();
		}
		
		long endTime = System.nanoTime();
		return (endTime-startTime) / 1000000000.0 ;
		
	}

	public static void main(String[] args) {
		int nCount = 100000;
		ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
		LoopQueue<Integer> loopQueue = new LoopQueue<>();
		System.out.println("ArrayQueue:"+costTime(arrayQueue,nCount)); //ArrayQueue:5.000418012
		System.out.println("LoopQueue:"+costTime(loopQueue,nCount)); // LoopQueue:0.022053394
	}
}

4. 总结

这节课主要学习了最常见的两种数据结构，栈和队列。栈是后进先出的一种线性结构，实际应用包括：撤销操作、函数调用、括号匹配等，借助动态数组很容易实现栈的相关功能；队列是先进先出的一种线性结构，基于动态数组可以实现队列的相关功能，但数组队列的出队复杂度比较高，为此，借助循环的概念，可以实现一种更加高效的循环队列结构，最后的测试也证实了循环队列的高效性。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/SweetZxl/p/11390674.html