在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 |
![[Spring] Spring Web MVC基础理论](https://i-blog.csdnimg.cn/direct/f0c5b1e3dbe044769fc9fc5c38accbae.jpeg#pic_center)
