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