LeetCode 232：用棧實現(xiàn)隊列 Implement Queue using Stacks

cloud 發(fā)布于2019-08-19 10:26 / 2502人閱讀

摘要：題目使用棧實現(xiàn)隊列的下列操作將一個元素放入隊列的尾部。用棧實現(xiàn)隊列，可以用兩個棧完成題解。入隊列時用存入節(jié)點，出隊列時內(nèi)節(jié)點順序出棧壓入中。這類編程語言就壓根不需要用隊列實現(xiàn)棧或用棧實現(xiàn)隊列這種問題，因為棧和隊列本身就必須借助實現(xiàn)。

題目：

使用棧實現(xiàn)隊列的下列操作：

push(x) -- 將一個元素放入隊列的尾部。

pop() -- 從隊列首部移除元素。

peek() -- 返回隊列首部的元素。

empty() -- 返回隊列是否為空。

Implement the following operations of a queue using stacks.

push(x) -- Push element x to the back of queue.

pop() -- Removes the element from in front of queue.

peek() -- Get the front element.

empty() -- Return whether the queue is empty.

示例:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

說明:

你只能使用標準的棧操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊列）來模擬一個棧，只要是標準的棧操作即可。

假設(shè)所有操作都是有效的（例如，一個空的隊列不會調(diào)用 pop 或者 peek 操作）。

Notes:

You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.

Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.

You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

解題思路：

隊列先進后出，棧后進先出。用棧實現(xiàn)隊列，可以用兩個棧完成題解。入隊列時用 stack1 存入節(jié)點，出隊列時 stack1 內(nèi)節(jié)點順序出棧壓入 stack2 中。

例如 1, 2, 3 元素順序入隊列 
即存入棧stack1：[1, 2, 3]

出隊列時順序應(yīng)為：1->2->3
但是棧先進先出，出棧順序為：3->2->1
與出隊列順序不相符

借助另一個棧stack2
stack1內(nèi)的元素順序出棧并壓入stack2
stack1：[1, 2, 3] ---> stack2：[3, 2, 1]
此時stack2出棧順序：1->2->3
與出隊列順序相符

注意：在出隊列時無需著急將 stack1 中的節(jié)點順序壓入 stack2。因為要實現(xiàn)的隊列是先進后出，可以將 stack2 中的節(jié)點全部彈出之后再將 stack1 內(nèi)節(jié)點順序壓入stack2，這樣可以將出棧的時間復(fù)雜度攤還到 O(1)。

Java：

class MyQueue {
    private Stack stack1;
    private Stack stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int peek() {
        //stack1節(jié)點順序彈出并壓入stack2
        if (stack2.isEmpty()) {//條件是: stack2為空,而不是stack1非空, 這樣攤還復(fù)雜度O(1)
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());//stack1彈出節(jié)點并壓入stack2
            }
        }
        return stack2.peek();
    }

    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

Python：

Python語言沒有棧和隊列數(shù)據(jù)結(jié)構(gòu)，只能用數(shù)組 List 或雙端隊列 deque 實現(xiàn)。

這類編程語言就壓根不需要用隊列實現(xiàn)棧或用棧實現(xiàn)隊列這種問題，因為棧和隊列本身就必須借助List、deque實現(xiàn)。

所以這道題在這種語言中這就非常簡單了，可以說是作弊。

class MyQueue:
    def __init__(self):
        self.queue = []

    def push(self, x: int) -> None:
        self.queue.append(x)

    def pop(self) -> int:
        #彈出第一個元素
        return self.queue.pop(0)

    def peek(self) -> int:
        #返回第一個元素
        return self.queue[0]

    def empty(self) -> bool:
        return not self.queue

歡迎關(guān)注微.信公.眾號：愛寫B(tài)ug