[Leetcode] Implement Stack using Queues 用隊列實現(xiàn)棧

ivan_qhz 發(fā)布于2019-08-14 12:39 / 2450人閱讀

摘要：雙隊列法復雜度時間空間思路和類似，我們也可以用兩個隊列來模擬棧的操作。當時，我們將數(shù)字進非空的隊列就行了。操作和一樣，區(qū)別在于我們拿到最后一個數(shù)后，還要再把它進另一個隊列中。

雙隊列法 復雜度

時間 O(N) 空間 O(N)

思路

和Implement Queue using Stack類似，我們也可以用兩個隊列來模擬棧的操作。當push時，我們將數(shù)字offer進非空的隊列就行了。當pop時，因為要拿的是隊列最后一個數(shù)，我們先將它前面的數(shù)offer進另一個隊列，然后多帶帶拿出最后一個數(shù)，并且不再offer進另一個隊列，這樣，另一個隊列就少了最后一個數(shù)，而我們也拿到了最后一個數(shù)，而本來的隊列就變成空了，等待下次的pop操作來填滿。top操作和pop一樣，區(qū)別在于我們拿到最后一個數(shù)后，還要再把它offer進另一個隊列中。

代碼

class MyStack {
    
    Queue queue1;
    Queue queue2;
    int size;
    
    public MyStack(){
        this.queue1 = new LinkedList();
        this.queue2 = new LinkedList();
        this.size = 0;
    }
    
    // Push element x onto stack.
    public void push(int x) {
        if(queue1.isEmpty()){
            queue2.offer(x);
        } else {
            queue1.offer(x);
        }
        size++;
    }

    // Removes the element on top of the stack.
    public int pop() {
        if(size == 0){
            return -1;
        }
        int res = 0;
        // 將前面的數(shù)都offer進另一個隊列，然后拿出最后一個數(shù)
        if(queue1.isEmpty()){
            for(int i = 0; i < size - 1; i++){
                queue1.offer(queue2.poll());
            }
            res = queue2.poll();
        } else {
            for(int i = 0; i < size - 1; i++){
                queue2.offer(queue1.poll());
            }
            res = queue1.poll();
        }
        size--;
        return res;
    }

    // Get the top element.
    public int top() {
        if(size == 0){
            return -1;
        }
        // 先執(zhí)行pop
        int top = pop();
        // 然后將pop出來的數(shù)再塞回隊列就行了
        if(queue1.isEmpty()){
            queue2.offer(top);
        } else {
            queue1.offer(top);
        }
        // 注意size也要加1
        size++;
        return top;
    }

    // Return whether the stack is empty.
    public boolean empty() {
        return size == 0;
    }
}