数据结构和算法|栈和队列相关面试题 LeetCode|面试|栈和队列|java|循环

前言：
上篇文章介绍了栈和队列及其相关操作，本篇通过几个面试题，来进一步掌握栈和队列~

文章图片

目录

- 括号匹配问题
- 用队列实现栈
- 用栈实现队列
- 实现一个最小栈
- 设计一个循环队列

括号匹配问题题目：在线OJ

文章图片

思考：

创立一个栈，存储字符类型
遍历字符串，依次取出每个字符
若为左括号，即：(，[，{，则入栈，然后接着继续比较
若为右括号，则取出栈顶元素，与该元素匹配
最后，判断栈是否为空 (这一步一定不要忘)

图解：

文章图片

代码实现：

public boolean isValid(String s) {//创建一个栈,存储字符类型 Stack stack = new Stack<>(); //遍历字符串，依次取出每个字符 for(int i = 0; i < s.length(); i++){//使用charAt，取出每个元素 char c = s.charAt(i); //如果 c 为左括号，则入栈 if(c == '(' || c == '[' || c== '{'){stack.push(c); continue; } if(stack.empty()){return false; } //若 c 为右括号，则取出栈顶元素，与该元素比较 char top = stack.pop(); if(top == '(' && c == ')'){continue; } if(top == '[' && c == ']'){continue; } if(top == '{' && c == '}'){continue; } return false; } //最后判断栈是否为空 if(stack.empty()){return true; } return false; }

用队列实现栈题目：在线OJ

文章图片

思考：

创建两个队列 A B
入栈操作：把新元素直接往 A 中插入即可
出栈操作：将 A 中的元素往 B 中转移，当剩最后一个元素的时候，直接从 A 中出队列即可，最后将 A B 两队列交换，让 A 始终保持为入栈操作
取栈顶元素：和出栈类似，只不过最后一个元素不删除
判定为空：即 A 和 B 都为空，即为空

图解：

文章图片

代码实现：

class MyStack {//创建两个队列 private Queue A = new LinkedList<>(); private Queue B = new LinkedList<>(); //入栈 public void push(int x) {//直接往 A 中入队列即可 A.offer(x); } //出栈 public Integer pop() {//判断是否为空 if(empty()){return null; } //将 A 中的元素转移到 B 中 while(A.size() > 1){Integer a = A.poll(); //A 为空 if(a == null){break; } //插入到B中 B.offer(a); } //循环结束，A中应只有1个元素 //将此元素出队列即可 int ret = A.poll(); swapAB(); return ret; } //交换 A B public void swapAB(){Queue tmp = A; A = B; B = tmp; } //取栈顶元素 public Integer top() {//判断是否为空 if(empty()){return null; } //将 A 中的元素转移到 B 中 while(A.size() > 1){Integer a = A.poll(); //A 为空 if(a == null){break; } //插入到B中 B.offer(a); } //循环结束，A中应只有1个元素 //将此元素出队列即可 int ret = A.poll(); B.offer(ret); swapAB(); return ret; } //判断是否为空 public boolean empty() {return A.isEmpty() && B.isEmpty(); } }

用栈实现队列题目：在线OJ

文章图片

【数据结构和算法|栈和队列相关面试题】思考：

创建两个栈 A B；A 负责入队列，B 负责出队列
入队列：先把 B 中元素转移到 A 中，然后再直接往 A 中插入 (入栈)
出队列：先把 A 中元素转移到 B 中，然后对 B 进行出栈操作
取队首元素：先把 A 中元素转移到 B 中，然后取 B 的栈顶元素，即队首元素
判断是否为空： A 和 B 都为空

图解：

文章图片

代码实现：

class MyQueue {//创建两个栈 private Stack A = new Stack<>(); private Stack B = new Stack<>(); //入队列 public void push(int x) {//将B中元素转移到A中 while(!B.isEmpty()){int tmp = B.pop(); A.push(tmp); } //再把新元素入栈 A.push(x); } //出队列 public Integer pop() {//判断是否为空 if(empty()){return null; } //将A中元素转移到B中 while(!A.isEmpty()){int tmp = A.pop(); B.push(tmp); } //再对 B 出栈 return B.pop(); } //取队首元素 public Integer peek() {//判断是否为空 if(empty()){return null; } //将A中元素转移到B中 while(!A.isEmpty()){int tmp = A.pop(); B.push(tmp); } //直接取B的栈顶元素 return B.peek(); } //判断是否为空 public boolean empty() {return A.isEmpty() && B.isEmpty(); } }

实现一个最小栈题目：在线OJ

文章图片

思考：
即： A中进行正常的栈的三个操作，而B中存放当前A中最小元素

创建两个栈A B
对 A 进行正常的入 / 出栈，取栈顶元素操作
第一个元素在 A B 中均插入
之后，每在 A 中插入一个元素，都与 B 中元素栈顶元素比较，将较小值插入 B 中
最后 B 的栈顶元素，便是栈中所有元素中最小的那个

图解：

文章图片

代码实现：

class MinStack {//创建两个栈 A B private Stack A = new Stack<>(); private Stack B = new Stack<>(); //入栈 public void push(int val) {A.push(val); if(B.isEmpty()){B.push(val); return; } int min = B.peek(); if(val < min){min = val; } B.push(min); }//出栈 public Integer pop() {if(A.isEmpty()){return null; } B.pop(); return A.pop(); }//取栈顶元素 public Integer top() {if(A.isEmpty()){return null; } return A.peek(); }//取最小元素 public Integer getMin() {if(A.isEmpty()){return null; } return B.peek(); } }

设计一个循环队列题目：在线OJ

文章图片

思考：
在介绍栈和队列中，我们设计了一个循环队列，但在那个实现中，tail 始终就是队尾的下一个元素，那么当队列满时， tail 指向的位置就是空的，即：数组中有一个位置是浪费的，显然那个思路不适合本题
当队列头或队列尾的索引值到达数组上限时，需要再从零开始
可以：head = (head + 1) % array.length，索引值就会自动进行循环
代码实现：

class MyCircularQueue {private int[] array = { 0}; private int head = 0; private int tail = -1; private int size = 0; publicMyCircularQueue(int k) {this.array = new int[k]; }//入队列 public boolean enQueue(int value) {//判断是否为满队列 if(isFull()){return false; } this.tail = (this.tail + 1) % this.array.length; this.array[tail] = value; this.size++; return true; }//出队列 public boolean deQueue() {//判断是否为空 if(isEmpty()){return false; } this.head = (this.head + 1) % this.array.length; this.size--; return true; }//取队首元素 public int Front() {//判断是否为空 if(isEmpty()){return -1; } return this.array[head]; }//取队尾元素 public int Rear() {if(isEmpty()){return -1; } return this.array[tail]; } //判断是否为空 public boolean isEmpty() {return this.size == 0; } //判断是否为满队列 public boolean isFull() {return this.size == array.length; } }