Python栈的实现方法示例【列表、单链表】

下面我将详细讲解Python栈的实现方法，包括列表和单链表两种方法。

什么是栈？

在开始讲解栈的实现方法之前，我们需要先了解什么是栈。栈（Stack）是一种先进后出的数据结构，它只允许在一端进行插入和删除操作，这一端通常称为栈顶。栈被广泛应用于计算机中，例如函数调用、表达式求值、括号匹配等。

列表实现栈

在Python中，可以使用列表（list）来实现栈。列表的append()方法用于在末尾添加元素，而pop()方法则用于删除并返回列表的最后一个元素，因此可以通过列表的末尾作为栈顶，实现栈的基本功能。

下面是使用列表实现栈的示例代码：

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()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

这个示例中，Stack类维护一个列表self.items，它代表栈。push()方法用于添加元素，pop()方法用于删除元素，peek()方法用于返回栈顶元素但不删除它，is_empty()方法用于判断栈是否为空，size()方法用于返回栈的大小。

单链表实现栈

除了使用列表，我们还可以使用单链表来实现栈。在单链表中，每个节点包含一个元素和一个指向下一个节点的引用。我们可以将头节点作为栈顶，然后使用链表的头插入和删除操作来实现栈的基本功能。

下面是使用单链表实现栈的示例代码：

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

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

    def push(self, item):
        new_node = Node(item)
        new_node.next = self.head
        self.head = new_node

    def pop(self):
        if not self.is_empty():
            popped = self.head
            self.head = self.head.next
            popped.next = None
            return popped.data

    def peek(self):
        if not self.is_empty():
            return self.head.data

    def is_empty(self):
        return not self.head

    def size(self):
        count = 0
        current = self.head
        while current:
            count += 1
            current = current.next
        return count

这个示例中，Node类代表链表的节点，它包含一个元素data和一个指向下一个节点的next引用。Stack类维护一个头节点self.head，它相当于栈顶。push()方法用于添加元素，pop()方法用于删除元素，peek()方法用于返回栈顶元素但不删除它，is_empty()方法用于判断栈是否为空，size()方法用于返回栈的大小。

总结

本文详细介绍了Python栈的实现方法，包括使用列表和单链表两种方法。列表的append()和pop()操作实现简单、方便，但如果栈中元素过多，可能会导致效率下降。单链表的头插入和删除操作效率高，但需要额外的节点空间来存储节点的next引用。因此，在使用栈时，需要根据实际情况选择合适的实现方法。