【LeetCode題解】232_用棧實現佇列（Implement-Queue-using-Stacks）

LeetCode Java · 發表 2018-12-01 23:58:00

摘要：目錄解法一：在一個棧中維持所有元素的出隊順序解法二：一個棧入，一個棧出更多 LeetCode 題解筆記可以訪問我的 github 。描述使用棧實現佇列的下列操作： push(x) -- 將一個元素放入佇列的尾部。 po...

解法一：在一個棧中維持所有元素的出隊順序
解法二：一個棧入，一個棧出

更多 LeetCode 題解筆記可以訪問我的 ofollow,noindex" target="_blank">github 。

描述

使用棧實現佇列的下列操作：

push(x) -- 將一個元素放入佇列的尾部。
pop() -- 從佇列首部移除元素。
peek() -- 返回佇列首部的元素。
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（雙端佇列）來模擬一個棧，只要是標準的棧操作即可。
假設所有操作都是有效的（例如，一個空的佇列不會呼叫 pop 或者 peek 操作）。

解法一：在一個棧中維持所有元素的出隊順序

思路

佇列是一種先入先出（first in first out, FIFO）的資料結構，而棧是一種後入先出（last in first out, LIFO）的資料結構。因此，如果要使用棧來達到佇列的效果，即用有後入先出性質的資料結構來實現先入先出的效果，需要借用兩個棧來改變元素的出隊順序。當然，借用兩個棧來實現佇列也有不同的實現方式，這一節介紹第一種實現方式，在下一小節介紹第二種方式。

第一種方式是 在一個棧中維持所有元素的出隊順序 ，即所有的元素在入隊操作完成後只會儲存在一個棧中，且其出棧的順序和出隊的順序是一致的。下面對入隊、出隊等操作的底層實現分別進行講解。

入隊（push）

為了實現出棧順序和出隊順序是一致的， 入棧時必須將新的元素壓入棧底 。為了實現這種效果，在入隊時，首先將棧1（假設棧1中儲存所有的元素）中所有的元素彈出並壓入棧2中，接著將新的元素壓入棧1中，最後再將棧2中的所有彈出並壓入棧1中。詳細的步驟如圖1所示。

圖1：將一個元素入隊

程式碼（Java）實現如下。

public void push(int x) {
// 將棧1中的所有元素彈出並壓入棧2中
while (!s1.isEmpty()) {
s2.push(s1.pop());
}

// 將新的元素壓入棧1
s1.push(x);

// 將棧2的所有元素彈出並壓入棧1
while (!s2.isEmpty()) {
s1.push(s2.pop());
}
}

複雜度分析如下：

時間複雜度： \(O(n)\) ，其中 \(n\) 表示入隊時佇列元素的數目，即棧1中元素的數目。入隊時，棧1中的元素需要進行出棧和入棧兩次，需要 \(4n\) 次操作，再加上新的元素的一次入棧操作，總的操作次數為 \(4n + 1\) 次。由於棧的入棧和出棧的時間複雜度是 \(O(1)\) 的，因此，入隊的時間複雜度是 \(O(n)\) 的
空間複雜度： \(O(n)\)

出隊（pop）

出隊操作比較簡單，由於棧1中元素的出棧順序和佇列的出隊順序一致，因此，只需要彈出棧頂元素即可完成出隊操作。

public int pop() {
if (s1.isEmpty()) {
throw new IllegalArgumentException("[ERROR] The queue is empty!");
}

return s1.pop();
}

複雜度分析如下：

時間複雜度： \(O(1)\)
空間複雜度： \(O(1)\)

檢視隊首（peek）

與出隊操作類似，只需要檢視棧1棧頂的元素即可完成檢視隊首的操作。

public int peek() {
if (s1.isEmpty()) {
throw new IllegalArgumentException("[ERROR] The queue is empty!");
}

return s1.peek();
}

複雜度分析如下：

時間複雜度： \(O(1)\)
空間複雜度： \(O(1)\)

是否為空（empty）

由於棧1中儲存佇列的所有元素，因此只需要判斷棧1是否為空即可知道佇列是否為空。

public boolean empty() {
return s1.isEmpty();
}

複雜度分析如下：

時間複雜度： \(O(1)\)
空間複雜度： \(O(1)\)

Java 實現

class MyQueue {
private Stack<Integer> s1;
private Stack<Integer> s2;

/** Initialize your data structure here. */
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}

/** Push element x to the back of queue. */
public void push(int x) {
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
s1.push(x);
while (!s2.isEmpty()) {
s1.push(s2.pop());
}
}

/** Removes the element from in front of queue and returns that element. */
public int pop() {
if (s1.isEmpty()) {
throw new IllegalArgumentException("[ERROR] The queue is empty!");
}

return s1.pop();
}

/** Get the front element. */
public int peek() {
if (s1.isEmpty()) {
throw new IllegalArgumentException("[ERROR] The queue is empty!");
}

return s1.peek();
}

/** Returns whether the queue is empty. */
public boolean empty() {
return s1.isEmpty();
}
}

Python 實現

class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self._s1, self._s2 = [], []

def push(self, x):
"""
Push element x to the back of queue.
:type x: int
:rtype: void
"""
while self._s1:
self._s2.append(self._s1.pop())
self._s1.append(x)
while self._s2:
self._s1.append(self._s2.pop())

def pop(self):
"""
Removes the element from in front of queue and returns that element.
:rtype: int
"""
return self._s1.pop()

def peek(self):
"""
Get the front element.
:rtype: int
"""
return self._s1[-1]

def empty(self):
"""
Returns whether the queue is empty.
:rtype: bool
"""
return not self._s1

解法二：一個棧入，一個棧出

思路

