Python 栈实现的几种方式及优劣详解

什么是栈

栈（Stack），是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算，称为栈顶，另一端称为栈底。它是一种先进后出的数据结构。

栈的基本操作

• push(item)：添加一个新元素到栈顶
• pop(): 弹出栈顶元素
• peek(): 返回栈顶元素
• is_empty(): 判断栈是否为空
• size(): 返回栈的元素数量

栈的实现方式

元素存储

• 数组：基于数组实现的栈，在栈满时需要进行扩容，而在栈空间浪费的情况下不能压缩。经常需要调整大小，因此它适用于当我们了解栈的最大容量时。时间复杂度：O(1)。
• 链表：就是链表实现的栈，插入与删除数据的时间复杂期均为O(1)，但需要额外的空间存储指针。同时，由于Python中的链表不支持随机读取，因此仅限于单线程或少量数据的情况。时间复杂度：O(1)。

栈的类型

• 普通栈：通用，无优劣势。
• 并发栈：一种特殊的栈，支持并发处理。用于多线程程序的并发操作，需要考虑并发控制。在多线程的场合下，经常会出现竞争和冲突，因此需要实现并发同步。时间复杂度：O(1)。

栈的实现方式的优缺点

• 数组：适用于需要快速访问元素的场合，时间复杂度较高，不适用于大量数据。空间复杂度：O(n)。
• 链表：空间利用率高，可以动态的进行扩容或缩小容量，适用于大量数据或动态增减的场合。同时也支持并发操作。时间复杂度：O(n)。
• 并发栈：支持多线程访问、修改的场景，不会出现竞争、冲突等问题，性能优秀。但是，实现起来比普通栈复杂，缺点是程序员需要掌握并发同步相关的知识点。时间复杂度：O(n)。

示例说明

用数组实现一个栈

class ArrayStack:
    def __init__(self):
        self._data = []
        self._size = 0

    def push(self, item):
        """将元素添加到栈顶"""
        self._data.append(item)
        self._size += 1

    def pop(self):
        """从栈顶弹出一个元素"""
        if self.is_empty():
            raise IndexError('pop from empty stack')
        self._size -= 1
        return self._data.pop()

    def peek(self):
        """返回栈顶元素"""
        if self.is_empty():
            raise IndexError('peek from empty stack')
        return self._data[-1]

    def is_empty(self):
        """判断栈是否为空"""
        return self._size == 0

    def size(self):
        """返回栈元素的数量"""
        return self._size

用链表实现一个栈

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

class LinkedListStack:
    def __init__(self):
        self._size = 0
        self._head = None

    def push(self, item):
        """将元素添加到栈顶"""
        new_node = Node(data=item, next_node=self._head)
        self._head = new_node
        self._size += 1

    def pop(self):
        """从栈顶弹出一个元素"""
        if self.is_empty():
            raise IndexError('pop from empty stack')
        self._size -= 1
        data = self._head.data
        self._head = self._head.next_node
        return data

    def peek(self):
        """返回栈顶元素"""
        if self.is_empty():
            raise IndexError('peek from empty stack')
        return self._head.data

    def is_empty(self):
        """判断栈是否为空"""
        return self._size == 0

    def size(self):
        """返回栈元素的数量"""
        return self._size

以上就是栈的两种实现方式及优缺点的介绍，希望可以帮助读者更好地理解栈的特点及实现方式。