Python 数据结构：顺序栈、链式栈、循环队列和链式队列实现

本文将介绍如何使用 Python 实现常见的四种数据结构：顺序栈、链式栈、循环队列和链式队列。我们将提供每个数据结构的定义和相关方法的代码示例，帮助您理解这些结构的实现原理和应用场景。

1. 栈

栈是一种后进先出 (LIFO) 的数据结构，就像一个堆叠的盘子，只能从顶部添加或移除盘子。

(1) 顺序栈 SeqStack

顺序栈使用列表来存储数据，通过列表的 append() 和 pop() 方法实现入栈和出栈操作。

class SeqStack:
    def __init__(self):
        self.stack = []
    
    def is_empty(self):
        return len(self.stack) == 0
    
    def push(self, item):
        self.stack.append(item)
    
    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
    
    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
    
    def size(self):
        return len(self.stack)

(2) 链式栈 LinkStack

链式栈使用链表来存储数据，每个节点包含数据和指向下一个节点的指针。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkStack:
    def __init__(self):
        self.top = None
    
    def is_empty(self):
        return self.top is None
    
    def push(self, item):
        new_node = Node(item)
        new_node.next = self.top
        self.top = new_node
    
    def pop(self):
        if not self.is_empty():
            top_node = self.top
            self.top = self.top.next
            return top_node.data
    
    def peek(self):
        if not self.is_empty():
            return self.top.data
    
    def size(self):
        count = 0
        current = self.top
        while current:
            count += 1
            current = current.next
        return count

2. 队列

队列是一种先进先出 (FIFO) 的数据结构，就像排队的人，先排队的人先被服务。

(1) 循环队列 CirQueue

循环队列使用数组来存储数据，通过两个指针 front 和 rear 分别指向队头和队尾，并使用取余运算来实现循环操作。

class CirQueue:
    def __init__(self, capacity):
        self.queue = [None] * capacity
        self.front = 0
        self.rear = 0
        self.capacity = capacity
    
    def is_empty(self):
        return self.front == self.rear
    
    def is_full(self):
        return (self.rear + 1) % self.capacity == self.front
    
    def enqueue(self, item):
        if not self.is_full():
            self.queue[self.rear] = item
            self.rear = (self.rear + 1) % self.capacity
    
    def dequeue(self):
        if not self.is_empty():
            item = self.queue[self.front]
            self.front = (self.front + 1) % self.capacity
            return item
    
    def size(self):
        return (self.rear - self.front + self.capacity) % self.capacity

(2) 链式队列 LinkQueue

链式队列使用链表来存储数据，通过两个指针 front 和 rear 分别指向队头和队尾。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkQueue:
    def __init__(self):
        self.front = None
        self.rear = None
    
    def is_empty(self):
        return self.front is None
    
    def enqueue(self, item):
        new_node = Node(item)
        if self.is_empty():
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node
    
    def dequeue(self):
        if not self.is_empty():
            front_node = self.front
            self.front = self.front.next
            if self.front is None:
                self.rear = None
            return front_node.data
    
    def size(self):
        count = 0
        current = self.front
        while current:
            count += 1
            current = current.next
        return count

总结

本文详细介绍了 Python 中顺序栈、链式栈、循环队列和链式队列的实现方法，并提供了相应的代码示例。这些数据结构在计算机科学中有着广泛的应用，对于理解算法和数据结构基础知识至关重要。希望本文能够帮助您更好地理解这些数据结构的实现原理和应用场景。