題目

用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列。隊(duì)列的聲明如下，請(qǐng)實(shí)現(xiàn)它的兩個(gè)函數(shù) appendTail 和 deleteHead ，分別完成在隊(duì)列尾部插入整數(shù)和在隊(duì)列頭部刪除整數(shù)的功能。(若隊(duì)列中沒(méi)有元素，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
  • 最多會(huì)對(duì) appendTail、deleteHead 進(jìn)行 10000 次調(diào)用

我的答案

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);        //將插入的元素再?gòu)臈?移回去棧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(); */

  • 補(bǔ)充棧相關(guān)
    		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() 測(cè)試此堆棧是否為空。
    Epeek() 查看此堆棧頂部的對(duì)象，而不從堆棧中刪除它。
    Epop() 刪除此堆棧頂部的對(duì)象，并將該對(duì)象作為此函數(shù)的值返回。
    Epush(E item) 將項(xiàng)目推送到此堆棧的頂部。
    intsearch(Object o) 返回一個(gè)對(duì)象在此堆棧上的基于1的位置。

精彩答案

使用java的同學(xué)請(qǐng)注意，如果你使用Stack的方式來(lái)做這道題，會(huì)造成速度較慢； 原因的話是Stack繼承了Vector接口，而Vector底層是一個(gè)Object[]數(shù)組，那么就要考慮空間擴(kuò)容和移位的問(wèn)題了。 可以使用LinkedList來(lái)做Stack的容器，因?yàn)長(zhǎng)inkedList實(shí)現(xiàn)了Deque接口，所以Stack能做的事LinkedList都能做，其本身結(jié)構(gòu)是個(gè)雙向鏈表，擴(kuò)容消耗少。 但是我的意思不是像100%代碼那樣直接使用一個(gè)LinkedList當(dāng)做隊(duì)列，那確實(shí)是快，但是不符題意。 貼上代碼，這樣的優(yōu)化之后，效率提高了40%，超過(guò)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();    }}