栈和队列相关知识题目

栈的底层原理

栈（Stack）是一种后进先出（LIFO）​的线性数据结构，所有操作（如插入、删除）仅在栈顶进行。它的底层实现可以是数组或链表，具体取决于编程语言和应用场景。

1.基于数组实现：使用连续内存的数组存储元素，通过一个指针（如 top）标记栈顶位置。

核心操作：入栈（Push）​：将元素放入 top 位置，top 指针后移。​

出栈（Pop）​：返回 top-1 位置的元素，top 指针前移。

2. 基于链表（链式存储）:使用单向链表（头插法）存储元素，链表的头节点作为栈顶。

入栈（Push）​：将新节点插入链表头部。

​出栈（Pop）​：删除链表头节点并返回其值。

栈的应用场景

函数调用与递归：操作系统自动管理函数调用栈。
​括号匹配：检查表达式中的括号是否成对。
​表达式求值：中缀表达式转后缀表达式（逆波兰式）。
​撤销操作（Undo）​：编辑器中的操作历史栈。
​深度优先搜索（DFS）​：用栈保存遍历路径

对应题目 

用栈实现队列用栈实现队列用栈实现队列

思想：用两个栈来模拟队列，由于队列是先进先出，所以设置两个栈，一个入队栈，一个出队栈

import java.util.Deque;
import java.util.ArrayDeque;class MyQueue {private Deque<Integer> inputStack;private Deque<Integer> outputStack;public MyQueue() {inputStack = new ArrayDeque<>();outputStack = new ArrayDeque<>();}// 入队：直接压入输入栈public void push(int x) {inputStack.push(x);}// 出队：若输出栈为空，先转移元素public int pop() {if (outputStack.isEmpty()) {transferInputToOutput();}return outputStack.pop();}// 查看队首元素：类似出队但不删除public int peek() {if (outputStack.isEmpty()) {transferInputToOutput();}return outputStack.peek();}// 判断队列是否为空public boolean empty() {return inputStack.isEmpty() && outputStack.isEmpty();}// 将输入栈元素转移到输出栈（反转顺序）private void transferInputToOutput() {while (!inputStack.isEmpty()) {outputStack.push(inputStack.pop());}}
}

用队列实现栈用队列实现栈用队列实现栈用队列实现栈

思想：队列模拟栈，使用两个队列来模拟，一个主队列，一个副队列

核心思想

• 维护两个队列：一个主队列（mainQueue）和一个辅助队列（tempQueue）。
• ​入栈（Push）​：直接将元素加入主队列。
• ​出栈（Pop）​：将主队列中除最后一个元素外的所有元素转移到辅助队列，弹出最后一个元素，最后交换主队列和辅助队列的角色。

​操作步骤

1. ​Push（入栈）​：
   • 将新元素直接加入主队列。
2. ​Pop（出栈）​：
   • 将主队列中的前 n-1 个元素依次出队并加入辅助队列。
   • 弹出主队列的最后一个元素（即栈顶元素）。
   • 交换主队列和辅助队列的角色，以便下次操作。

   • import java.util.LinkedList;
     import java.util.Queue;class MyStack {private Queue<Integer> mainQueue;private Queue<Integer> tempQueue;public MyStack() {mainQueue = new LinkedList<>();tempQueue = new LinkedList<>();}// 入栈：直接加入主队列public void push(int x) {mainQueue.offer(x);}// 出栈：转移前n-1个元素后弹出最后一个元素public int pop() {while (mainQueue.size() > 1) {tempQueue.offer(mainQueue.poll());}int top = mainQueue.poll();// 交换主队列和辅助队列Queue<Integer> swap = mainQueue;mainQueue = tempQueue;tempQueue = swap;return top;}// 查看栈顶元素：逻辑同pop，但需将元素重新放回主队列public int top() {while (mainQueue.size() > 1) {tempQueue.offer(mainQueue.poll());}int top = mainQueue.poll();tempQueue.offer(top); // 重新加入队列// 交换队列Queue<Integer> swap = mainQueue;mainQueue = tempQueue;tempQueue = swap;return top;}// 判空：主队列是否为空public boolean empty() {return mainQueue.isEmpty();}
     }

有效的括号有效的括号

思想：括号匹配是使用栈解决的经典问题。遇见左括号就压入栈中，遇见右括号，先判断栈是否为空，在导出栈顶元素判断，若最后栈为空则说明符号匹配成功，若左右括号不匹配也返回失败。

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

删除字符串中的所有相邻重复项 

思想：比较简单，需要注意一个点就是，栈无法直接转化成数组，即stack.toString()是错误的
要创建数组，将栈中的元素都出栈即可

class Solution {public String removeDuplicates(String s) {Stack<Character> stack =new Stack<>();for(int i=0;i<s.length();i++){char c = s.charAt(i);if(stack.isEmpty() || c != stack.peek()){stack.push(c);}else {stack.pop();}}String str = "";//剩余的元素即为不重复的元素while (!stack.isEmpty()) {str = s.pop() + str;}return str;}
}

逆波兰表达式求值

要注意下述代码中的几个问题：
1.因为字符串表示的是整数的加减乘除运算，所以定义栈的时候要采取整型Stack<Integer> stack =new Stack<>();
2.定义两个变量分别存储前两个操作数，但要注意操作数的顺序，因为先进后出，所以第一个出来的是第二个操作数
3.巧用switch分支结构，先做判断，在压入栈
4.最后不是输出整个栈的元素，方法要求的返回表达式值的整数，所以要做类型转换Integer.valueOf(token)

5.由于leetcode 内置jdk的问题，不能使用==判断字符串是否相等，只能用equals。并且字符相等用双引号

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack =new Stack<>();int a,b,c;for(String token :tokens){if(token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/") ){b = stack.pop();//第二个操作数a = stack.pop();//第一个操作数c = switch(token){case "+" -> a+b;case "-" -> a-b;case "*" -> a*b;case "/" -> a/b;default ->  0;};stack.push(c);}else {stack.push(Integer.valueOf(token));}}return stack.pop();}
}

有效的括号用队列实现栈用队列实现栈用队列实现栈