当前位置：首页 > news >正文

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

news 来源：原创 2025/5/23 13:42:36

栈与队列

选择题
括号匹配
逆波兰表达式求值
出栈入栈次序匹配
最小栈
设计循环队列
面试题
- 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. 获取队头注意空队列时返回-16. 获取队尾时，注意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<>();}// 入队类时，直接找s1public 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();}
}