【Java数据结构】栈与队列 经典面试题——解题笔记+动图思路
1. 实现一个最小栈
题目：
思路：
实现代码
2. 括号匹配问题
题目：
思路：
实现代码
3. 用队列实现栈
题目：
思路：
实现代码：
4. 用栈实现队列
题目：
思路：
实现代码：
5. 设计循环队列
题目：
思路：
实现代码：
1. 实现一个最小栈
题目：
思路：
把题目要求的最小栈内部分为两个栈，一个stack用于储存所有元素，另一个min_stack用于储存最小的元素
压入第一个元素时，这个元素就是当前栈里最小元素，所以不光要压入stack栈中也要压入min_stack栈中
压入第二个元素的时候，要判断这个元素是否小于min_stack里的栈顶元素，如果小于，则将其压入min_stack
总之min_stack栈顶元素要始终保持是栈里最小的元素
删除栈顶元素的时候，除了要弹出stack里的栈顶元素
还要判断这个栈顶元素是否和min_stack栈里的栈顶元素相同，如果相同则要把min_stack栈里的栈顶元素也弹出
因为min_stack只是辅助栈，一个元素如果在储存元素的栈里都没了，辅助栈里怎么能还有呢？
获取栈顶元素就简单了，直接用java自带的方法peek（）就好了，只是获取，不操作
检索最小元素就更简单了，min_stack栈是用来干嘛的？
就是用来存最小元素的嘛，直接弹出min_stack栈栈顶元素可以了
这个栈顶元素必然是整个栈里的最小元素
实现代码
class MinStack { Stack<Integer> stack; Stack<Integer> MinStack; public MinStack() {//构造两个栈，一个普通栈，一个辅助栈 stack = new Stack<>(); MinStack = new Stack<>(); } public void push(int val) { stack.push(val);//压入元素 if(MinStack.isEmpty()){ MinStack.push(val);如果两个栈都是空，也要将此元素压入辅助栈 } else{ if(val <= MinStack.peek())//如果新压入的元素小于辅助栈栈顶元素 MinStack.push(val);//将新元素压入辅助栈 } } public void pop() { //如果从普通栈中弹出的元素等于辅助栈的栈顶元素，那么也要将此元素从辅助栈弹出 if(stack.pop().equals(MinStack.peek())){//这里要用eqauls，不能用==，pop方法和peek方法返回的是一个object类型，也就是两个对象，我们要比较对象的值，如果用==，比较的是对象的地址 MinStack.pop();//弹出辅助栈栈顶元素 } } public int top() { if(MinStack.isEmpty()){ return -1; } return stack.peek();//查看普通栈栈顶元素 } public int getMin() { if(MinStack.isEmpty()){ return -1; } return MinStack.peek();//查看辅助栈栈顶元素 } }
2. 括号匹配问题
题目：
思路：
- 左括号和右括号是
匹配关系，考虑用栈的方法实现 - 栈里只放三种
左括号 - 遍历字符串，
遇到左括号，将其入栈，遇到右括号，就查看栈顶的左括号，看是否能匹配。如果能匹配上，就将此左括号出栈（删除），如果最后栈为空，那么它是有效的括号，反之不是。
实现代码
3. 用队列实现栈
题目：
思路：
栈是先进后出，队列是先进先出，所以这里用两个队列来回倒，从而实现栈
抓住一个关键点，不管入栈还是出栈，都找不为空的队列进行操作
入栈时，找到不为空的队列，从队列尾部插入元素即可，就达到了入栈的效果
出栈时，找到不为空的队列，将size-1个元素加入到另一个空的队列里，然后把这个队列最后一个元素出列，就达到了出栈效果
返回栈顶元素方法与出栈类似（注意，只查看，不删除），不过要设置一个临时变量tmp储存最后出队的那个元素，而且最后出队的这个元素也要继续加入另一个队列，不然就是出栈操作了
实现代码：
class MyStack { //创建两个队列 Queue<Integer> que1; Queue<Integer> que2; public MyStack() { que1 = new LinkedList<>();//队列是接口，不能直接实例化 que2 = new LinkedList<>();//队列是由链表实现的，所以要用链表来实例化队列 } public void push(int x) { if(empty()){//一开始两个队列都是空的时候，默认将第一个元素插入到que1中 que1.offer(x); }else{//从第二个元素开始，哪个队列不为空，对哪个队列进行插入操作 if(que1.isEmpty()){ que2.offer(x); }else{ que1.offer(x); } } } public int pop() { if(empty()){ return -1; } //出栈也是找哪个队列不为空，就对哪个队列进行操作 if(que1.isEmpty()){ int size = que2.size(); for(int i =0 ; i<size-1 ;i++){ int tmp = que2.poll(); que1.offer(tmp); } return que2.poll(); }else{ int size = que1.size(); for(int i =0 ; i<size-1 ;i++){ int tmp = que1.poll(); que2.offer(tmp); } return que1.poll(); } } public int top() { if(empty()){ return -1; } //查看栈顶元素，和出栈类似，只不过记得把队列最后一个元素继续插入到另一个队列的最后 //不然就是出栈操作了 if(que1.isEmpty()){ int size = que2.size(); int tmp = -1; for(int i =0 ; i<size ;i++){ tmp = que2.poll(); que1.offer(tmp); } return tmp; }else{ int size = que1.size(); int tmp = -1; for(int i =0 ; i<size ;i++){ tmp = que1.poll(); que2.offer(tmp); } return tmp; } } public boolean empty() { return que1.isEmpty() && que2.isEmpty(); } }
4. 用栈实现队列
题目：
思路：
队列是先进先出，需要用到两个栈才能实现队列
指定S1为输入栈，S2为输出栈
入队时，直接将元素压入S1栈即可
出队时，要将输入栈S1中的元素依次出栈，并压入输出栈S2中，然后将S2栈顶元素出栈，这样就能实现先入队的元素先出队，有一点要注意，只有S2为空的时候，才能将输入栈S1中的元素移到S2中，不然会打乱队列顺序！
实现代码：
5. 设计循环队列
题目：
思路：
要设计一个循环队列，用到的是一个数组，需要设置一个front下标表示队列首元素，rear下标，表示尾元素后一个可用位置的下标
有三个关键问题要解决：
①front和rear相遇之后，队列到底是空了还是满了？
答：每次再放元素的时候，都去判断rear位置的下一个位置是不是front，如果是，就满了，所以要预留一个空间，不放元素
②rear每次存放完成之后，能不能进行rear=rear+1
③front每次出队之后，能不能进行front=front+1
答：rear和front都不能直接+1，因为假设7个元素的循环队列，下标走到6了，6+1=7 数组此时能访问7下标嘛？不能，所以研究处一个公式rear/front = (rear/front+1)%len就能表示下一个位置了
实现代码：
class MyCircularQueue { private int[] elem; //数组 private int front;// 头 private int rear;//尾巴下标 当前可以存放元素的下标 public MyCircularQueue(int k) { //这里为什么是k+1: 题的描述指定要放k个，因为用我的方法实现的时候就是多一个空间出来的 this.elem = new int[k+1]; this.rear = 0; this.front = 0; } //入队 public boolean enQueue(int value) { if(isFull()) //判断循环队列满了没有 return false;//满了就返回false this.elem[this.rear] = value;//没满就给rear位置插入元素 this.rear = (this.rear+1)%this.elem.length;//然后rear下标往后走一步 //this.rear = this.rear+1; return true; } //删除 出队 public boolean deQueue() { if(isEmpty()) {//先判断循环队列是否空 return false;//空的就返回false } //循环队列不为空，就将首元素位置，front往后走一步 //原来的元素会被以后加入的覆盖掉，或者不再能被访问到 this.front = (this.front+1)%this.elem.length; return true; } //得到队头元素 public int Front() { if(isEmpty()) {//依旧先判断是否为空 return -1; } return this.elem[this.front]; } //得到队尾元素 注意：当rear == 0下标的时候 public int Rear() { if(isEmpty()) {//依旧先判断是否为空 return -1; } //这里注意一个问题，我们已经知道rear-1位置就是队尾元素，可是当rear=0的时候，0-1=-1，这样不就出错了？所以遇到这种情况的时候用 循环队列的长度-1 就是0下标的上一个位置了 int index = (this.rear == 0) ? this.elem.length-1 : this.rear-1; return this.elem[index]; } public boolean isEmpty() { //只要他两相遇了 那么就是空的队列 if(this.front == this.rear) { return true; } return false; } public boolean isFull() { //判断rear位置的下一个位置是不是front，如果是，就满了 if((this.rear+1) % this.elem.length == this.front) { return true; } return false; } }
