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

Stack_Queue 两个栈实现一个队列 @CareerCup,布布扣,bubuko.com

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

原文：http://blog.csdn.net/fightforyourdream/article/details/20271229