原文:
Implement a MyQueue class which implements a queue using two stacks.
译文:
使用两个栈实现一个队列MyQueue。
思路:
建两个栈,stackNewest和stackOldest。要始终保持:stackNewest的栈顶总是存放着最新的元素,stackOldest的栈顶总是存放着最旧的元素。
而且为了尽量减少栈之间的倒腾,只有在必须时(peek或pop)才倒腾栈。
倒腾栈的关键是判断stackOldest内是否有元素?
如果有,什么都不用做,因为可以直接从stackOldest的栈顶取出最老元素。
如果没有,则把stackNewest的所有元素一一倒腾到stackOldest中。
package Stack_Queue;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import CtCILibrary.AssortedMethods;
public class S3_5 {
// 用两个栈实现一个队列:
// Invariant:stackNewest的栈顶总是存放着最新的元素,stackOldest的栈顶总是存放着最旧的元素
static class MyQueue<T> {
Stack<T> stackNewest, stackOldest;
public MyQueue() {
stackNewest = new Stack<T>();
stackOldest = new Stack<T>();
}
// 返回队列大小,即为两个栈的大小之和
public int size() {
return stackNewest.size() + stackOldest.size();
}
// 添加元素到队列,直接添加到stackNewest的栈顶
public void add(T value) {
stackNewest.push(value);
}
// 查看队列的列头元素,则借助shiftStacks函数,使得stackOldest的栈顶总是存放着最旧的元素
public T peek() {
shiftStacks();
return stackOldest.peek();
}
// 移除队列的列头元素,则借助shiftStacks函数,使得stackOldest的栈顶总是存放着最旧的元素
public T remove() {
shiftStacks();
return stackOldest.pop();
}
// 重要的辅助函数,用于保持invariant:stackOldest的栈顶总是存放着最旧的元素
// 具体实现:
// 如果stackOldest非空,则说明队列的最老的元素已经stackOldest的栈顶,如果要取直接取即可,所以直接退出
// 如果stackOldest为空,则需要把stackNewest的元素一一转移到stackOldest内,
// 这样stackOldest的栈顶元素就是stackNewest的栈底元素,恰好就是最老的元素!
private void shiftStacks() {
if( stackOldest.isEmpty() ) { // 如果非空,说明可以直接找到最老元素,退出
while( !stackNewest.isEmpty() ) { // 倒腾栈
stackOldest.push(stackNewest.pop());
}
}
}
}
public static void main(String[] args) {
MyQueue<Integer> my_queue = new MyQueue<Integer>();
// Let's test our code against a "real" queue
Queue<Integer> test_queue = new LinkedList<Integer>();
for (int i = 0; i < 100; i++) {
int choice = AssortedMethods.randomIntInRange(0, 10);
if (choice <= 5) { // enqueue
int element = AssortedMethods.randomIntInRange(1, 10);
test_queue.add(element);
my_queue.add(element);
System.out.println("Enqueued " + element);
} else if (test_queue.size() > 0) {
int top1 = test_queue.remove();
int top2 = my_queue.remove();
if (top1 != top2) { // Check for error
System.out.println("******* FAILURE - DIFFERENT TOPS: " + top1 + ", " + top2);
}
System.out.println("Dequeued " + top1);
}
if (test_queue.size() == my_queue.size()) {
if (test_queue.size() > 0 && test_queue.peek() != my_queue.peek()) {
System.out.println("******* FAILURE - DIFFERENT TOPS: " + test_queue.peek() + ", " + my_queue.peek() + " ******");
}
} else {
System.out.println("******* FAILURE - DIFFERENT SIZES ******");
}
}
}
}
分享到:
相关推荐
Stack_Queue_Stack_源码
常用的C++数据结构算法,包括队列、堆栈、链表...等.以模板类型式实现
c++stack_和_queue用法,很好的介绍了STL中stack和queue的用法,及其使用方法
Data structure: Stack->Queue Example
前端大厂最新面试题-stack_queue
本源码实现了两个类,一个是带有最大值的栈和一个是带有最大值的队列。栈利用了两个C++的stack,队列利用了C++的queue。
A和B两个同学玩简单的纸牌游戏,每人手里有n张牌,两人轮流出牌并依次排列在桌面上,每次出掉手里的第1张牌,出牌后如果发现桌面上有跟刚才打出的牌的数字相同的牌,则把到相同的那张牌结束的全部牌按次序放在自己...
Java_Stack_Queue Java中使用链表的堆栈和队列实现
实现栈,队列,链表的简单操作,其中链表包括单链表,双链表,循环链表。
试用java.util.Stack泛型栈作为父类,用另一个泛型栈对象作为成员变量,模拟实现一个泛型子类Queue,当存储元素的第1个栈的元素超过dump时,再有元素入队列就倒入第2栈。除提供无参构造函数Queue( )外,其它所有队列...
任务描述栈和队列都提供 Push/Pop 两... 输出描述对每组测试数据输出一行, 输出该组数据对应的线性结构,若为栈则输出”Stack”,若为队列则输出“Queue”,若两者都是则输出“Both”,若两者都不是则输出“Error”。
使用两个stack来模拟实现一个队列的功能
NXP 的 LIN 协议栈,之前一直用的 4.5.7 的版本,使用过程中有好几个问题都是手动修复的。最近在官网上看见了 4.6.6 的版本,下载测试了一遍,发现之前手动修复的几个问题都已经 OK 了。
内容包括: 嵌入式TCPIP协议栈应用主机端程序(VC6源码);如何构造嵌入式Linux系统;基于ARM的嵌入式TCPIP协议的实现等
Pro_MERN_Stack_Full_Stack_Web_App_Development_with_Mongo,_Express,_React,_and_Node
Lists_Stack_Queue_PriorityQueue.java
TI公司提供2015年11月最新基于ZigBee无线智能家居开发协议(Z_Stack_Home_1.2.2a.exe) 由于只能上传小于60MB文件,将150MB原文件分割3个部分上传,分别为: Z_Stack_Home_1.2.2a.exe.part1.rar Z_Stack_Home_1.2.2a....
tcpip_stack_v1_2_TCP,IP_TCP_IP_udpmac_UDP_tcp.zip
stack_queue_p2pchat_practice:只是使用Stack和Queue技术的Java实践聊天应用程序