Java 栈(Stack)与队列(Queue)

一.栈(Stack)

1.概念

是一种特殊的线性表，遵循“先进后出”的原则。进栈就是向栈内放入元素，元素放在栈顶；出栈就是删除栈顶元素。

2.栈的方法

实例化栈：

这是int类型的例子

Stack<Integer> s = new Stack<>();

方法：

方法	功能
E push(E e)	将e入栈，并返回e
E pop()	将栈顶元素出栈并返回
E peek()	获取栈顶元素
int size()	获取栈中有效元素个数
boolean empty()	检测栈是否为空

3.栈的模拟实现

栈的模拟实现主要是用数组，定义一个标记，记录数组使用的长度。模拟的就是上面的5个方法。

3.1 push

数组从头开始用，入栈一个就是在数组后面加一个

public int push(int e){array[size++] = e;return e;
}

3.2 pop

直接让size--即可，后面本来有的数据（就是array[size-1]）会被后来入栈的元素覆盖

public int pop(){int e = array[size-1];size--;return e;
}

3.3 peek

思路与pop无异，只是不用size--而已

public int peek(){if(empty()){throw new RuntimeException("栈为空，无法获取栈顶元素");}return array[size-1];
}

3.4 size

public int size(){return size;
}

3.5 empty

public boolean empty(){return 0 == size;
}

4.栈的经典例题

4.1 经典括号对应问题

对应题目LeetCode：20. 有效的括号

这个无需多言，遍历整个字符串，遇到左括号放入栈，遇到右括号与栈顶元素匹配。

class Solution {public boolean isValid(String s) {Stack<Character> stack=new Stack<>();for(int i=0;i<s.length();i++){char ch=s.charAt(i);if(ch=='(' || ch=='[' || ch=='{'|| i==0){stack.push(ch);}else{if(stack.empty()==false){char chp=stack.peek();if(chp=='(' && ch==')'){stack.pop();}else if(chp=='{' && ch=='}'){stack.pop();}else if(chp=='[' && ch==']'){stack.pop();}else{return false;}}else{return false;}}}if(stack.empty()){return true;}else{return false;}}
}

这个可以说是括号问题的元问题，其他的括号问题都是其变种，万变不离其宗，本质上还是栈的问题。

4.2 表达式求值

表达式分为三种：前缀表达式、中缀表达式和后缀表达式（逆波兰式）。

不管怎么变，本质都是栈问题。

我们平常写的数学表达式是中缀表达式，这里着重说明后缀表达式也就是逆波兰式表达式。

这里对应的题目：LeetCode 150. 逆波兰表达式求值

怎么将中缀转成后缀呢？

第一步，先加括号，在中缀表达式的基础上继续加，如图上加的彩色括号

第二步，将一个括号内的运算符移出，图上标记了该运算符是从那个括号里移出的

第三步，把括号全删了就成了后缀表达式

明白了转化的原理，不难发现这就是一个栈问题。

我们可以从头遍历后缀表达式，数字入栈，遇到运算符两个数字出栈运算。这里注意两个数字是有顺序的，后出栈的是运算符前面的数。运算完得到的新数入栈，直到后缀表达式遍历完，返回栈顶元素即可。

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack=new Stack<>();int val1=0;int val2=0;for(String str : tokens) {switch(str) {case "+" :val2 = stack.pop();val1 = stack.pop();stack.push(val1+val2);break;case "-" :val2 = stack.pop();val1 = stack.pop();stack.push(val1-val2);break;case "*" :val2 = stack.pop();val1 = stack.pop();stack.push(val1*val2);break;case "/" :val2 = stack.pop();val1 = stack.pop();stack.push(val1/val2);break;default:stack.push(Integer.parseInt(str));break;}}return stack.pop();}}

5.栈、虚拟机栈、栈帧有什么区别

名称	描述	举例
栈	一种具有后进先出特性的数据结构，用于存储临时数据、函数调用信息、局部变量等	程序执行函数调用时，新函数调用信息压入栈
虚拟机栈	Java 虚拟机中的运行时数据区，用于存储方法调用状态，每个线程有独立的虚拟机栈	多线程 Java 程序中，各线程执行方法时在其虚拟机栈操作
栈帧	虚拟机栈中的存储单元，与正在执行的方法对应，方法调用时创建，执行完弹出	Java 方法调用时创建对应栈帧存储执行数据

二.队列(Queue)

1.概念

一种特殊的线性表，与栈不用的是，队列遵循“先进先出”的原则，队尾入队，队头出队。

