《劍指Offer》面試題七之用兩個棧實現(xiàn)隊列

2019-11-06 06:35:24

字體：大中小

供稿：網(wǎng)友

題目描述

用兩個棧實現(xiàn)一個隊列。隊列的聲明如下，請實現(xiàn)它的兩個函數(shù)：appendTail() 和deleteHead() ，分別完成在隊列的尾部添加結(jié)點以及在隊列的頭部刪除結(jié)點。

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

解題思路

解題思路如下圖所示：大致思路

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

隊列尾部添加元素在stack1中插入元素，如上圖中的x5。如果想刪除頭結(jié)點呢？則將stack1中的元素全部“倒入”stack2，這時候stack2中的元素就是stack1中的反序了。那么stack2出棧的就是最先進入棧的元素了。

以上講的只是一個大致的思路，還有一些小細(xì)節(jié)要去潤色。比如如果這時候stack2中的元素沒有全部出棧，這時候又有數(shù)據(jù)要進棧呢？

第一種思路

思路1 我們將stack2中的元素再次“倒回”，這時候問題就回到初始狀況。

思考？我們真的需要做這一次的“倒回”操作嗎？答案是否定的，我們看一下下面優(yōu)化的解法！

第二種思路

在插入元素的時候我們?nèi)匀辉?code>stack1中插入元素。刪除元素頭元素的時候我們?nèi)匀焕^續(xù)在stack2中刪除。如果stack2為空，我們再將stack1中的元素“倒入”stack2。

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

代碼實現(xiàn)

這里的代碼是第二種思路的：

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(); }}