理論基礎
- python 沒有棧扬蕊，需要用list來實現
232. 用棧實現隊列 - 力扣（LeetCode）
解題思路
用兩個棧，一個入棧一個出棧來實現隊列
class MyQueue:
def __init__(self):
self.stack_in = []
self.stack_out = []
def push(self, x: int) -> None:
self.stack_in.append(x)
def pop(self) -> int:
if self.empty():
return None
if self.stack_out:
return self.stack_out.pop()
"""
#隊列是先進先出丹擎，棧是先進后出尾抑；不管入棧有沒有再push進新元素，出棧里的元素都要先出棧蒂培。
"""
else:
for i in range(len(self.stack_in)):
self.stack_out.append(self.stack_in.pop())
return self.stack_out.pop()
def peek(self) -> int:
ans = self.pop()
self.stack_out.append(ans)
return ans
def empty(self) -> bool:
"""
只要stack_in 或 stack_out有元素再愈，隊列就不為空
"""
return not(self.stack_in or self.stack_out)
225. 用隊列實現棧 - 力扣（LeetCode）
解題思路
用一個隊列實現，利用隊列先進后出的特性护戳，pop出的元素再push進同一個隊列翎冲，留下最后一個元素就是要pop的元素
class MyStack(object):
def __init__(self):
"""
Python普通的Queue或SimpleQueue沒有類似于peek的功能
也無法用索引訪問，在實現top的時候較為困難媳荒。
用list可以抗悍，但是在使用pop(0)的時候時間復雜度為O(n)
因此這里使用雙向隊列，我們保證只執(zhí)行popleft()和append()钳枕，因為deque可以用索引訪問缴渊，可以實現和peek相似的功能
"""
self.que = deque()
def push(self, x):
"""
:type x: int
:rtype: None
"""
self.que.append(x)
def pop(self):
"""
:rtype: int
"""
if self.empty():
return None
for i in range(len(self.que)-1):
self.que.append(self.que.popleft())
return self.que.popleft()
def top(self):
"""
:rtype: int
"""
if self.empty():
return None
return self.que[-1]
def empty(self):
"""
:rtype: bool
"""
return not self.que
- python用雙端隊列方便
