devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】栈和队列面试题总结(持续更新中...)_栈和队列的相关问题

作者：知新_RL | 2024-06-08 21:28:04

赞

踩

栈和队列的相关问题

目录

一、栈相关基础概念

二、队列相关基础概念

三、OJ题

3.1 不可能的出栈顺序

3.2 中缀表达式

3.3 括号匹配

3.4 逆波兰表达式求值

3.5 出栈入栈次序匹配

3.6 循环队列

3.7 用队列实现栈

3.8 用栈实现队列

3.9 最小栈

一、栈相关基础概念

① 先进先入。不是所有进完才可以出，入的同时也可以出。

②用数组实现栈：入栈和出栈的时间复杂度是O(1)

③用单链表实现栈：

头插法： 入栈和出栈 O(1)

尾插法：入栈和出栈 O(n)

所以用单链表实现栈时一定要头入头出。

④方法  push、peek、pop、size、empty

二、队列相关基础概念

① 队尾进，队头出。底层是个双向链表。

②Queue是个接口，在实例化时必须实例化LinkedList的对象。

        Queue<Integer> q = new LinkedList<>();

③用单链表实现队列  ok

④ 用数组实现队列 。必须使用循环数组。后面3.6有代码实现逻辑。

④方法  offer、poll、peek、size、isEmpty

三、OJ题

3.1 不可能的出栈顺序

核心：入的时候同时可以出

3.2 中缀表达式

中缀转后缀：按照自己的理解，从左往右加括号，先乘除后加减。再逐步将运算符移到括号后，移

                        掉所有的(),就是rug

计算中缀表达式的值：遇见数字入栈，遇到运算符就从栈出两个元素。先出的放在运算符的后面，后出栈的放在运算符前面。将计算结果再入栈。

3.3 括号匹配

 OJ链接：20. 有效的括号 - 力扣（LeetCode）

实现代码：

  1. class Solution {
  2.     public boolean isValid(String s) {
  3.         Stack<Character> stack = new Stack<>();
  4.         for(int i = 0 ;i<s.length();i++){
  5.             char ch = s.charAt(i);
  6.             // 遇见左括号就入栈，注意是单引号
  7.             if(ch == '[' || ch == '{' || ch == '('){
  8.                 stack.push(ch);
  9.             }else{
  10.                 // 否则，就与栈顶元素进行比较
  11.                 // 如果栈是空的，并且遇见的是右括号，直接返回false
  12.                 // 判断栈空 不能使用stack==null
  13.                 if(stack.isEmpty()){
  14.                     return false;
  15.                 }else{
  16.                     char peek = stack.pop();
  17.                     if( (peek == '[' && ch == ']') || (peek == '{' && ch == '}') || (peek == '(' && ch ==')')){
  18.                         continue;
  19.                     }else{
  20.                         return false;
  21.                     }
  22.                 }
  23.             }
  24.         }
  25.         if(stack.isEmpty()){
  26.             return true;
  27.         }else{
  28.             return false;
  29.         }
  30.     }
  31. }

3.4 逆波兰表达式求值

 OJ链接：150. 逆波兰表达式求值 - 力扣（LeetCode）

实现代码：

  1. class Solution {
  2.  
  3.     public int evalRPN(String[] tokens) {
  4.         Stack<Integer> stack = new Stack<>();
  5.         HashSet<String> set = new HashSet<>();
  6.         set.add("+");
  7.         set.add("-");
  8.         set.add("*");
  9.         set.add("/");
  10.         for(String str:tokens){
  11.             // 如果遇见的是不是运算符，是数字，就入栈
  12.             if(!set.contains(str)){
  13.                 stack.push(Integer.parseInt(str));
  14.             }else{
  15.                 // 遇见运算符，就弹出两个数字
  16.                 int back = stack.pop();
  17.                 int front = stack.pop();
  18.                 HashMap<String,Integer> hashMap = new HashMap<>();
  19.                 hashMap.put("+",front+back);
  20.                 hashMap.put("-",front-back);
  21.                 hashMap.put("*",front*back);
  22.                 //  注意：back有可能为 0 
  23.                 if(back != 0){
  24.                     hashMap.put("/",front/back);
  25.                 }
  26. //计算结果，将结果入栈
  27.                 int result = hashMap.get(str);
  28.                 stack.push(result);
  29.             }
  30.         }
  31.         return stack.peek();
  32.     }
  33. }

3.5 出栈入栈次序匹配

 OJ链接：栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)

 解题思路：

要点1：定义一个pos，记录popA数组中元素的位置。

