Python中如何使用列表或其他数据结构实现栈和队列

作者：小舞很执着 | 2024-07-09 17:04:14

踩

在Python中，可以使用列表（List）数据结构来方便地实现栈（Stack）和队列（Queue）这两种重要的数据结构。栈和队列都是基于先进后出（FILO, First In Last Out）和先进先出（FIFO, First In First Out）原则的数据结构，但它们的应用场景和特性有所不同。

使用列表实现栈

栈是一种后进先出（LIFO, Last In First Out）的数据结构，只允许在栈顶进行添加（push）或删除（pop）元素的操作。使用Python的列表实现栈时，可以利用列表的末尾作为栈顶。

栈的基本操作：

push(x): 向栈顶添加一个元素x。
pop(): 移除栈顶的元素，并返回这个元素。
peek() 或 top(): 返回栈顶的元素，但不移除它。
is_empty(): 检查栈是否为空。

示例代码：

python复制代码

	`class Stack:`
	`def __init__(self):`
	`self.items = []`

	`def push(self, item):`
	`self.items.append(item)`

	`def pop(self):`
	`if not self.is_empty():`
	`return self.items.pop()`
	`else:`
	`return None`

	`def peek(self):`
	`if not self.is_empty():`
	`return self.items[-1]`
	`else:`
	`return None`

	`def is_empty(self):`
	`return len(self.items) == 0`

	`# 使用示例`
	`stack = Stack()`
	`stack.push(1)`
	`stack.push(2)`
	`print(stack.peek()) # 输出: 2`
	`print(stack.pop()) # 输出: 2`
	`print(stack.is_empty()) # 输出: False`

使用列表实现队列

队列是一种先进先出（FIFO）的数据结构，只允许在队列的一端进行添加（enqueue）操作，在另一端进行删除（dequeue）操作。使用Python的列表实现队列时，可以将列表的开头视为队列的前端，末尾视为队列的后端。然而，由于列表在头部插入和删除元素的时间复杂度为O(n)，因此这种实现方式效率并不高。更高效的实现方式是使用collections模块中的deque（双端队列）。

队列的基本操作：

enqueue(x): 向队列的尾部添加一个元素x。
dequeue(): 从队列的头部移除一个元素，并返回这个元素。
is_empty(): 检查队列是否为空。
size(): 返回队列中的元素个数。

使用列表实现的示例（不推荐，因为效率低）：

python复制代码

	`class Queue:`
	`def __init__(self):`
	`self.items = []`

	`def enqueue(self, item):`
	`self.items.append(item)`

	`def dequeue(self):`
	`if not self.is_empty():`
	`return self.items.pop(0)`
	`else:`
	`return None`

	`def is_empty(self):`
	`return len(self.items) == 0`

	`def size(self):`
	`return len(self.items)`

	`# 使用示例`
	`queue = Queue()`
	`queue.enqueue(1)`
	`queue.enqueue(2)`
	`print(queue.dequeue()) # 输出: 1`
	`print(queue.is_empty()) # 输出: False`

更高效的实现（使用deque）：

python复制代码

	`from collections import deque`

	`class Queue:`
	`def __init__(self):`
	`self.items = deque()`

	`def enqueue(self, item):`
	`self.items.append(item)`

	`def dequeue(self):`
	`if not self.is_empty():`
	`return self.items.popleft()`
	`else:`
	`return None`

	`def is_empty(self):`
	`return len(self.items) == 0`

	`def size(self):`
	`return len(self.items)`

	`# 使用示例`
	`queue = Queue()`
	`queue.enqueue(1)`
	`queue.enqueue(2)`
	`print(queue.dequeue()) # 输出: 1`
	`print(queue.is_empty()) # 输出: False`

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小舞很执着/article/detail/803076