- 思路
- example
- stack: FILO/LIFO, queue: FIFO/LILO
- python中用list实现stack,用deque实现queue
- 单栈实现pop时需要O(n) time
- 双栈: stack_in, stack_out (逆序)
- 复杂度. 时间：均摊O(1), 空间: O(n)
class MyQueue:
def __init__(self):
self.stack_in = []
self.stack_out = []
self.size = 0
def push(self, x: int) -> None:
self.stack_in.append(x)
self.size += 1
def pop(self) -> int:
if not self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
res = self.stack_out.pop()
self.size -= 1
return res
def peek(self) -> int:
if not self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
return self.stack_out[-1]
def empty(self) -> bool:
return self.size == 0
class MyQueue:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, x: int) -> None:
self.stack1.append(x)
def pop(self) -> int: # always valid
if self.stack2 == []:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
def peek(self) -> int: # always valid
if self.stack2 == []:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2[-1]
def empty(self) -> bool:
return self.stack1 == [] and self.stack2 == []
- 思路
- example
- 两个队列实现
- 每次push元素进que2, 然后把que1元素转移到que2,最后再转移到que1.
- que1: 逆序存储元素（逆序是指跟Push进去的顺序相反）
- que2: 过渡用途，最后为空状态。
- 复杂度. 时间：
)
, 空间: O(n)
class MyStack:
def __init__(self):
self.que1 = collections.deque()
self.que2 = collections.deque()
def push(self, x: int) -> None:
self.que２.append(x)
while self.que1:
self.que2.append(self.que1.popleft())
while self.que2:
self.que1.append(self.que2.popleft())
def pop(self) -> int:
return self.que1.popleft()
def top(self) -> int:
return self.que1[0]
def empty(self) -> bool:
return len(self.que1) == 0
- 一个队列实现
- 每次push进去一个元素，马上把之前元素按照popleft()出来再push进队列，这样保证队列是逆序存储了。从而下次popleft()出来的元素必定是最新Push进去的。
class MyStack:
def __init__(self):
self.que = collections.deque()
def push(self, x: int) -> None:
self.que.append(x)
for _ in range(len(self.que)-1):
self.que.append(self.que.popleft())
def pop(self) -> int:
return self.que.popleft()
def top(self) -> int:
return self.que[0]
def empty(self) -> bool:
return len(self.que) == 0
