栈和队列
栈（Stack）
-
特点：
栈也是一种
线性结构相比数组，栈对应的操作是数组的子集
只能从一端添加元素，也只是从一端取出元素
这一端称为栈顶
栈是一种后进先出的数据结构
-
Last In First Out(LIFO)
栈.gif
-
栈的应用
- 无处不在的Undo操作（撤销）
ctrl + Z-编辑器 - 程序调用的系统栈（
递归） -操作系统
- 无处不在的Undo操作（撤销）
递归.gif
-
栈的实现
public class ArrayStack<E> implements Stack<E> { Array<E> array; public ArrayStack(int capacity){ array = new Array<>(capacity); } public ArrayStack(){ array = new Array<>(); } @Override public int getSize() { return array.getSize(); } @Override public boolean isEmpty() { return array.isEmpty(); } public int getCapcity(){ return array.getCapacity(); } //入栈 @Override public void push(E e) { array.addLast(e); } //弹栈 @Override public E pop() { return array.removeLast(); } //看栈顶元素 @Override public E peek() { return array.getLast(); } @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(); } } -
栈的另一个应用：括号匹配 -编译器
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。示例 1:
输入: "()"
输出: true
示例 2:输入: "()[]{}"
输出: true
示例 3:输入: "(]"
输出: false
示例 4:输入: "([)]"
输出: false来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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.add(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();
}
括号匹配.gif
- LeetCode的更多说明
- 在LeetCode里无需
main方法，它自己创建测试用例。 - 实现方法不能是
private,而是public。 - 可以使用
内部类。
- 在LeetCode里无需
队列(Queue)
-
特点：
队列也是一种线性结构。
相比数组，队列对应的操作是数组的子集。
只能从一端（队尾）添加元素，只能从另一端（队首）取出元素。
队列是一种先进先出的数据结构（先到先得）
First In First Out(FIFO)
队列.gif
-
数组队列
public class ArrayQueue<E> implements Queue<E> { private Array<E> array; public ArrayQueue(int capacity){ array=new Array<>(capacity); } public ArrayQueue(){ array = new Array<>(); } public int getCapacity(){ return array.getCapacity(); } @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 getFornt() { 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(); } }- 数组队列的复杂度分析
| ArrayQueue<E> | |
|---|---|
| void enqueue(E) | O(1)均摊 |
| E dequeue() | ==O(n)== [removeFirst] |
| E front() | O(1) |
| int getSize | O(1) |
| boolean isEmpty() | O(1) |
-
数组队列的问题
队列删除问题.gif
-
思考：每一次删除，都需要移动后面所有元素，使得时间复杂度为O（n）
解决：不移动后面元素
方案：循环队列
-
循环队列
front：指向队列第一个元素
tail:指向队列最后一个元素后一个位置
-
队列为空
front==tail1572615047251.png
-
入队和出队的操作
- 入队时直接在队尾添加，tail向后移动一位
- 出队时队首元素删除，front移动到第一个元素位置
循环队列普通的出队入队.gif
- 体现循环队列的`特点`
- tail=(tail+1)%capacity
- 队列中必然有一个位置空着，capacity中，`浪费一个空间`
若把剩余一个的装满，`front = tail`表示队列为空，但此时队列不为空
所以在循环队列中 `(tail + 1) % capacity = front`表示队列满
- 可想象循环队列为时钟，一个轮回又回到12点
循环队列入队的特点.gif
-
循环队列实现
-
其中
size可以用front 和 tail算出if(tail<front){ size=(tail+data.length)-front; }else{ size=tail-front; } -
获取最大存储元素数量(capacity)
public int getCapacity(){ return data.length - 1; } -
扩容操作(要想容纳newCapacity个元素，新的数组空间就需要多一位，抵消浪费的空间)
private void resize(int newCapacity){ //要想容纳newCapacity个元素，新的数组空间就需要多一位，抵消浪费的空间 E[] newData = (E[]) new Object[newCapacity + 1]; //两种循环方式 /*for (int i = 0; i < size; i++) { newData[i] = data[(i+front)%data.length]; }*/ for(int i=front;i !=tail;i=(i+1)%data.length){ newData[i] = data[i]; } data = newData; front = 0; tail = size; }
-
- 入队操作（注意其中的扩容操作参数应该是getCapacity*2）
```java
public void enqueue(E e) {
if((tail + 1) % data.length == front)
//不使用data.length是因为length包含了浪费的那一位，
//用它扩容将产生4个空位置(扩容操作本身会增加一位空间)
resize(getCapacity()*2);
data[tail] = e;
tail =(tail + 1) % data.length;
size ++;
}
```
- 出队操作
```java
public E dequeue() {
if(isEmpty())
throw new IllegalArgumentException("队列为空，无法删除");
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;
}
```
-
循环队列复杂度分析
| LoopQueue<E> | |
|---|---|
| void enqueue(E) | O(1) 均摊 |
| E dequeue() | O(1) 均摊 |
| E getFornt() | O(1) |
| int getSize() | O(1) |
| boolean isEmpty() | O(1) |
- 数组队列和循环队列的差别
- 出队操作循环队列的时间复杂度是O(1)!
此文章是学习《玩转数据结构》的学习笔记总结，如要课程请支持正版