要点2：遍历pushA，依次将pushA中的元素入栈，判断栈顶元素和popA中的元素是否相同，相同就出栈，并观察popA中的下一个元素是否和新栈顶元素相等。如果不相等，入栈pushA的下一个元素

实现代码：

  1. import java.util.*;
  2. import java.util.ArrayList;
  3.  
  4. public class Solution {
  5.     public boolean IsPopOrder(int [] pushA,int [] popA) {
  6.         Stack<Integer> stack1 = new Stack();
  7.         int pos = 0;
  8.         for(int i=0;i<pushA.length;i++){
  9.             stack1.push(pushA[i]);
  10.             while(!stack1.isEmpty() && stack1.peek() == popA[pos]){
  11.                 stack1.pop();
  12.                 pos++;
  13.             }
  14.         }
  15.         if(stack1.empty()){
  16.             return true;
  17.         }
  18.         return false;
  19.     }
  20. }

3.6 循环队列

 OJ链接：622. 设计循环队列 - 力扣（LeetCode）

​ 解题思路：

要点1：为了区分队列空和满，约定：

        rear指向数组最后一个元素的下一个位置，下一次添加数据，可以直接往rear位置上放

        front == rear 队列空

        rear的下一个元素是front，队列满了。（rear+1）%elem.length

要点2：返回队列顶部元素，返回front所在位置元素，front向前移。为了保证front可以从3移到1，front=（front+1）%elem.length

要点3：返回队列最后一个元素。如果rear=0，返回elem[elem.length-1].如果rear不为0，就返回elem[rear-1]

实现代码：

  1. class MyCircularQueue {
  2.  
  3.     private int[] elem;
  4.     private int front;
  5.     private int rear;
  6.  
  7.     public MyCircularQueue(int k) {
  8.         elem = new int[k+1];
  9.     }
  10.     
  11.     public boolean enQueue(int value) {
  12.         if(isFull()){
  13.             return false;
  14.         }
  15.         if(isEmpty()){
  16.             elem[0] = value;
  17.             front = 0;
  18.             rear = 1;
  19.             return true;
  20.         }
  21.         elem[rear] = value;
  22.         rear = (rear+1) % elem.length;
  23.         return true;
  24.     }
  25.     
  26.     public boolean deQueue() {
  27.         if(isEmpty()){
  28.             return false;
  29.         }
  30.         front = (front+1) % elem.length;
  31.         return true;
  32.     }
  33.     
  34.     public int Front() {
  35.         if(isEmpty()){
  36.             return -1;
  37.         }
  38.         return elem[front];
  39.  
  40.     }
  41.     
  42.     public int Rear() {
  43.         if(isEmpty()){
  44.             return -1;
  45.         }
  46.         if(rear == 0){
  47.             return elem[elem.length-1];
  48.         }
  49.         return elem[rear-1];
  50.  
  51.     }
  52.     
  53.     public boolean isEmpty() {
  54.         return rear == front;
  55.  
  56.     }
  57.     
  58.     public boolean isFull() {
  59.         if((rear+1)%elem.length == front){
  60.             return true;
  61.         }
  62.         return false;
  63.  
  64.     }
  65. }

3.7 用队列实现栈

 OJ链接：225. 用队列实现栈 - 力扣（LeetCode）

解题思路：

要点1：有两个队列

要点2：第一次放push数据时，默认放到队列1中

要点3：添加元素时，添加到不为空的队列中，这样才能保证顺序

要点4：出栈—》获得栈顶元素—》栈后入先出—》弹出最后一个入栈的元素

因此，需要找出最后一个入队列的元素。将队列的前n-1个元素，放到另外一个队列中，剩下的就是最后一个入队列的元素

