題目

用兩個棧實現一個隊列。隊列的聲明如下，請實現它的兩個函數 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 {    Stack stk1,stk2;    int  size;    public CQueue() {        //初始化         stk1 = new Stack();         stk2 = new Stack();         size =0;    }    public void appendTail(int value) {        //插入前先將棧1的全部移到棧2里面        while(!stk1.isEmpty()){            stk2.push(stk1.pop());        }        //插入元素放入到棧1        stk1.push(value);        //將插入的元素再從棧2移回去棧1        while(!stk2.isEmpty()){            stk1.push(stk2.pop());        }        size ++;    }    public int deleteHead() {        //直接彈出棧1        if(size==0) return -1;          int res = stk1.pop();        size --;        return res;    }}/** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */

  • 補充棧相關
    		Modifier and TypeMethod and Description
    booleanempty() Tests if this stack is empty.
    Epeek() Looks at the object at the top of this stack without removing it from the stack.
    Epop() Removes the object at the top of this stack and returns that object as the value of this function.
    Epush(E item) Pushes an item onto the top of this stack.
    intsearch(Object o) Returns the 1-based position where an object is on this stack.
    Modifier and TypeMethod and Description
    booleanempty() 測試此堆棧是否為空。
    Epeek() 查看此堆棧頂部的對象，而不從堆棧中刪除它。
    Epop() 刪除此堆棧頂部的對象，并將該對象作為此函數的值返回。
    Epush(E item) 將項目推送到此堆棧的頂部。
    intsearch(Object o) 返回一個對象在此堆棧上的基于1的位置。

精彩答案

使用java的同學請注意，如果你使用Stack的方式來做這道題，會造成速度較慢； 原因的話是Stack繼承了Vector接口，而Vector底層是一個Object[]數組，那么就要考慮空間擴容和移位的問題了。 可以使用LinkedList來做Stack的容器，因為LinkedList實現了Deque接口，所以Stack能做的事LinkedList都能做，其本身結構是個雙向鏈表，擴容消耗少。 但是我的意思不是像100%代碼那樣直接使用一個LinkedList當做隊列，那確實是快，但是不符題意。 貼上代碼，這樣的優化之后，效率提高了40%，超過97%。
class CQueue {        LinkedList stack1;    LinkedList stack2;    public CQueue() {        stack1 = new LinkedList<>();        stack2 = new LinkedList<>();    }    public void appendTail(int value) {        stack1.add(value);    }    public int deleteHead() {        if (stack2.isEmpty()) {            if (stack1.isEmpty()) return -1;            while (!stack1.isEmpty()) {                stack2.add(stack1.pop());            }            return stack2.pop();        } else return stack2.pop();    }}