【数据结构与算法】栈的实现（链式存储）

**栈的实现（链式存储）**

栈是一种线性数据结构，它遵循后进先出（LIFO）的原则，即最后添加的元素将最先被移除。栈可以使用数组或链表来实现。在本文中，我们将讨论如何使用链式存储来实现栈。

**链式存储**

链式存储是一种数据结构，其中每个元素都有一个指向下一个元素的引用（也称为“后继”）。这种结构允许我们在任意位置添加或删除元素，而不需要移动其他元素。链式存储通常用于实现栈、队列和图等数据结构。

**栈的基本操作**

栈支持以下基本操作：

1. **push（x）**: 将元素 x 添加到栈顶。
2. **pop（）：** 移除并返回栈顶元素。
3. **peek（）：** 返回但不移除栈顶元素。
4. **isEmpty（）：** 检查栈是否为空。

**链式存储实现**

下面是链式存储实现栈的代码示例：

class Node:
 """链式存储中的一个节点"""
 def __init__(self, value):
 self.value = value self.next = Noneclass Stack:
 """使用链式存储实现的栈"""
 def __init__(self):
 self.top = None # 栈顶指针 self.size =0 # 栈大小 def push(self, x):
 """
 将元素 x 添加到栈顶。
 :param x: 元素值 """
 node = Node(x)
 if self.top is None:
 self.top = node else:
 node.next = self.top self.top = node self.size +=1 def pop(self):
 """
 移除并返回栈顶元素。
 :return: 栈顶元素值 :raises IndexError: 如果栈为空 """
 if self.isEmpty():
 raise IndexError("Stack is empty")
 value = self.top.value self.top = self.top.next self.size -=1 return value def peek(self):
 """
 返回但不移除栈顶元素。
 :return: 栈顶元素值 :raises IndexError: 如果栈为空 """
 if self.isEmpty():
 raise IndexError("Stack is empty")
 return self.top.value def isEmpty(self):
 """检查栈是否为空"""
 return self.size ==0

stack = Stack()

# 将元素添加到栈中stack.push(1)
stack.push(2)
stack.push(3)

# 移除并返回栈顶元素print(stack.pop()) # 输出:3# 返回但不移除栈顶元素print(stack.peek()) # 输出:2# 检查栈是否为空print(stack.isEmpty()) # 输出: False# 将元素添加到栈中stack.push(4)

# 移除并返回栈顶元素print(stack.pop()) # 输出:4# 检查栈是否为空print(stack.isEmpty()) # 输出: True