实现代码：

  1. class MyStack {
  2.  
  3.     private Queue<Integer> qu1;
  4.     private Queue<Integer> qu2;
  5.  
  6.     public MyStack() {
  7.         qu1 = new LinkedList<>();
  8.         qu2 = new LinkedList<>();
  9.     }
  10.     
  11.     public void push(int x) {
  12.         // 如果队列2是空的，就往队列1里面放。原因：只有放在不为空的队列中顺序才不会乱
  13.         if(qu2.isEmpty()){
  14.             qu1.offer(x);
  15.         }else{
  16.             qu2.offer(x);
  17.         }
  18.         
  19.     }
  20.     
  21.     public int pop() {
  22.         if(empty()){
  23.             return -1;
  24.         }
  25.         if(qu1.isEmpty()){
  26.             // 队列2不为空，队列先进先出，将队列前size-1个元素放到队列1中，剩下的最后一个元素就是最后入队列的，也就是栈的第一个元素，将其返回
  27.             int size = qu2.size();
  28.             while(size > 1){
  29.                 qu1.offer(qu2.poll());
  30.                 size--;
  31.             }
  32.             int result = qu2.poll();
  33.             return result;
  34.         }
  35.         if(qu2.isEmpty()){
  36.             int size = qu1.size();
  37.             while(size > 1){
  38.                 qu2.offer(qu1.poll());
  39.                 size--;
  40.             }
  41.             int result = qu1.poll();
  42.             return result;
  43.         }
  44.         return -1;
  45.     }
  46.     public int top() {
  47.         if(empty()){
  48.             return -1;
  49.         }
  50.         if(qu1.isEmpty()){
  51.             int size = qu2.size();
  52.             while(size > 1){
  53.                 qu1.offer(qu2.poll());
  54.                 size--;
  55.             }
  56.             int result = qu2.poll();
  57.             qu1.offer(result);
  58.             return result;
  59.         }
  60.         if(qu2.isEmpty()){
  61.             int size = qu1.size();
  62.             while(size > 1){
  63.                 qu2.offer(qu1.poll());
  64.                 size--;
  65.             }
  66.             int result = qu1.poll();
  67.             qu2.offer(result);
  68.             return result;
  69.         }
  70.         return -1;
  71.  
  72.     }
  73.     
  74.     public boolean empty() {
  75.         return qu1.isEmpty()&&qu2.isEmpty();
  76.     }
  77. }

3.8 用栈实现队列

 OJ链接：232. 用栈实现队列 - 力扣（LeetCode）

​ 解题思路：

要点1：有两个栈。存数据都存到栈1中，取数据都从栈2中取。

要点2：取数据时，如果栈2是空的，就把栈1中的元素全放到栈2中。再从栈2中取。

实现代码：

  1. class MyQueue {
  2.     private Stack<Integer> stack1;
  3.     private Stack<Integer> stack2;
  4.     public MyQueue() {
  5.         stack1 = new Stack();
  6.         stack2 = new Stack();
  7.     }
  8.     
  9.     public void push(int x) {
  10.         stack1.push(x);
  11.     }
  12.     
  13.     public int pop() {
  14.         if(empty()){
  15.             return -1;
  16.         }
  17.         if(stack2.empty()){
  18.             while(!stack1.empty()){
  19.                 stack2.push(stack1.pop());
  20.             }
  21.         }
  22.         return stack2.pop();
  23.     }
  24.     
  25.     public int peek() {
  26.         if(empty()){
  27.             return -1;
  28.         }
  29.         if(stack2.empty()){
  30.             while(!stack1.empty()){
  31.                 stack2.push(stack1.pop());
  32.             }
  33.         }
  34.         return stack2.peek();
  35.  
  36.     }
  37.     
  38.     public boolean empty() {
  39.         return stack1.empty()&&stack2.empty();
  40.  
  41.     }
  42. }

3.9 最小栈

 OJ链接：155. 最小栈 - 力扣（LeetCode）

 解题思路：

要点1：创建两个栈。一个栈存放所有的元素，另外一个栈存放栈中最小的元素

要点2：第一次push数据，数据存放在两个栈中

要点3：之后存放数据，该数据小于等于最小栈的栈顶元素，才能存放到最小栈和stack中。否则，就只能存放到stack中

实现代码：

  1. class MinStack {
  2.     public Stack<Integer> stack;
  3.     public Stack<Integer> minStack;
  4.  
  5.     public MinStack() {
  6.         stack = new Stack();
  7.         minStack = new Stack();
  8.     }
  9.     
  10.     public void push(int val) {
  11.         // 如果第一次放元素，往stack和minStack里都放
  12.         if(stack.empty() && minStack.empty()){
  13.             stack.push(val);
  14.             minStack.push(val);
  15.             return;
  16.         }
  17.         // 如果存放的数据比minStack元素小，该元素同时放到两个栈中
  18.         if(val <= minStack.peek()){
  19.             stack.push(val);
  20.             minStack.push(val);
  21.             return;
  22.         }else{
  23.             // 否则，就只往stack中放
  24.             stack.push(val);
  25.             return;
  26.         }
  27.     }
  28.     
  29.     public void pop() {
  30.         int peek = stack.pop();
  31.         if(peek == minStack.peek()){
  32.             minStack.pop();
  33.         }
  34.     }
  35.     
  36.     public int top() {
  37.         if(stack.empty()){
  38.             return -1;
  39.         }
  40.         return stack.peek();
  41.  
  42.     }
  43.     
  44.     public int getMin() {
  45.         if(minStack.empty()){
  46.             return -1;
  47.         }
  48.         return minStack.peek();
  49.  
  50.     }
  51. }


 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/691257
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号