数据结构实践：用Python实现栈、队列及链表

原创布满荆棘的人生 2025-02-15 13:42 10阅读 0赞

在Python中，我们可以使用内置的数据类型或一些特定的库来实现栈、队列和链表。

下面我将分别介绍如何使用Python实现这些数据结构。

1. 栈（Stack）

- 双端队列（deque）：Python的collections模dule提供了Deque类，它是一种可以在两端进行插入和删除操作的线性容器。
```python
from collections import deque

class Stack:
    def __init__(self):
        self.items = deque()

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

# 从栈顶移除并返回元素
    def pop(self):
        if not self.is_empty():
            return self.items.popleft()
        else:
            raise Exception("Stack is empty!")

# 检查栈是否为空
    def is_empty(self):
        return len(self.items) == 0

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

2. 队列（Queue）

- Python标准库中的`queue`模块：Python提供了一个名为`queue`的内置模块，它提供了多种队列类型。
```python
from queue import Queue

class Queue:
    def __init__(self):
        self.queue = Queue()

# 添加元素到队尾
    def enqueue(self, item):
        self.queue.put(item)

# 从队头移除并返回元素
    def dequeue(self):
        if not self.is_empty():
            return self.queue.get()
        else:
            raise Exception("Queue is empty!")

# 检查队列是否为空
    def is_empty(self):
        return self.queue.empty()

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

3. 链表（Linked List）

- Python实现：我们可以通过定义一个类来表示链表中的节点，然后通过连接这些节点的方式来构建链表。
```python
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

# 在链尾添加新节点
    def append(self, new_node):
        if not self.head:
            self.head = new_node
            return
        current_node = self.head
        while current_node.next:
            current_node = current_node.next
        current_node.next = new_node

# 从链表中移除指定节点
    def remove(self, node_to_remove):
        if not self.head or node_to_remove == self.head:
            return None
        current_node = self.head
        while current_node and current_node != node_to_remove:
            current_node = current_node.next
        # 如果找到了要删除的节点，删除它并更新链表
        if current_node:
            next_node = current_node.next
            current_node.next = next_node
            return node_to_remove
        else:
            return None

# 使用示例
linked_list = LinkedList()
linked_list.append(Node(1)))
linked_list.append(Node(2))
linked_list.append(Node(3))

# 输出链表中的元素
current_node = linked_list.head
while current_node:
    print(current_node.data, end=' -> ')
    current_node = current_node.next
print("None")

# 删除节点 2
node_to_remove = linked_list.remove(Node(2)))
if node_to_remove:
    print(f"Node {node_to_remove.data}} successfully removed.")
else:
    print("Failed to remove the node.")
```

以上代码示例展示了如何使用Python来实现栈、队列和链表。