栈Stack和队列Queue
目录
一、栈
（1）用数组实现
（2）用单链表实现
（3）用标注尾结点的单链表实现
（4）用双向链表实现
2、栈的实际应用
（1）改变元素的序列
（2）将递归转化为循环（逆序打印链表）
（3）括号匹配
（4）逆波兰表达式求值
（5）出栈入栈次序匹配
（6）最小栈
二、队列
1、队列的使用
2、队列的模拟实现
3、循环队列
4、双端队列Deque
三、面试题
1、用栈实现队列
2、用队列实现栈
一、栈
栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作
进行数据插入和删除操作的一端称为栈顶，另一端称为栈底
栈中的数据元素遵守后进先出的原则
- 压栈/进栈/入栈：栈的插入操作
- 出栈：栈的删除操作
| 方法 | 功能 |
| Stack() | 构造一个空的栈 |
| E push(E e) | 将e入栈，并返回e |
| E pop() | 将栈顶元素出栈并返回 |
| E peek() | 获取栈顶元素 |
| int size() | 获取栈中有效元素个数 |
| boolean empty() | 检测栈是否为空 |
1、栈的模拟实现
（1）用数组实现
（2）用单链表实现
- 若使用尾插法，则入栈时间复杂度为O(n)，出栈时间复杂度为O(n)
- 若使用头插法，则入栈复杂度为O(1)，出栈复杂度为O(1)
（3）用标注尾结点的单链表实现
- 尾插法：入栈O(1)，出栈O(n)（因为删除尾结点依旧要遍历到前一个结点，改变其next值）
- 头插法：入栈O(1)，出栈O(1)
（4）用双向链表实现
无论尾插还是头插时间复杂度都为O(1)
LinkedList<Integer> stack=new LinkedList<>();stack.push(1);// addFirst(e);stack.push(2);stack.push(3);System.out.println(stack.peek());//拿到头结点32、栈的实际应用
（1）改变元素的序列
（2）将递归转化为循环（逆序打印链表）
//1、递归方式void reverseprintList1(Node head){if(head!=null){printList(head.next);System.out.print(head.val + " ");}}
//2、循环方式void reverseprintList2(Node head){if(head==null){return;}Stack<Node> s = new Stack<>();// 将链表中的结点保存在栈中Node cur = head;while(cur!=null){s.push(cur);cur = cur.next;}// 将栈中的元素出栈while(!s.empty()){System.out.print(s.pop().val + " ");}}（3）括号匹配
给定一个只包含' ( '、' ) '、' { '、' } '、' [ '、' ] '的字符串s，判断括号是否匹配。匹配条件：左括号必须与相同类型的右括号闭合，不可交错排列
匹配示例：(){}[]、({}[])、([{}])、()[{}]
public boolean isValid(String s) {Stack<Character> stack=new Stack<Character>();for (int i = 0; i < s.length(); i++) {char c=s.charAt(i);if (c=='(' || c=='[' || c=='{'){//c为左括号就添加进来等着对称匹配stack.push(c);}else {//c为右括号//此时栈中可能有左括号等着匹配，也可能为空（无法匹配）if (stack.empty()){return false;}//不为空，则栈中存放的是左括号，那就判断c与栈顶元素是否匹配（因为两括号必须要对称匹配）char top=stack.peek();if (c==')' && top=='(' || c==']' && top=='[' || c=='}' && top=='{'){//对称匹配了则弹出此左括号stack.pop();}else {//遇到一个右括号无法与栈顶左括号对称匹配，则无法匹配return false;}}}//如果s遍历完发现栈中不为空，即栈中仍有残存左括号未进行匹配，不匹配if (!stack.empty()){return false;}//否则匹配return true;}（4）逆波兰表达式求值
中缀表达式转化为后缀表达式技巧：
public int evalRPN(String[] tokens) {Stack<Integer> stack=new Stack<>();for (String s : tokens) {if (!isOperation(s)) {//压入数字字符stack.push(Integer.parseInt(s));}else {//运算符则弹出栈顶2个元素进行操作（先弹出的放运算符右边）int num2=stack.pop();int num1=stack.pop();switch (s){case "+":stack.push(num1+num2);break;case "-":stack.push(num1-num2);break;case "*":stack.push(num1*num2);break;case "/":stack.push(num1/num2);break;}}}return stack.pop();}private boolean isOperation(String s) {if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){//是运算符return true;}return false;}（5）出栈入栈次序匹配
public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack=new Stack<>();int j=0;for (int i = 0; i < pushV.length; i++) {stack.push(pushV[i]);while (!stack.empty() && j<popV.length && stack.peek()==popV[j]){stack.pop();j++;}}return stack.empty();}（6）最小栈
class MinStack {private Stack<Integer> stack;private Stack<Integer> minStack;//存储阶段性最小值private int minValue;public MinStack() {stack=new Stack<>();minStack=new Stack<>();}public void push(int val) {stack.push(val);if (minStack.empty()){minStack.push(val);}else {if (val<=minStack.peek()){minStack.push(val);}}}public void pop() {if (!stack.empty()){int ret=stack.pop();if (minStack.peek()==ret){minStack.pop();}}}public int top() {//获取stack栈顶元素if (stack.empty()){return -1;}return stack.peek();}public int getMin() {//获取minStack栈顶元素if (minStack.empty()){return -1;}return minStack.peek();}
}
- 栈：一种数据结构。是一种特殊的线性表，只允许在栈顶进行插入和删除操作，栈顶的数据元素遵守后进先出的原则
- 虚拟机栈：JVM内存管理的一部分，用于管理函数调用的内存和回收。属于线程私有，确保每个线程的内存隔离和安全。
- 栈帧：函数调用过程中的内存管理单元。包含局部变量表、操作栈等信息。每个方法在运行时JVM都会创建一个栈帧，并将其压入虚拟机栈中；当方法调用结束时对应的栈帧会从虚拟机栈中出栈，确保函数调用的顺利进行和结束后的资源释放
二、队列
队列：只允许在一端进行插入和删除数据操作，在另一端进行删除数据操作的特殊线性表
- 进行插入操作的一端称为队尾，进行删除操作的一端称为队头
- 队列遵守先进先出的原则
1、队列的使用
在Java中，Queue是个接口，底层是通过链表实现的
| 方法 | 功能 |
| boolean offer(E e) | 入队列 |
| E poll() | 出队列 |
| peek() | 获取队头元素 |
| int size() | 获取队列中有效元素个数 |
| boolean isEmpty() | 检测队列是否为空 |
Queue是个接口，在实例化时必须实例化LInkedList的对象，因为LinkedList实现了Queue接口
Queue<Integer> q = new LinkedList<>();// 从队尾入队列q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5);System.out.println(q.size());//5System.out.println(q.peek()); // 获取队头元素 1q.poll();//弹出队头元素 1System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回 2if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());//3}2、队列的模拟实现
队列中既然可以存储元素，那底层肯定要有能够保存元素的空间。通过前面线性表的学习了解到常见的空间类型有2种：顺序结构和链式结构。那是用哪种结构实现比较好呢？
（1）双向链表实现
（2）数组实现
如果rear==elem.length-1之后发现数组前面还有位置还可以往前面插入元素就好了，这时候也就是我们的循环队列
3、循环队列
数组设计循环队列
4、双端队列Deque
双端队列是指允许两端都可以进行入队和出队操作的队列
Deque是一个接口，使用时必须创建LinkedList对象
在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口
Deque<Integer>stack =newArrayDeque<>();//双端队列的线性实现
Deque<Integer>queue=newLinkedList<>();//双端队列的链式实现三、面试题
1、用栈实现队列
class MyQueue {Stack<Integer> inStack;Stack<Integer> outStack;public MyQueue() {inStack=new Stack<>();outStack=new Stack<>();}public void push(int x) {inStack.push(x);}public int pop() {if (empty()){return -1;//队列此时为空}if (outStack.empty()){while (!inStack.empty()){outStack.push(inStack.pop());}}return outStack.pop();}public int peek() {if (empty()){return -1;}if (outStack.empty()){while (!inStack.empty()){outStack.push(inStack.pop());}}return outStack.peek();}public boolean empty() {return inStack.empty() && outStack.empty();}
}2、用队列实现栈
class MyStack {private Queue<Integer> qu1;private Queue<Integer> qu2;public MyStack() {qu1=new LinkedList<>();qu2=new LinkedList<>();}//入栈入到不为空的队列，都为空则入到qu1即可public void push(int x) {if (!qu1.isEmpty()){qu1.offer(x);}else if (!qu2.isEmpty()){qu2.offer(x);}else {qu1.offer(x);}}//出栈出不为空的队列size-1个。最后一个元素就是要出栈的元素public int pop() {if (empty()){return -1;//栈为空}if (!qu1.isEmpty()){int size=qu1.size();for (int i = 0; i < size - 1; i++) {qu2.offer(qu1.poll());}return qu1.poll();}else {int size=qu2.size();for (int i = 0; i < size - 1; i++) {qu1.offer(qu2.poll());}return qu2.poll();}}public int top() {int tmp=-1;if (empty()){return -1;//栈为空}if (!qu1.isEmpty()){int size=qu1.size();for (int i = 0; i < size; i++) {tmp=qu1.poll();qu2.offer(tmp);//出的最后一个元素存在tmp即为栈顶元素}return tmp;}else {int size=qu2.size();for (int i = 0; i < size; i++) {tmp=qu2.poll();qu1.offer(tmp);}return tmp;}}public boolean empty() {return qu2.isEmpty() && qu1.isEmpty();}
}