【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. 括号匹配问题
题目：
思路：
-
左括号和右括号是
匹配关系，考虑用栈的方法实现 -
栈里只放三种
左括号 -
遍历字符串，
遇到左括号，将其入栈，遇到右括号，就查看栈顶的左括号，看是否能匹配。如果能匹配上，就将此左括号出栈（删除），如果最后栈为空，那么它是有效的括号，反之不是。
实现代码
class Solution {
public boolean isValid(String s) {
if(s==null||s.length()==0){
return true;
}
//定义一个栈，来存放左括号
Stack stack = new Stack();
//遍历字符串
for(int i =0; i<s.length(); i++){
//获取当前i小标是一个啥字符
char ch = s.charAt(i);
//判断当前的字符是哪个左括号，因为题上说 只有3种左括号。
if(ch=='('||ch=='['||ch=='{'){
stack.push(ch);
}else{
//进入else 说明当前i下标是一个右括号
//但是 要判断栈空不空，有可能第一个括号就是右括号
if(stack.empty()){
//说明右括号多了
return false;
}
//获取栈顶元素，只是查看是否能和读取到的括号匹配，不是出栈
char tmp = (char)stack.peek();
if(tmp=='('&& ch == ')'||tmp=='['&& ch == ']'||tmp=='{'&& ch == '}'){
//如果有可匹配的，就出栈当前的栈顶的括号
stack.pop();
}else{
//说明括号不匹配
return false;
}
}
}
//字符遍历完了，判断栈是否为空
if(stack.empty()){//如果栈最终为空，说明括号刚好都匹配上了
return true;
}else{//左括号多了
return false;
}
}
}
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中，不然会打乱队列顺序！
实现代码：
class MyQueue {
//创建两个栈
Stack<Integer> s1;//输入栈
Stack<Integer> s2;//输出栈
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}
public void push(int x) {
s1.push(x);//入队直接将元素压入S1即可
}
public int pop() {
int size = s1.size();//出队时，将s1中所以元素移至s2中
if(!s2.isEmpty()){
return s2.pop();//s2不为空，则直接弹出栈顶元素即可
}else{
for(int i=0; i<size; i++){//否则要将s1中元素转移到s2中再弹出s2栈顶元素
int tmp = s1.pop();
s2.push(tmp);
}
return s2.pop();
}
}
public int peek() {//和出队方法一样，只不过由删除变成查看，只看不删
int size = s1.size();
if(!s2.isEmpty()){
return s2.peek();
}else{
for(int i=0; i<size; i++){
int tmp = s1.pop();
s2.push(tmp);
}
return s2.peek();
}
}
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}
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;
}
}
🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙
❤原创不易，如有错误，欢迎评论区留言指出，感激不尽❤
❤ 如果觉得内容不错，给个三连不过分吧~ ❤
❤ 看到会回访~ ❤
🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