注意：在Java中，Queue是个接口，底层是通过链表实现的，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

Queue<Integer> queue = new LinkedList<>();

2.队列的方法

方法	功能
boolean offer(E e)	入队列
E poll()	出队列
peek()	获取队头元素
int size()	获取队列中有效元素个数
boolean isEmpty()	检测队列是否为空

3.队列的模拟实现

队列的模拟实现可以用数组，也可以用双向链表。

这里使用的是双向链表。

3.1 offer

public void offer(int e){ListNode newNode = new ListNode(e);if(first == null){first = newNode;}else{last.next = newNode;newNode.prev = last;}last = newNode;size++;
}

这里的first是队头，last是队尾，下面也都是这样

3.2 poll

public int poll(){
// 1. 队列为空
// 2. 队列中只有一个元素----链表中只有一个节点---直接删除
// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除int value = 0;if(first == null){return null;}else if(first == last){last = null;first = null;}else{value = first.value;first = first.next;first.prev.next = null;first.prev = null;}--size;return value;
}

3.3 peek

public int peek(){if(first == null){return null;}return first.value;
}

3.4 size

public int size() {return size;
}

3.5 isEmpty

public boolean isEmpty(){return first == null;
}

4.循环队列

在用数组模拟队列时，如果只是单纯删一个first++，加一个las--的话会太浪费空间。如果我们让空间变成一个环的话，空间就可以得到循环利用。

那么怎么让一个数组变成一个环呢？

这里的变环不是“物理”的变环，而是通过一个技巧。

假如一个数组的长度是8，如果成环的话，那么下标7的下一个下标就是0了，我们只要（n+1）%arr.length即可（n是当前数组的下标，arr是整个数组）。这种思想在一些算法题中也有使用。

循环队列对应的例题：LeetCode 622. 设计循环队列

上面只是解决了怎么成环的问题，在设计循环队列时有一个很重要的点就是怎么判断队列是否为空、是否为满。这里有三个解决方法：

一是用一个size记录现在用了多少个位置；二是用boolean数组标记（锁上），这个也是做算法题的惯用套路；三是我用的，留下一个位置空着不用。

用第三种判断是不是满了直接看rear（后面）的下一个的下一个是不是front（前面）；判断是不是空直接判断rear是不是等于front。

class MyCircularQueue {public int front;public int rear;public int[] elem;public MyCircularQueue(int k) {elem = new int[k+1];}public boolean enQueue(int value) {if(isFull()){return false;}else{elem[rear]=value;rear=(rear+1)%elem.length;return true;}}public boolean deQueue() {if(isEmpty()){return false;}else{front = (front+1)%elem.length;return true;}}public int Front() {if(isEmpty()){return -1;}else{return elem[front];}}public int Rear() {if(isEmpty()){return -1;}else{int index = (rear == 0) ? elem.length-1 : rear-1;return elem[index];}}public boolean isEmpty() {return front==rear;}public boolean isFull() {return (rear+1)%(elem.length)==front;}
}

三.双端队列((Deque)

双端队列的两端都支持出队入队，可以说是队列的进化版。

同时注意：Deque也是一个接口，使用时必须创建LinkedList的对象。

在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。

Deque<Integer> stack = new ArrayDeque<>();
Deque<Integer> queue = new LinkedList<>();

双端队列的方法：

• addFirst() - 在双端队列的开头添加指定的元素。如果双端队列已满，则引发异常。

• addLast() - 在双端队列的末尾添加指定的元素。如果双端队列已满，则引发异常。

• offerFirst() - 在双端队列的开头添加指定的元素。如果双端队列已满，则返回false。

• offerLast() - 在双端队列的末尾添加指定的元素。如果双端队列已满，则返回false。

• getFirst() - 返回双端队列的第一个元素。如果双端队列为空，则引发异常。

• getLast() - 返回双端队列的最后一个元素。如果双端队列为空，则引发异常。

• peekFirst() - 返回双端队列的第一个元素。如果双端队列为空，则返回null。

• peekLast() - 返回双端队列的最后一个元素。如果双端队列为空，则返回null。

• removeFirst() - 返回并删除双端队列的第一个元素。如果双端队列为空，则引发异常。

• removeLast() - 返回并删除双端队列的最后一个元素。如果双端队列为空，则引发异常。

• pollFirst() - 返回并删除双端队列的第一个元素。如果双端队列为空，则返回null。

• pollLast() - 返回并删除双端队列的最后一个元素。如果双端队列为空，则返回null。