LeetCode–用兩個堆疊實作佇列
博客說明
文章所涉及的資料來自互聯網整理和個人總結，意在于個人學習和經驗匯總，如有什么地方侵權，請聯系本人洗掉，謝謝！
介紹
劍指 Offer 09. 用兩個堆疊實作佇列
題目
用兩個堆疊實作一個佇列，佇列的宣告如下，請實作它的兩個函式 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 {
Deque<Integer> stack1;
Deque<Integer> stack2;
public CQueue() {
stack1 = new LinkedList<Integer>();
stack2 = new LinkedList<Integer>();
}
public void appendTail(int value) {
stack1.push(value);
}
public int deleteHead() {
// 如果第二個堆疊為空
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.isEmpty() ? -1 : stack2.pop();
}else {
return stack2.pop();
}
}
}
感謝
Leetcode
以及勤勞的自己
關注公眾號： 歸子莫，獲取更多的資料，還有更長的學習計劃
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/38602.html
標籤：Java
上一篇：LeetCode–重建二叉樹