解法二的實現方式與解法一有點不同，按照功能的不同，解法二將 兩個棧一個用於入隊，一個用於出隊 。假設棧 inStack 用於實現入隊操作，棧 outStack 用於實現出隊操作。下面對入隊、出隊等操作的底層實現分別進行講解。

入隊（push）

入隊操作比較簡單，直接將新的元素壓入棧 inStack 中，同時，對於第一個進入棧中的元素，我們用一個變數 front 儲存起來，用於表示棧 inStack 這個佇列的隊首。

/** Push element x to the back of queue. */
public void push(int x) {
if (inStack.empty()) {
front = x;
}
inStack.push(x);
}

複雜度分析如下：

時間複雜度： \(O(1)\)
空間複雜度： \(O(n)\) ，需要額外的空間用於儲存佇列元素

出隊（pop）

在入隊時，由於先入的元素處於輸入棧 inStack 的棧底，因此，為了能夠彈出棧底的元素實現出隊操作，需要將輸入棧 inStack 中的元素彈出並壓入到輸出棧 outStack 中。此時，輸出棧 outStack 中元素的出棧順序和佇列的出隊順序是一致的。只要輸出棧 outStack 中還有元素，每次執行出隊操作只需要將棧 outStack 的棧頂元素彈出即可。當輸出棧 outStack 為空時，執行出隊操作則需要先將輸入棧 inStack 中的元素彈出並壓入輸出棧。詳細的步驟如圖2所示。

圖2：將一個元素出隊

程式碼（Java）實現如下。

/** Removes the element from in front of queue and returns that element. */
public int pop() {
if (empty()) {
throw new IllegalArgumentException("[ERROR] The queue is empty!");
}

if (outStack.isEmpty()) {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
return outStack.pop();
}

複雜度分析如下：

時間複雜度：均攤時間複雜度為 \(O(1)\) ，最壞情況下，時間複雜度為 \(O(n)\) ，更為詳細的均攤複雜度分析可以檢視官網的文章
空間複雜度： \(O(1)\)

檢視隊首（peek）

與出隊操作類似，當輸出棧 outStack 不為空時，只需要返回輸出棧 outStack 的棧頂元素即可。不同的是，由於我們用變數 front 儲存了輸入棧最先進入的元素，因此，當輸出棧 outStack 為空時，不需要再將輸入棧 inStack 的元素彈出並壓入到輸出棧 outStack 中便可以得到當前隊首的元素。

/** Get the front element. */
public int peek() {
if (empty()) {
throw new IllegalArgumentException("[ERROR] The queue is empty!");
}

if (!outStack.isEmpty()) {
return outStack.peek();
} else {
return front;
}
}

複雜度分析如下：

時間複雜度： \(O(1)\) ，藉助於變數 front ，可以使得 peek 操作在任意情況下都是 \(O(1)\) 的時間複雜度
空間複雜度： \(O(1)\)

是否為空（empty）

由於兩個都有可以存在元素，因此，要判斷佇列是否為空，需要同時判斷兩個棧。

/** Returns whether the queue is empty. */
public boolean empty() {
return inStack.isEmpty() && outStack.isEmpty();
}

複雜度分析如下：

時間複雜度： \(O(1)\)
空間複雜度： \(O(1)\)

Java 實現

class MyQueue {
/**
* The stack used to implement enqueue functionality
*/
private Stack<Integer> inStack;
/**
* The stack used to implement dequeue functionality
*/
private Stack<Integer> outStack;
/**
* The front element in the stack `inStack` 's queue
*/
private int front;

/** Initialize your data structure here. */
public MyQueue2() {
inStack = new Stack<>();
outStack = new Stack<>();
}

/** Push element x to the back of queue. */
public void push(int x) {
if (inStack.empty()) {
front = x;
}
inStack.push(x);
}

/** Removes the element from in front of queue and returns that element. */
public int pop() {
if (empty()) {
throw new IllegalArgumentException("[ERROR] The queue is empty!");
}

if (outStack.isEmpty()) {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
return outStack.pop();
}

/** Get the front element. */
public int peek() {
if (empty()) {
throw new IllegalArgumentException("[ERROR] The queue is empty!");
}

if (!outStack.isEmpty()) {
return outStack.peek();
} else {
return front;
}
}

/** Returns whether the queue is empty. */
public boolean empty() {
return inStack.isEmpty() && outStack.isEmpty();
}
}

Python 實現

class MyQueue:

def __init__(self):
"""
Initialize your data structure here.
"""
self._in_stack, self._out_stack, self._front = [], [], None

def push(self, x):
"""
Push element x to the back of queue.
:type x: int
:rtype: void
"""
if not self._in_stack:
self._front = x
self._in_stack.append(x)

def pop(self):
"""
Removes the element from in front of queue and returns that element.
:rtype: int
"""
if self.empty():
raise Exception("[ERROR] The queue is empty!")

if not self._out_stack:
while self._in_stack:
self._out_stack.append(self._in_stack.pop())
return self._out_stack.pop()

def peek(self):
"""
Get the front element.
:rtype: int
"""
if self.empty():
raise Exception("[ERROR] The queue is empty!")

if not self._out_stack:
return self._front
else:
return self._out_stack[-1]


def empty(self):
"""
Returns whether the queue is empty.
:rtype: bool
"""
return not self._in_stack and not self._out_stack

【LeetCode題解】232_用棧實現佇列（Implement-Queue-using-Stacks）

描述

示例:

說明:

解法一：在一個棧中維持所有元素的出隊順序

思路

入隊（push）

出隊（pop）

檢視隊首（peek）

是否為空（empty）

Java 實現

Python 實現

解法二：一個棧入，一個棧出

思路

入隊（push）

出隊（pop）

檢視隊首（peek）

是否為空（empty）

Java 實現

Python 實現

您可能也會喜歡…