数据结构 ~ 栈、队列

**数据结构之栈与队列**

在计算机科学中，数据结构是指组织和存储数据的方式。栈和队列是两种常见的线性数据结构，它们都有自己的特点和应用场景。

### 栈栈是一种后进先出的数据结构（LIFO），它遵循这样的规则：最后添加的元素将首先被移除。栈通常使用一个数组或链表来实现。

#### 栈的基本操作1. **push**: 将元素添加到栈顶。
2. **pop**: 移除栈顶元素。
3. **peek**: 查看栈顶元素（但不移除）。
4. **isEmpty**: 检查栈是否为空。

#### 栈的实现

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

 def push(self, item):
 """添加元素到栈顶"""
 self.items.append(item)

 def pop(self):
 """移除栈顶元素"""
 if not self.isEmpty():
 return self.items.pop()
 else:
 raise IndexError("Stack is empty")

 def peek(self):
 """查看栈顶元素（但不移除）"""
 if not self.isEmpty():
 return self.items[-1]
 else:
 raise IndexError("Stack is empty")

 def isEmpty(self):
 """检查栈是否为空"""
 return len(self.items) ==0# 示例使用stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop()) # 输出:2print(stack.peek()) # 输出:1print(stack.isEmpty()) # 输出: False

### 队列队列是一种先进先出的数据结构（FIFO），它遵循这样的规则：最先添加的元素将首先被移除。队列通常使用一个数组或链表来实现。

#### 队列的基本操作1. **enqueue**: 将元素添加到队尾。
2. **dequeue**: 移除队头元素。
3. **peek**: 查看队头元素（但不移除）。
4. **isEmpty**: 检查队列是否为空。

#### 队列的实现

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

 def enqueue(self, item):
 """添加元素到队尾"""
 self.items.append(item)

 def dequeue(self):
 """移除队头元素"""
 if not self.isEmpty():
 return self.items.pop(0)
 else:
 raise IndexError("Queue is empty")

 def peek(self):
 """查看队头元素（但不移除）"""
 if not self.isEmpty():
 return self.items[0]
 else:
 raise IndexError("Queue is empty")

 def isEmpty(self):
 """检查队列是否为空"""
 return len(self.items) ==0# 示例使用queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
print(queue.dequeue()) # 输出:1print(queue.peek()) # 输出:2print(queue.isEmpty()) # 输出: False

### 总结栈和队列是两种常见的线性数据结构，它们都有自己的特点和应用场景。栈遵循后进先出（LIFO）的规则，而队列遵循先进先出的规则。通过理解这些基本概念和实现，开发者可以更好地设计和使用这些数据结构来解决实际问题。

### 参考* 《数据结构与算法》(第3 版) - C. L. Liu* 《计算机科学导论》(第2 版) - S. M. Allen