Python中如何用棧實現隊列

Python中如何用棧實現隊列，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。

用棧實現隊列

題目：

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

• 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（雙端隊列）來模擬一個棧，只要是標準的棧操作即可。

• 假設所有操作都是有效的 （例如，一個空的隊列不會調用 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).

解題思路：

隊列先進后出，棧后進先出。用棧實現隊列，可以用兩個棧完成題解。入隊列時用 stack1 存入節點，出隊列時 stack1 內節點順序出棧壓入 stack2 中。

例如 1, 2, 3 元素順序入隊列 
即存入棧stack1：[1, 2, 3]
出隊列時順序應為：1->2->3
但是棧先進先出，出棧順序為：3->2->1
與出隊列順序不相符
借助另一個棧stack2
stack1內的元素順序出棧并壓入stack2
stack1：[1, 2, 3] ---> stack2：[3, 2, 1]
此時stack2出棧順序：1->2->3
與出隊列順序相符

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

Java：

class MyQueue {
 private Stack<Integer> stack1;
 private Stack<Integer> 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節點順序彈出并壓入stack2
 if (stack2.isEmpty()) {//條件是: stack2為空,而不是stack1非空, 這樣攤還復雜度O(1)
 while (!stack1.isEmpty()) {
 stack2.push(stack1.pop());//stack1彈出節點并壓入stack2
 }
 }
 return stack2.peek();
 }
 public boolean empty() {
 return stack1.isEmpty() && stack2.isEmpty();
 }
}

Python：

Python語言沒有棧和隊列數據結構，只能用數組 List 或雙端隊列 deque 實現。

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

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

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

看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。