代码随想录训练营第十天|栈和队列|232|225
栈(Stack)和队列(Queue)是两种基本的数据结构,它们的思想在日常生活中的许多场景中都有体现。
栈(Stack)的思想应用:
- 书堆:书桌上的书堆是栈的一个直观例子。你总是放下(push)一本新书在最上面,当需要一本书时,你会从顶部取走(pop)书,这是一个后进先出(LIFO)的过程。
- 浏览器的后退按钮:浏览过的网页地址被存储在一个栈中。每当你访问一个新网页,它就被“压入”这个栈。点击后退按钮时,最近访问的网页被“弹出”,显示前一个网页。
- 撤销(Undo)功能:在文本编辑器中,每次编辑操作(如输入、删除)都被存储在一个栈中。当你执行撤销操作时,最近的编辑动作被撤销,这也是一个后进先出的过程。
队列(Queue)的思想应用:
- 排队购票:在电影院或音乐会购票处排队时,第一个排队的人将是第一个买到票并离开的。这是一个先进先出(FIFO)的过程。
- 打印任务队列:在办公室,多个人可能同时向同一台打印机发送打印任务。这些任务按照它们到达打印机的顺序被处理,形成了一个队列。
- 呼叫中心:在客服中心,来电被放入队列中,客服人员按照来电的顺序接听电话。这确保了第一个呼叫的客户将是第一个被服务的。
232.用栈实现队列
得用两个栈,一个入队列一个出队列
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() 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: return not (self.stack_in or self.stack_out)
初始状态
stack_in = []
stack_out = []
执行push(x)
stack_in = [x]
(将x
压入stack_in
)stack_out = []
执行push(y)
stack_in = [x, y]
(y
入栈到stack_in
,放在x
之上)stack_out = []
执行peek()
- 首先检查
stack_out
是否为空,是的话,将stack_in
的元素逆序转移到stack_out
中。转移后,stack_in
为空,而stack_out
按照stack_in
的逆序存放之前的元素。转移前:stack_in = []stack_out = [y, x](x是队列前端元素) - 然后从
stack_out
中pop
出栈顶元素(此时为x
),这是peek
操作想要查看的队列前端元素。 - 由于是
peek
操作,需要将弹出的元素(x
)再次放回stack_out
,以保持队列状态不变。操作后:stack_in = []stack_out = [x, y](x再次被放回)
执行pop()
- 如果
stack_out
非空(此时是[x, y]
),直接从stack_out
中pop
出栈顶元素(此时为x
),即为执行pop
操作移除的队列前端元素。操作后:stack_in = []stack_out = [y](x被移除)
执行empty()
- 检查
stack_in
和stack_out
是否都为空。在此步骤中,stack_in
确实为空,但stack_out
包含元素[y]
,因此队列不为空。最终状态:stack_in = []stack_out = [y]
总结
通过这系列操作,我们可以看到stack_in
主要用于处理新元素的入队操作,而stack_out
主要用于出队操作。通过在pop
和peek
操作中适当地将元素从一个栈转移到另一个栈,这种设计成功地用两个栈模拟了队列的先进先出(FIFO)特性。
225. 用队列实现栈
from collections import deque class MyStack: def __init__(self): self.stack = deque() def push(self, x: int) -> None: # 使用append方法向deque的末尾添加元素,模拟栈的push操作 self.stack.append(x) def pop(self) -> int: # 如果栈不为空,则使用pop方法移除并返回deque的最后一个元素,模拟栈的pop操作 if not self.empty(): return self.stack.pop() return None def top(self) -> int: # 如果栈不为空,返回deque的最后一个元素,但不移除它,模拟栈的top操作 if not self.empty(): return self.stack[-1] return None def empty(self) -> bool: # 如果deque为空,则返回True,表示栈为空;否则返回False return not self.stack
deque
(双端队列)是Python中collections
模块提供的一种数据结构。它支持从两端快速添加(push)和移除(pop)元素,因此非常适合用作栈(Stack)和队列(Queue)。下面详细介绍deque
的一些常用操作和用法。
deque用法
创建deque
首先,需要从collections
模块中导入deque
:
from collections import deque
然后,可以创建一个空的deque
,或者使用一个可迭代对象(如列表)初始化deque
:
d = deque() # 创建一个空的deque d = deque([1, 2, 3]) # 使用列表初始化deque
向deque
添加元素
- append: 在deque的右端添加一个元素。
- appendleft: 在deque的左端添加一个元素。
从deque
中移除元素
- pop: 移除并返回deque的右端元素。
- popleft: 移除并返回deque的左端元素。
访问元素
直接使用索引访问deque
中的元素:
first_element = d[0] # 访问第一个元素 last_element = d[-1] # 访问最后一个元素
deque
的其他常用操作
- extend: 在deque的右端一次性添加多个元素。
- extendleft: 在deque的左端一次性添加多个元素。注意,添加的序列元素将会反序出现在deque的左端。
- rotate: 向右旋转deque中的元素。如果参数为负数,则向左旋转。
- clear: 清空deque中的所有元素。
- maxlen: 创建deque时可以指定一个最大长度。一旦达到这个长度,新添加的元素会导致相反端的元素被移除。
总结
deque
是一个非常灵活的数据结构,适用于需要从两端操作数据的场景。由于deque
支持O(1)时间复杂度的元素添加和移除操作,它比使用Python列表实现栈或队列更加高效。