【数据结构练习题】栈与队列

栈与队列

选择题
括号匹配
逆波兰表达式求值
出栈入栈次序匹配
最小栈
设计循环队列
面试题
- 1. 用队列实现栈。[OJ链接](https://leetcode.cn/problems/implement-stack-using-queues/solutions/)
- 2. 用栈实现队列。[OJ链接](https://leetcode.cn/problems/implement-queue-using-stacks/description/)

选择题

在这里插入图片描述

用无头单链表存储队列，front引用队头，back引用队尾，则在进行出队列操作时( )
A.仅修改front
B.front 和 back 都要修改
C.front 和 back 可能都要修改
D.仅修改back

出队列时：
如果队列中有多个节点时，只需要修改front
如果队列中只有一个节点时，front和back都需要修改
故应该选择C

下列关于队列的叙述错误的是( )
A.队列可以使用链表实现
B.队列是一种"先入先出"的数据结构
C.数据出队列时一定只影响队尾引用
D.数据入队列时一定从尾部插入

A正确：队列是尾插头删，就适合使用链表实现
B正确：队列的特性
C错误：如果队列中只有一个元素时，出队列后队尾和队头引用都会影响
D正确：队列的特性
故选择C

*4.下列关于用栈实现队列的说法中错误的是（）
A.用栈模拟实现队列可以使用两个栈，一个栈模拟入队列，一个栈模拟出队列
B.每次出队列时，都需要将一个栈中的全部元素导入到另一个栈中，然后出栈即可
C.入队列时，将元素直接往模拟入队列的栈中存放即可
D.入队列操作时间复杂度为O(1)

答案：B
选项B中，一个栈模拟入队列，一个栈模拟出队列，出队列时直接弹出模拟出队列栈的栈顶元素，当该栈为空时，将模拟入队列栈中所有元素导入即可，不是每次都需要导入元素，故错误
选项A中，栈和队列的特性是相反的，一个栈实现不了队列
选项C中，一个栈模拟入队列，一个栈模拟出队列，入队列时，将元素直接往模拟入队列的栈中存放
选项D中，入队列就是将元素放到栈中，因此时间复杂度就是O(1)

以下不是队列的基本运算的是（）
A.从队尾插入一个新元素
B.从队列中删除队尾元素
C.判断一个队列是否为空
D.读取队头元素的值

答案：B
解析：
队列只能从队头删除元素。

下面关于栈和队列的说法中错误的是（）
A.队列和栈通常都使用链表实现
B.队列和栈都只能从两端插入、删除数据
C.队列和栈都不支持随机访问和随机插入
D.队列是“先入先出”，栈是“先入后出”

A错误：栈是尾部插入和删除，一般使用顺序表实现，队列是头部删除尾部插入，一般使用链表实现
B错误：栈是后进先出，尾部插入和删除；队列是先进先出，尾部插入头部删除
C正确：栈只能访问栈顶元素，不支持随机访问，队列也不支持
D正确：栈和队列的特性
故错误的是A和B

9.下列关于顺序结构实现循环队列的说法，正确的是（）
A.循环队列的长度通常都不固定
B.直接用队头和队尾在同一个位置可以判断循环队列是否为满
C.通过设置计数的方式可以判断队列空或者满
D.循环队列是一种非线性数据结构

队列适合使用链表实现，使用顺序结构(即固定的连续空间)实现时会出现假溢出的问题，因此大佬们设计出了循环队列，循环队列就是为了解决顺序结构实现队列假溢出问题的
A错误：循环队列的长度都是固定的
B错误：队头和队尾在同一个位置时队列可能是空的，也可能是满的，因此无法判断
C正确：设置计数即添加一个字段来记录队列中有效元素的个数，如果队列中有效元素个数等于空间总大小时队列满，如果队列中有效元素个数为0时队列空
D错误：循环队列也是队列的一种，是一种特殊的线性数据结构
故选择C

现有一循环队列，其队头为front，队尾为rear(rear指向队尾数据的下一个位置)，循环队列长度为N,最多存储N-1个数据。其队内有效长度为（）
A.(rear - front + N) % N + 1
B.(rear - front + N) % N
C.(rear - front) % (N + 1)
D.(rear - front + N) % (N - 1)

答案：B
有效长度一般是rear-front, 但是循环队列中rear有可能小于front，减完之后可能是负数，所以需要+N，此时结果刚好是队列中有效元素个数，但如果rear大于front，减完之后就是有效元素个数了，再加N后有效长度会超过N，故需要%N。

下述有关栈和队列的区别，说法错误的是？
A.栈是限定只能在表的一端进行插入和删除操作。
B.队列是限定只能在表的一端进行插入和在另一端进行删除操作。
C.栈和队列都属于线性表
D.栈的插入操作时间复杂度都是o(1)，队列的插入操作时间复杂度是o(n)

A正确：参考栈的概念
B正确：参考队列的概念
C正确：栈和队列都是特殊的线性表，因为线性表可以在任意位置插入或者删除，但是栈和队列就没有，相当于栈和队列属于阉割版的线性表
D错误：栈和队列插入、删除操作的时间复杂度都是O(1)
故选择D

括号匹配

括号匹配
在这里插入图片描述
只要是左括号就入栈
遇到右括号就开始匹配
1.和栈顶不匹配
2.栈为空
3.栈不为空但是字符串遍历完了

class Solution {
    public boolean isValid(String s) {
        Stack<Character>stack=new Stack<>();
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(ch=='('||ch=='['||ch=='{'){
                stack.push(ch);
            }else{
                if(stack.empty()){
                    return false;
                }
                char top=stack.peek();
                if(top=='('&&ch==')'||top=='['&&ch==']'||top=='{'&&ch=='}'){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        if(!stack.empty()){
            return false;
        }
        return true;
    }
}

逆波兰表达式求值

后缀表达式也叫逆波兰表达式
在这里插入图片描述

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack=new Stack<>();
        for(String s:tokens){
            if(!isOperation(s)){
                stack.push(Integer.parseInt(s));
            }else{
                int num2=stack.pop();
                int num1=stack.pop();
                switch(s){
                    case"+":
                        stack.push(num1+num2);
                        break;
                    case"-":
                        stack.push(num1-num2);
                        break;
                    case"*":
                        stack.push(num1*num2);
                        break;
                    case"/":
                        stack.push(num1/num2);
                        break;
                }
            }
        }
        return stack.pop();
    }
    public boolean isOperation(String s){
        if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/"))
            return true;
        return false;
    }
}

出栈入栈次序匹配

import java.util.*;

public class Solution {
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        Stack<Integer> stack = new Stack<>();
        int j=0;
        for(int i=0;i<pushV.length;i++){
            stack.push(pushV[i]);
            while(!stack.empty()&&j<popV.length&&stack.peek()==popV[j]){
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}

最小栈

最小栈
在这里插入图片描述

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minstack;
    public MinStack() {
        stack=new Stack<>();
        minstack=new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(minstack.empty()){
            minstack.push(val);
        }else{  //=要加上，否则stack中此数有多个 出栈时minstack也要出栈 数不够只有一个
            if(val<=minstack.peek()){
                minstack.push(val);
            }
        }
    }
   
    public void pop() {
        if(!stack.empty()){
            int ret=stack.pop();
            if(minstack.peek()==ret){
                minstack.pop();
            }
        }
    }
     //获取正常栈顶元素
    public int top() {
        if(stack.empty()){
            return -1; //oj题中轻易不要抛出异常 直接return-1即可
        }
        return stack.peek();
    }
    //获取最小栈顶元素
    public int getMin() {
        if(minstack.empty()){
            return -1;
        }
        return minstack.peek();
    }
}

设计循环队列

/*
    解题思路：
    1. 注意，循环队列底层空间大小是固定的
    2. 采用计数方式实现队列空或者满的判断
    3. 入队列时：队列可能满，往队尾插入，注意back在末尾特殊情况
    4. 出队列时：队列可能空，删除队头元素，注意front可能在队尾
    5. 获取队头注意空队列时返回-1
    6. 获取队尾时，注意back-1可能为负数，队尾元素下标：
       (back-1+array.length)%array.length
*/
class MyCircularQueue {
    int[] array;
    int front;   // 队头
    int back;    // 队尾
    int count;   // 队列中有效元素个数
    public MyCircularQueue(int k) {
        array = new int[k];
    }
    
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }

        // 在队尾插入一个元素，然后back往后移动
        array[back] = value;
        back++;

        // back往后移动之后，可能会来到空间末尾
        // 此时将back挪到空间起始位置
        if(back == array.length){
            back = 0;
        }

        count++;
        return true;
    }
    
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }

        // 出队列，队头往后移动
        ++front;

        // 队头往后移动之后也可能会来到空间末尾
        // 此时需要挪到空间起始位置
        front %= array.length;
        --count;
        return true;
    }
    
    public int Front() {
        if(isEmpty()){
            return -1;
        }

        // 如果队列不空，说明队列中有元素，队头元素直接返回front即可
        return array[front];
    }
    
    public int Rear() {
        if(isEmpty()){
            return -1;
        }

        // 如果队列不空，说明队列中有元素
        // 队尾元素即：back-1,
        // 如果back不在0号位置，back-1就是队尾元素下标
        // 如果back在0号位置，-1之后就是负数，因此需要+数组长度
        // 两个结合起来：
        return array[(back - 1 + array.length)%array.length];
    }
    
    public boolean isEmpty() {
        return 0 == count;
    }
    
    public boolean isFull() {
        return count == array.length;
    }
}

