栈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());//拿到头结点3

2、栈的实际应用

（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();}
}