`
xitonga
  • 浏览: 579621 次
文章分类
社区版块
存档分类
最新评论

Stack_Queue 两个栈实现一个队列 @CareerCup

阅读更多

原文:

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 ******");
			}
		}
	}
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics