1.問題描述

用兩個棧實現一個隊列。隊列的聲明如下，請實現它的兩個函數 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]

2.解題思路

成員變量：維護兩個棧 stack1 和 stack2，其中 stack1 支持插入操作，stack2 支持刪除操作
構造方法：初始化 stack1 和 stack2 為空
插入元素：插入元素對應方法 appendTail，對應stack1 直接插入元素
刪除元素：刪除元素對應方法 deleteHead

• 如果 stack2 為空，則將 stack1 里的所有元素彈出插入到 stack2 里
• 如果 stack2 仍為空，則返回 -1，否則從 stack2 彈出一個元素并返回

時間復雜度：對于插入和刪除操作，時間復雜度均為 O(1)。插入不多說，對于刪除操作，雖然看起來是 O(n)的時間復雜度，但是仔細考慮下每個元素只會「至多被插入和彈出 stack2 一次」，因此均攤下來每個元素被刪除的時間復雜度仍為 O(1)。

空間復雜度：O(n)。需要使用兩個棧存儲已有的元素。

class CQueue {private Stack<Integer> stack1;private Stack<Integer> stack2;public CQueue() {stack1 = new Stack<Integer>();stack2 = new Stack<Integer>();}public void appendTail(int value) {stack1.push(value);}public int deleteHead() {if (stack2.isEmpty()){while (!stack1.isEmpty()){stack2.push(stack1.pop());}}if (stack2.isEmpty()){return -1;}else{int item = stack2.pop();return item;}}
}/*** Your CQueue object will be instantiated and called as such:* CQueue obj = new CQueue();* obj.appendTail(value);* int param_2 = obj.deleteHead();*/