《剑指Offer》面试题七之用两个栈实现队列

2019-11-06 06:35:24

字体：大中小

来源：转载

供稿：网友

题目描述

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数：appendTail() 和deleteHead() ，分别完成在队列的尾部添加结点以及在队列的头部删除结点。

class MyQueue<T>{ PRivate Stack<T> stack1; private Stack<T> stack2; public MyQueue(){ stack1=new Stack<T>(); stack2=new Stack<T>(); }

解题思路

解题思路如下图所示：大致思路

上面的图就是大致的思路：

队列尾部添加元素在stack1中插入元素，如上图中的x5。如果想删除头结点呢？则将stack1中的元素全部“倒入”stack2，这时候stack2中的元素就是stack1中的反序了。那么stack2出栈的就是最先进入栈的元素了。

以上讲的只是一个大致的思路，还有一些小细节要去润色。比如如果这时候stack2中的元素没有全部出栈，这时候又有数据要进栈呢？

第一种思路

思路1 我们将stack2中的元素再次“倒回”，这时候问题就回到初始状况。

思考？我们真的需要做这一次的“倒回”操作吗？答案是否定的，我们看一下下面优化的解法！

第二种思路

在插入元素的时候我们仍然在stack1中插入元素。删除元素头元素的时候我们仍然继续在stack2中删除。如果stack2为空，我们再将stack1中的元素“倒入”stack2。

不知道不有没有理解我的意思？

代码实现

这里的代码是第二种思路的：

class MyQueue<T>{ private Stack<T> stack1; private Stack<T> stack2; public MyQueue(){ stack1=new Stack<T>(); stack2=new Stack<T>(); } public void appentTail(T ele){ //尾部插入 stack1.push(ele); } public T deleteHead() throws Exception{ //头部删除 if(stack2.isEmpty()){ //如果stack2为空 while(!stack1.isEmpty()){ //stack1的元素全部倒入stack2 stack2.push(stack1.pop()); } } if(stack2.isEmpty()) throw new Exception("队列为空"); return stack2.pop(); }}