• 【数据结构】栈和队列面试题总结(持续更新中...)

    目录

    一、栈相关基础概念

    二、队列相关基础概念

    三、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 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 stack = new Stack<>();
    4.         for(int i = 0 ;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 stack = new Stack<>();
    5.         HashSet 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 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 stack1 = new Stack();
    7.         int pos = 0;
    8.         for(int i=0;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 qu1;
    4.     private Queue 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 stack1;
    3.     private Stack 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 stack;
    3.     public Stack 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. }


     

  • 相关阅读:
    Minillama3-＞训练tokenizer
    hadoop 实现数据排序
    软考高项-成本管理
    在uni-app中使用手机号一键登录
    前端开发---在vue项目中使用openLayers
    apollo源码解读：/cyber/sysmo 模块
    【Python】按特定条件查找列表的最小/最大值
    AN基础工具——动画人物上色
    笔试题之指针结合数组的精讲2
    作战仿真试验理论体系研究
  • 原文地址：https://blog.csdn.net/weixin_44258092/article/details/126240946