1. 棧 Stack
1.1 棧的特點
- 棧是一種線性結(jié)構(gòu)
- 只能從一端添加元素，也只能從同一端（棧頂）取出元素
- 后進先出(Last In First Out，LIFO)
1.2 棧的應(yīng)用
無處不在的撤銷操作(Undo)
程序調(diào)用的系統(tǒng)棧
-
括號匹配("{}[]()[()]")
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 棧的實現(xiàn)
棧應(yīng)該具有的功能：
1）入棧, void push(E,e)
2）出棧, E pop()
3）返回棧頂元素, E peek()
4）判斷棧是否為空, boolean isEmpty()
5）返回棧中元素個數(shù), int getSize()-
定義支持泛型的棧接口
public interface Stack<E> { int getSize(); boolean isEmpty(); E peek(); E pop(); void push(E e); -
定義動態(tài)數(shù)組以存儲棧內(nèi)元素：
public class DynamicArray<E> { private E[] data; private int size; // 構(gòu)造函數(shù)，傳入數(shù)組的容量 public DynamicArray(int capacity) { data = (E[])new Object[capacity]; size = 0; } // 空構(gòu)造，默認(rèn)數(shù)組容量capacity=10 public DynamicArray() { this(10); } // 獲取數(shù)組的容量 public int getCapacity(){ return data.length; } // 獲取數(shù)組中元素個數(shù) public int getSize(){ return size; } // 返回數(shù)組是否為空 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."); } // 如果存儲數(shù)據(jù)長度已超過數(shù)組容量，則擴容 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; } // 查找數(shù)組中是否包含元素e public boolean contains(E e) { for(int i = 0;i<size;i++) { if (data[i].equals(e)) return true; } return false; } // 查找數(shù)組中元素e所在的索引，如果不存在元素e，則返回-1 public int find(E e) { for(int i = 0;i<size;i++) { if (data[i].equals(e)) return i; } return -1; } // 從數(shù)組中刪除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; // 如果存儲數(shù)據(jù)的個數(shù)已小于容量的一半，則縮減容量 // 惰性，如果存儲數(shù)據(jù)的個數(shù)已小于容量的1/4，則縮減一半容量 if(size==data.length/4) { resize(data.length/2); } return ret; } // 從數(shù)組中刪除第一個元素，返回刪除的元素 public E removeFirst() { return remove(0); } // 從數(shù)組中刪除最后元素，返回刪除的元素 public E removeLast() { return remove(size-1); } // 從數(shù)組刪除元素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); } } -
基于動態(tài)數(shù)組，實現(xiàn)數(shù)組棧
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 棧的復(fù)雜度分析
- void push(E) // O(1)，均攤復(fù)雜度（可能觸發(fā)resize操作）
- E pop() // O(1)，均攤復(fù)雜度（可能觸發(fā)resize操作）
- E peek() // O(1)，返回棧頂元素即可
- int getSize() // O(1)
- boolean isEmpty() // O(1)
2. 隊列 Queue
2.1 隊列特點
- 一種先進先出的數(shù)據(jù)結(jié)構(gòu)
- 只能從一端(隊尾)添加元素，從另一端（隊首）取出元素
- First In First Out (FIFO)
- 在實際生活中應(yīng)用廣泛（排隊）
2.2 數(shù)組隊列的實現(xiàn)
-
基本功能
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(); } -
利用定義的動態(tài)數(shù)組實現(xiàn)數(shù)組隊列
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 數(shù)組隊列復(fù)雜度分析
- void enqueue(E) // O(1)，均攤復(fù)雜度（可能觸發(fā)resize操作）
- E dequeue() // O(n)
- E getFront() // O(1)，返回隊首元素即可
- int getSize() // O(1)
- boolean isEmpty() // O(1)
2.4 循環(huán)隊列
數(shù)組隊列在出隊時，總是需要遍歷隊列，將隊列所有元素向前移一位，復(fù)雜度比較高，因此一個解決辦法就是循環(huán)隊列：
- 關(guān)鍵點1: 定義front,tail記錄隊首及隊尾所在位置,入隊時 tail = (tail+1)%length,出隊時front = (front+1) % length
- 關(guān)鍵點2: 當(dāng)front == tail時表示隊列為空
- 關(guān)鍵點3: 當(dāng)front == (tail+1) % length時表示隊列已滿，需要擴容
實現(xiàn)過程：
-
泛型接口
public interface Queue<E> { int getSize(); boolean isEmpty(); void enqueue(E e); E getFront(); E dequeue(); } -
定義包含靜態(tài)數(shù)組成員變量、實現(xiàn)泛型接口的動態(tài)循環(huán)隊列
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];//循環(huán)隊列要預(yù)留一個空間 front = 0; tail = 0; size = 0; } // 缺省構(gòu)造 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 向后移一位，循環(huán)移位 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 向后移一位，循環(huán) front = (front + 1)%data.length; size--; // 當(dāng)隊列元素等于容量的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 "+"["); // 從隊首開始循環(huán)，直到隊尾結(jié)束 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 循環(huán)隊列時間復(fù)雜度分析
- void enqueue(E) // O(1)，均攤復(fù)雜度（可能觸發(fā)resize操作）
- E dequeue() // O(1)，均攤復(fù)雜度（可能觸發(fā)resize操作）
- E getFront() // O(1)，返回隊首元素即可
- int getSize() // O(1)
- boolean isEmpty() // O(1)
3. 數(shù)組隊列與循環(huán)隊列對比
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. 總結(jié)
這節(jié)課主要學(xué)習(xí)了最常見的兩種數(shù)據(jù)結(jié)構(gòu)，棧和隊列。棧是后進先出的一種線性結(jié)構(gòu)，實際應(yīng)用包括：撤銷操作、函數(shù)調(diào)用、括號匹配等，借助動態(tài)數(shù)組很容易實現(xiàn)棧的相關(guān)功能；隊列是先進先出的一種線性結(jié)構(gòu)，基于動態(tài)數(shù)組可以實現(xiàn)隊列的相關(guān)功能，但數(shù)組隊列的出隊復(fù)雜度比較高，為此，借助循環(huán)的概念，可以實現(xiàn)一種更加高效的循環(huán)隊列結(jié)構(gòu)，最后的測試也證實了循環(huán)隊列的高效性。
