当前位置:首页 > 笔记 > 正文内容

编写一个类,用两个栈实现队列,支持队列的基本操作(add,poll, peek)

jsc4年前 (2021-12-01)笔记2105

由两个组成的队列

【题目】

编写一个类,用两个栈实现队列,支持队列的基本操作(add,poll, peek)。

【解答】

栈的特点是先进后出,而队列的特点是先进先出。我们用两个栈正好能把顺序反过来实现类似队列的操作。

具体实现上是一个栈作为压入栈,在压入数据时只往这个栈中压入,记为 stack Push;另一个栈只作为弹出栈,在弹出数据时只从这个栈弹出,记为 stackpop.

因为数据压入栈的时候,顺序是先进后出的。那么只要把stack Push的数据再压入 stack Pop中,顺序就变回来了。例如,将1~5依次压入 stack Push,那么从 stack Push的栈顶到栈底为5~1,此时依次再将5~1倒入 stackpop,那么从 stackpop的栈顶到栈底就变成了1~5。再从 stack Pop弹出时,顺序就像队列一样,如图1-3所示。

111.jpeg

听起来虽然简单,实际上必须做到以下两点。

1.如果 stack Push要往 Estack Pop中压入数据,那么必须一次性把stackPush中的数据全部压入。

2.如果 stack Pop.不为空, stack Push绝对不能向 stack Pop中压入数据。

违反了以上两点都会发生错误

违反1的情况举例:1~5依次压入 stack Push, stack Push的栈顶到栈底为5~1,从 stack Push压入 stack Pop时,只将5和4压入了tack Pop, stack Push还剩下1、2、3没有压入。此时如果用户想进行弹出操作,那么4将最先弹出,与预想的队列顺序就不一致。

违反2的情况举例:1~5依次压入 stack Push, stack Push将所有的数据压入了 stack Pop,此时从 stack Pop的栈顶到栈底就变成了1~5此时又有6~10依次压入 stack Push, stackpop不为空, stack Push不能向其中压入数据。如果违反2压入了 stackpop,从 stack Pop的栈顶到栈底就变成了6~10、1~5。那么此时如果用户想进行弹出操作6将最先弹出,与预想的队列顺序就不一致。

上面介绍了压入数据的注意事项。那么这个压入数据的操作在何时发生呢?

这个选择的时机可以有很多,调用add、poll和peek三种方法中的任何一种时发生“压”入数据的行为都是可以的。只要满足如上提到的两点,就不会出错。

本书的实现是在调用poll和peek方法时进行压入数据的过程。

具体实现请参看如下的 Twostacksqueue类:

import java.util.Stack;


public class Twostacksqueue {
	public Stack<Integer> stackPush;
	public Stack<Integer> stackPop;
	public Twostacksqueue(){
		this.stackPush=new Stack<Integer>();
		this.stackPop=new Stack<Integer>();
	}
	//add
	public void add(int pushInt){
		stackPush.push(pushInt);
	}

	//poll
	public int poll(){
		if(stackPop.empty()&&stackPush.empty()){
			throw new RuntimeException("the stack is empty!");
		}else if(stackPop.empty()){
			while(!stackPush.empty()){
				stackPop.push(stackPush.pop());
			}
		}
		return stackPop.pop();

	}

	//peek
	public int peek(){
		if(stackPop.empty()&&stackPush.empty()){
			throw new RuntimeException("the stack is empty!");
		}else if(stackPop.empty()){
			while(!stackPop.empty()){
				stackPop.push(stackPush.pop());
			}
		}
		return stackPop.peek();
	}
}


扫描二维码推送至手机访问。

版权声明:本文由微小站发布,如需转载请注明出处。

本文链接:https://jsc0.com/post/200.html

标签:
分享给朋友:

“编写一个类,用两个栈实现队列,支持队列的基本操作(add,poll, peek)” 的相关文章

equals和==区别

对于==,如果作用于基本数据类型的变量,则直接比较其存储的 “值”是否相等;    如果作用于引用类型的变量,则比较的是所指向的对象的地址对于equals方法,注意:equals方法不能作用于基本数据类型的变量    如果没有对equals方法进行重写,则比较的是引用类型的变量所指向的对象的地址; ...

viewpager、listview、gridview、scrollview去除蓝色阴影

xml:   android:overScrollMode="never"java:    view.setOverScrollMode(ScrollView.OVER_SCROLL_NEVER);...

Notification 8.0 关闭声音震动

NotificationChannel notificationChannel = new NotificationChannel                    (NOTIFICATION_C...

更新Android Studio的系統找不到指定的路径错误的解决方法

Android Studio的安装和设定之后如果更换了电脑,想再次更新(检查更新)的时候也许会遇到这个问题:安装未成功完成。有关详细信息,请参阅IDE日志这是因为教室里的电脑,使用者的名称,和你家里或是别的地方的使用者名称不同所导致因为在更新的过程中,Android Studio会先将更新档放到Te...

ERROR: Failed to create toolchain.

哔哩哔哩视频编译报错build on Darwin x86_64ANDROID_NDK=/Users/sampeng/export/android-sdk-macosx/ndk-bundleIJK_NDK_REL=15.0.4075724NDKr15.0.4075724 detectedHOST_O...