【数据结构练习题】队——1.用队实现栈2.用栈实现队

本文主要是介绍【数据结构练习题】队——1.用队实现栈2.用栈实现队，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述
♥♥♥♥♥个人主页♥♥♥♥♥
♥♥♥♥♥数据结构练习题总结专栏♥♥♥♥♥
♥♥♥♥♥上一章：堆的练习题♥♥♥♥♥

文章目录

1.用队去实现栈
- 1.1问题描述
- 1.2思路分析
- 1.3绘图分析
- 1.4代码实现
- 2.用栈实现队
- 2.1问题描述
- 2.2思路分析
- 1.3绘图分析
- 2.4代码实现

1.用队去实现栈

1.1问题描述

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

1.2思路分析

首先，要实现用队去模拟一个有压栈，入栈，peek，判断栈是否为空这些功能的栈，用一个简单的队列是不能实现这个栈的，用一个双向队列是可以实现这个栈的，但我们今天不用双向队列来实现，我们用两个简单队列来实现这个栈。
在分析具体功能怎么实现的，我们先确定一些大前提：
1.我们先要创建两个简单队列分别设为q1，q2
2.确保这两个队列中必须是空的
接下来分析这些功能怎么实现的：
1.压栈
大前提：在压栈的过程中，始终需要保证一个队列中是空，目的是为了出栈
在压栈的过程中分两种情况：
1.1如果在压栈前两个队列都为空，则默认压入q1
1.2如果在压栈前有一个队是空的，则压入另一个不为空的队列中
2.出栈
2.1如果两个队列都是空，则直接返回false
2.2如果一个队列为空，另一个不为空，则只需要将不为空队列q1中的size-1个元素压到另一个队列q
2中然后最后不为空的队列q1中剩下的就是出栈的元素
3.peek
3.1如果两个队列都是空，则直接返回false
3.2如果一个队列为空，另一个不为空，则只需要将不为空队列q1中的size-1个元素压到另一个队列q
2中然后最后不为空的队列q1中剩下的元素只需要对它进行peek操作即可
4.empty
两个队列都为空，则栈为空。

1.3绘图分析

1.压栈
在这里插入图片描述
2.出栈

1.4代码实现

public class QueueAchieveStack {Queue<Integer> q1;Queue<Integer> q2;public QueueAchieveStack() {q1 = new LinkedList<>();q2 = new LinkedList<>();}public void push(int x) {//1.两个队列都为空if(empty()) {q1.offer(x);return;}//2.假设只有一个队列为空if(!q2.isEmpty()) {//2.1 q1为空,入队q2q2.offer(x);} else {//2.2 q2为空，入队q1q1.offer(x);}}public int pop() {//1.两个队列都是空if(empty()) {return -1;}//2.只有一个队为空if(!q2.isEmpty()) {//2.1 q1队列为空，那么将q2中size-1的元素入到q1中，最后直接出q2的元素int size1 = q2.size();for (int i = 0; i <size1-1 ; i++) {q1.offer(q2.poll());}return q2.poll();} else {//2.2 q2队列为空，那么将q1中size-1的元素入到q2中，最后直接出q1的元素int size2 = q1.size();for (int i = 0; i <size2-1 ; i++) {q2.offer(q1.poll());}return q1.poll();}}public int top() {//1.两个队列都是空if(empty()) {return -1;}//2.只有一个队为空if(!q2.isEmpty()) {//2.1 q1队列为空，用一个中间变量tmp来存储每一次从q2出队的元素，然后在入q1中int size1 = q2.size();int tmp = -1;for (int i = 0; i <size1 ; i++) {tmp = q2.poll();q1.offer(tmp);}return tmp;} else {//2.2 q2队列为空，用一个中间变量tmp来存储每一次从q1出队的元素，然后在入q2中int size2 = q1.size();int tmp = -1;for (int i = 0; i <size2; i++) {tmp = q1.poll();q2.offer(tmp);}return tmp;}}public boolean empty() {return q1.isEmpty() && q2.isEmpty();}
}

2.用栈实现队

2.1问题描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

2.2思路分析

首先，要实现用栈去模拟一个有入队，出队，peek，判断栈是否为空这些功能的队，我们用一个栈也是不能模拟出队列的，我们用两个栈来模拟这个队列，但是这里和队列实现栈的两个队列不一样，这里的两个栈，我们分别设置一个入队的栈，一个专门出队的栈。相比用队列模拟实现栈，队列模拟实现栈简单一些。
大前提：
1.我们先要创建两个简单栈分别设为s1为入队的栈，q2出队的栈
2.确保这两个栈中必须是空的
接下来分析这些功能怎么实现的：
1.入队
直接将元素压入s1栈中即可
2.出队
2.1如果s2栈中为空，则将s1栈中的元素全部弹出，入栈到s2栈中，然后再弹出s2中栈顶的元素即可
2.2如果s2栈中不为空，则直接弹出s2栈顶的元素
3.peek
3.1如果s2栈中为空，则将s1栈中的元素全部弹出，入栈到s2栈中，然后再peeks2中栈顶的元素即可
3.2如果s2栈中不为空，则直接peeks2栈顶的元素
4.empty
直接判断这两个栈是否为空

1.3绘图分析

1.入队
在这里插入图片描述
2.出队
2.1 s2为空：

2.2 s2不为空：

2.4代码实现

public class StackAchieveQueue {Stack<Integer> s1;Stack<Integer> s2;public StackAchieveQueue() {s1 = new Stack<>();s2 = new Stack<>();}public void push(int x) {//直接将s1当作一个入队的操作s1.push(x);}public int pop() {//判断s2中空不空if(!s2.isEmpty()) {//不空直接弹出元素return s2.pop();} else {//空则将s1中的元素全部都入到s2栈中，再弹出s2的元素int size = s1.size();for(int i=0; i<size; i++) {s2.push(s1.pop());}}return s2.pop();}public int peek() {//判断s2中空不空if(!s2.isEmpty()) {//不空直接返回栈顶元素return s2.peek();} else {//空则将s1中的元素全部都入到s2栈中，再返回s2栈顶的元素int size = s1.size();for(int i=0; i<size; i++) {s2.push(s1.pop());}}return s2.peek();}public boolean empty() {return s1.isEmpty() && s2.isEmpty();}
}