[LeetCode] #225. Implement Stack using Queues
題目
Implement a last in first out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal queue (push, top, pop, and empty).
Implement the MyStack class:
void push(int x)Pushes element x to the top of the stack.int pop()Removes the element on the top of the stack and returns it.int top()Returns the element on the top of the stack.boolean empty()Returnstrueif the stack is empty,falseotherwise.
Notes:
- You must use only standard operations of a queue, which means only
push to back,peek/pop from front,size, andis emptyoperations are valid. - Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue), as long as you use only a queue's standard operations.
直覺解
構想：
用 list 模擬 queue。
使用兩個 queue，q1 和 q2。q1 用來存資料，q2 是要取出資料時，用來暫放資料的：要拿出 stack 中的東西時，先把 q1 的資料一個一個搬進 q2 裡，直到 q1 裡只剩下一個東西時，剩下的那個就是要 return 的東西。
python 3 實作：
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.queue1, self.queue2 = [], []
def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
self.queue1.append(x)
return None
def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
while len(self.queue1) > 1:
self.queue2.append(self.queue1.pop(0))
self.queue1, self.queue2 = self.queue2, self.queue1
return self.queue2.pop(0)
def top(self) -> int:
"""
Get the top element.
"""
while len(self.queue1) > 1:
self.queue2.append(self.queue1.pop(0))
top = self.queue1.pop(0)
self.queue2.append(top)
self.queue1, self.queue2 = self.queue2, self.queue1
return top
def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return len(self.queue1) == 0
效能：
Runtime: 24 ms, faster than 94.44% of Python3 online submissions for Implement Stack using Queues.
Memory Usage: 14.2 MB, less than 88.77% of Python3 online submissions for Implement Stack using Queues.
參考 solution Approach #3 (One Queue, push - O(n)O(n), pop O(1)O(1) ) 後，python 3 實作：
構想：只用一個 queue。每 push 一個元素，就把排在該元素前面的東西，一個一個從 queue 拿出來再放回去，這樣資料排列的順序就會跟 stack 一樣了。
class MyStack:
def __init__(self):
self.queue = []
def push(self, x: int) -> None:
self.queue.append(x)
for i in range(len(self.queue) - 1):
self.queue.append(self.queue.pop(0))
return None
def pop(self) -> int:
return self.queue.pop(0)
def top(self) -> int:
print(self.queue)
return self.queue[0]
def empty(self) -> bool:
return len(self.queue) == 0
效能：
Runtime: 32 ms, faster than 52.26% of Python3 online submissions for Implement Stack using Queues.
Memory Usage: 14.4 MB, less than 39.82% of Python3 online submissions for Implement Stack using Queues.
Comments
Post a Comment