算法学习之栈与队列
算法学习之栈与队列
一、栈 Stack
0x1 数组的子集
- 栈也是一种线性结构
- 相比数组，栈对应的操作是数组的子集
- 只能从一端添加元素，也只能从一端取出元素
- 这一端称为栈顶
- 栈是一种后进先出的数据结构
- Last In First Out (LIFO)
- 在计算机的世界里，栈拥有着不可思议的作用
0x2 栈的应用
- 无处不在的Undo操作(撤销)
- 程序调用的系统栈
- 括号匹配 - 编译器
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 Code: import java.util.Stack; class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); 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; char topChar = stack.pop(); if(c == ')' && topChar != '(') return false; if(c == ']' && topChar != '[') return false; if(c == '}' && topChar != '{') return false; } } return stack.isEmpty(); } //测试类： public static void main(String[] args) { System.out.println((new Solution()).isValid("()[]{}")); System.out.println((new Solution()).isValid("([)]")); } } |
0x3 栈的实现
|
1 2 3 4 5 6 7 |
Stack<E> void push(E) //入栈 E pop() //出栈 E peek() //查看 int getSize() //长度 boolean isEmpty() //是否为空 |
二、队列 Queue
0x1 站队
0x2 队列的实现
|
1 2 3 4 5 6 7 |
Interface Queue<E> void enqueue(E) //入队 E dequeue() //出队 E getFront() //查看队首 int getSize() //长度 boolean isEmpty() //是否为空 |
0x3 数组队列
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
public class ArrayQueue<E> implements Queue<E> { private Array<E> array; public ArrayQueue(int capacity){ array = new Array<>(capacity); } public ArrayQueue(){ array = new Array<>(); } @Override public int getSize(){ return array.getSize(); } @Override public boolean isEmpty(){ return array.isEmpty(); } public int getCapacity(){ return array.getCapacity(); } @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); } } } } |
0x4 循环队列
数组队列的实现出队的操作的复杂度是O(n），为了使得效率更高，这里编写循环队列。底层的实现仍然是数组，此时复杂度是O(1)。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
public class LoopQueue<E> implements Queue<E> { private E[] data; private int front, tail; private int size; // 有兴趣的同学，在完成这一章后，可以思考一下： // LoopQueue中不声明size，如何完成所有的逻辑？ // 这个问题可能会比大家想象的要难一点点：） public LoopQueue(int capacity){ data = (E[])new Object[capacity + 1]; front = 0; tail = 0; size = 0; } public LoopQueue(){ this(10); } public int getCapacity(){ return data.length - 1; } @Override public boolean isEmpty(){ return front == tail; } @Override public int getSize(){ return size; } @Override public void enqueue(E e){ if((tail + 1) % data.length == front) resize(getCapacity() * 2); data[tail] = e; tail = (tail + 1) % data.length; size ++; } @Override public E dequeue(){ if(isEmpty()) throw new IllegalArgumentException("Cannot dequeue from an empty queue."); E ret = data[front]; data[front] = null; front = (front + 1) % data.length; size --; if(size == getCapacity() / 4 && getCapacity() / 2 != 0) resize(getCapacity() / 2); return ret; } @Override public E getFront(){ if(isEmpty()) throw new IllegalArgumentException("Queue is empty."); return data[front]; } private void resize(int newCapacity){ E[] newData = (E[])new Object[newCapacity + 1]; for(int i = 0 ; i < size ; i ++) newData[i] = data[(i + front) % data.length]; data = newData; front = 0; tail = size; } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append(String.format("Queue: 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); } } } } |