或
在这里插入图片描述

面试题

1. 用队列实现栈。OJ链接

注意：pop容易错写成下图 que.size是变量会随着循环改变应该提前记录一下que.size

/*
   解题思路：
     借助两个队列来模拟实现栈。一个队列是辅助的，起到导元素的作用
     入栈：
       先将元素放入a队列中，如果b不空，将b中所有元素导入到a中
       此时，刚刚入栈的元素刚好在a的队头，然后将a和b队列交换下
       即：b队列队头相当于栈顶，b队列队尾相当于栈底
     出栈：
       直接从b中poll()即可
     获取栈顶元素：
       直接从b中peek()即可
 */
class MyStack {
    private Queue<Integer> a;  // a是用来辅助导元素的
    private Queue<Integer> b;  // 元素全部放在b中
    public MyStack() {
        a = new LinkedList<>();
        b = new LinkedList<>();
    }
    
    public void push(int x) {
        // 先把元素放入a队列中
        a.offer(x);

        while(!b.isEmpty()){
            a.offer(b.poll());
        }

        Queue<Integer> temp = a;
        a = b;
        b = temp;
    }
    
    public int pop() {
        return b.poll();
    }
    
    public int top() {
        return b.peek();
    }
    
    public boolean empty() {
        return b.isEmpty();
    }
}

2. 用栈实现队列。OJ链接

/*
    解题思路：
     利用两个栈模拟实现队列
     入队列：s1模拟入队列，所有入队列的元素都放入到s1中
     出队列：s2模拟出队列，当s2为空时，将s1中所有元素导入到s2中
            s2中pop一个元素
     获取队头元素：如果s2是空，将s1中所有元素导入s2中，然后peek()一个元素
 */
class MyQueue {
    private Stack<Integer> s1;  // 模拟入队列，所有元素都放入到s1中
    private Stack<Integer> s2;
    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
    
    // 入队类时，直接找s1
    public void push(int x) {
        s1.push(x);
    }
    
    // 出队列：如果s2是空的，需要将s1中的所有元素导入到s2中
    // 此时s1先压入的元素就后进入到s2中，出的时候就先出了
    public int pop() {
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    
    public int peek() {
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    
    public boolean empty() {
        return s1.empty() && s2.empty();
    }
}