問題描述
用兩個堆疊實作一個佇列，佇列的宣告如下，請實作它的兩個函式 appendTail 和 deleteHead ，分別完成在佇列尾部插入整數和在佇列頭部洗掉整數的功能，(若佇列中沒有元素，deleteHead 操作回傳 -1 )
示例 1：
輸入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
輸出：[null,null,3,-1]
示例 2：
輸入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
輸出：[null,-1,null,null,5,2]
提示：
1 <= values <= 10000
最多會對 appendTail、deleteHead 進行 10000 次呼叫
解題思路
維護兩個堆疊，第一個堆疊支持插入操作，第二個堆疊支持洗掉操作，
根據堆疊先進后出的特性，我們每次往第一個堆疊里插入元素后(插入到堆疊頂)，第一個堆疊的堆疊底就是最先插入并且需要最先洗掉的元素，而堆疊頂就是最后插入且需要最后洗掉的元素，為了維護佇列先進先出的特性，我們引入第二個堆疊，用第二個堆疊維護待洗掉的元素，在執行洗掉操作的時候我們首先看下第二個堆疊是否為空，如果為空，我們將第一個堆疊里的元素一個個彈出插入到第二個堆疊里，這樣第二個堆疊里元素的順序就是待洗掉的元素的順序，要執行洗掉操作的時候我們直接彈出第二個堆疊的元素回傳即可，
實作代碼
class CQueue {
//維護兩個成員變數s1和s2,其中s1主要支持插入元素，s2支持洗掉元素
Stack<Integer> s1;
Stack<Integer> s2;
public CQueue() { //在構造方法中創建物件
s1=new Stack<>();
s2=new Stack<>();
}
//隊尾入隊時直接將元素壓入堆疊s1中
public void appendTail(int value) {
s1.push(value);
}
//洗掉元素時，如果s2中存在元素，那么直接把s2堆疊頂元素洗掉即可，
//如果s2為空，那么需要把s1中的全部元素都出堆疊壓入到s2堆疊中，此時
//s2堆疊中各個元素出堆疊的順序其實就是模擬佇列中出隊的順序，
//當然，可能s1本身也為空，所以s2也可能為空，如果為空，回傳-1，否則彈出s2堆疊頂元素
public int deleteHead() {
if(!s2.empty()){
return s2.pop();
}else{
while(!s1.empty()){
s2.push(s1.pop());
}
}
if(s2.empty()){
return -1;
}else{
return s2.pop();
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/260032.html
標籤：java
上一篇：Random類,JavaSE