南城区做网站,Wordpress上传万网空间,江苏建设教育培训网,郑州有没有厉害的seo♥♥♥♥♥个人主页♥♥♥♥♥ ♥♥♥♥♥数据结构练习题总结专栏♥♥♥♥♥ ♥♥♥♥♥上一章#xff1a;堆的练习题♥♥♥♥♥ 文章目录 1.用队去实现栈1.1问题描述1.2思路分析1.3绘图分析1.4代码实现2.用栈实现队2.1问题描述2.2思路分析1.3绘图分析2.4代码实现 1.用队去实现… ♥♥♥♥♥个人主页♥♥♥♥♥ ♥♥♥♥♥数据结构练习题总结专栏♥♥♥♥♥ ♥♥♥♥♥上一章堆的练习题♥♥♥♥♥ 文章目录 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.我们先要创建两个简单队列分别设为q1q2 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 {QueueInteger q1;QueueInteger 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 {StackInteger s1;StackInteger 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 i0; isize; 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 i0; isize; i) {s2.push(s1.pop());}}return s2.peek();}public boolean empty() {return s1.isEmpty() s2.isEmpty();}
}
结尾希望大家可以给我点点关注点点赞并且在评论区发表你们的想法和意见我会认真看每一条评论你们的支持就是我的最大鼓励。
