GuangchaoSun's Blog

用两个stack实现一个queue

发表于  |    |   分类于   |  

题目：

  • 用两个stack实现一个queue
  • push(x) – 把元素x插入queue的尾部
  • pop(x) – 删除queue头部的元素

备注：

只能使用stack的标准操作，push to top，peek/pop from top, is empty等
所有的操作必须是合法的，比如当queue是空的时候不会有pop操作

题目介绍：

这道题目牵涉到两个基础的数据结构，stack和queue。
stack：先进后出(FILO, First In Last Out)，stack可以比喻成一个盒子，我们往盒子里先放a书，再放b书，最后放c书，如果我们想要拿出a书，那么要先拿出c书，再拿出b书，最后才能拿到a书。
queue： 先进先出(FIFO, First In First Out)，就像我们结账排队，先到先结账，queue正好具备和stack相反的性质。

思路总结

  • inbox：总是用来存储新元素。
  • outbox：用来取出元素，以此来满足queue FIFO的性质。

只要有新的元素进来，就把它放进inbox。
如果需要删除元素，直接从outbox里面拿元素出来，但是注意这是在outbox里面有元素的情况下。
如果outbox里面没有元素呢？那就把inbox(if any)里面的元素先放进outbox。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void Queue{
	private Stack<Integer> inbox;
	private Stack<Integer> outbox;
	public Queue(){
		inbox = new Stack<>();
		outbox = new Stack<>();
	}
	public void push(int x){
		inbox.push(x);
	}
	public void pop(int x){
		move();
		return outbox.isEmpty() ? null : outbox.pop();
	}
	public void move(int x){
		if(outbox.isEmpty())
		{
			while (!inbox.isEmpty()) {
				outbox.push(inbox.pop());
			}
		}
	}
}