算法夕拾（05）--用栈实现队列

用栈实现队列

方案1

此方案较为繁琐。

1. 声明两个栈A,B。
2. 队列put：将A中的所有元素压入B中，向A中压入元素，将B中所有元素压回。
3. 队列poll：将A中元素全部压入B，B出栈。

   方案2

4. 申明两个栈A,B。A专职入队，B专职出队。
5. 队列put：向A中压入元素。
6. 队列poll：如B中有，则B出栈。如果B为空，则将A中元素全部压入B，然后B中出栈。

实现（方案2）

package stack2queue;

import stack.Stack;

/**
 * @author jack
 * 2016年11月19日 上午2:20:25
 */
public class Queue {

	private Stack s1; // 专门入栈
	private Stack s2; // 专门出栈

	public Queue(int cap) {
		super();
		this.s1 = new Stack(cap);
		this.s2 = new Stack(cap);
	}

	// 入队
	public boolean put(Object o) {
		return s1.push(o);
	}

	// 出队
	public Object poll() throws Exception {
		if (s2.isEmpty()) {
			stackTrans(s1, s2);
		}
		return s2.pop();
	}

	// 栈之间全拷贝
	private void stackTrans(Stack stack1, Stack stack2) throws Exception {
		while (!stack1.isEmpty()) {
			Object o = stack1.pop();
			stack2.push(o);
		}
	}
}

赏

谢谢你请我吃糖果