Python实现栈的方法详解【基于数组和单链表两种方法】

首先我们需要了解什么是栈。栈是一种后进先出（LIFO）的数据结构，即最后进入的元素最先弹出。栈包含两种主要操作：压入（Push）和弹出（Pop）。压入操作用于添加新元素到栈顶，弹出操作则是将栈顶元素移出并返回其值。

用Python实现栈有两种常见方法：基于数组和基于单链表。下面我将分别介绍这两种方法。

基于数组的栈实现

首先，我们需要创建一个类来表示栈。这个类需要包含以下操作：

• push(item)：将一个元素压入栈顶。
• pop()：将栈顶元素弹出并返回其值。
• peek()：返回栈顶元素的值。
• is_empty()：判断栈是否为空。
• size()：返回栈的大小。

下面是基于数组的栈实现的完整代码示例：

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

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

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

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

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

# 示例：
s = ArrayStack()
s.push(1)
s.push(2)
s.push(3)
print(s.peek())  # 输出结果：3
print(s.pop())   # 输出结果：3
print(s.pop())   # 输出结果：2
print(s.size())  # 输出结果：1

基于单链表的栈实现

基于单链表的栈实现与基于数组的栈实现相比，主要区别在于数据的存储方式。在基于单链表的栈实现中，每个元素都是一个单独的节点，而这些节点通过指针连接在一起。

下面是基于单链表的栈实现的完整代码示例：

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

class LinkedListStack:
    def __init__(self):
        self.top = None

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

    def pop(self):
        if self.is_empty():
            raise Exception("Stack is empty")
        else:
            popped_node = self.top
            self.top = self.top.next
            return popped_node.data

    def peek(self):
        if self.is_empty():
            raise Exception("Stack is empty")
        else:
            return self.top.data

    def is_empty(self):
        return self.top is None

    def size(self):
        count = 0
        current = self.top
        while current is not None:
            count += 1
            current = current.next
        return count

# 示例：
s = LinkedListStack()
s.push(1)
s.push(2)
s.push(3)
print(s.peek())  # 输出结果：3
print(s.pop())   # 输出结果：3
print(s.pop())   # 输出结果：2
print(s.size())  # 输出结果：1

以上就是基于数组和单链表的两种Python实现栈的方法。通过上述代码示例，我们可以更清晰地了解栈的基本操作以及两种实现方式的异同。