Python 实现栈的几种方式及其优劣(Python实现栈的多种方法及其优缺点分析)

原创

ithorizon 6个月前 (10-21) 阅读数 22 #后端开发

Python 实现栈的几种方法及其优劣

一、引言

栈（Stack）是一种后进先出（Last In First Out, LIFO）的数据结构。在Python中，有多种方法可以实现栈的功能。本文将介绍几种常见的实现方法，并分析它们的优缺点。

二、使用列表实现栈

Python中的列表（list）是一种内置的数据结构，它提供了多彩的操作方法，可以很方便地实现栈的功能。


class ListStack:
    def __init__(self):
        self.items = []
    def is_empty(self):
        return len(self.items) == 0
    def push(self, item):
        self.items.append(item)
    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        raise IndexError("Pop from empty stack")
    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        raise IndexError("Peek from empty stack")
    def size(self):
        return len(self.items)

优点：

实现易懂，易于懂得；

利用Python内置的列表，无需额外安装包；

时间纷乱度较低，push和pop操作的时间纷乱度为O(1)。

缺点：

列表的内存分配是动态的，当列表扩容时，需要复制原有元素到新的内存空间，大概引起性能下降；

列表的存储空间是连续的，不适合存储大量数据。

三、使用deque实现栈

deque（双端队列）是Python标准库中的一个模块，它提供了高效的插入和删除操作，适合用于实现栈。


from collections import deque
class DequeStack:
    def __init__(self):
        self.items = deque()
    def is_empty(self):
        return len(self.items) == 0
    def push(self, item):
        self.items.append(item)
    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        raise IndexError("Pop from empty stack")
    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        raise IndexError("Peek from empty stack")
    def size(self):
        return len(self.items)

优点：

提供了高效的插入和删除操作，时间纷乱度为O(1)；

内存分配更为高效，避免了列表扩容时的性能问题。

缺点：

需要额外安装collections模块；

相较于列表，使用场景较少。

四、使用链表实现栈

链表是一种动态的数据结构，可以有效地实现栈。在Python中，可以使用类和节点来实现链表栈。


class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
class LinkedListStack:
    def __init__(self):
        self.head = None
    def is_empty(self):
        return self.head is None
    def push(self, item):
        new_node = Node(item)
        new_node.next = self.head
        self.head = new_node
    def pop(self):
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        value = self.head.value
        self.head = self.head.next
        return value
    def peek(self):
        if self.is_empty():
            raise IndexError("Peek from empty stack")
        return self.head.value
    def size(self):
        count = 0
        current = self.head
        while current:
            count += 1
            current = current.next
        return count

优点：

动态内存分配，避免了列表扩容问题；

插入和删除操作的时间纷乱度为O(1)。

缺点：

实现较为纷乱，代码量较大；

相较于列表和deque，性能略低。

五、使用数组实现栈

数组是一种基本的数据结构，也可以用于实现栈。在Python中，可以使用数组模块（array）来实现。


import array
class ArrayStack:
    def __init__(self, capacity=10):
        self.items = array.array('i', [None] * capacity)
        self.capacity = capacity
        self.top = -1
    def is_empty(self):
        return self.top == -1
    def push(self, item):
        if self.size() == self.capacity:
            raise IndexError("Stack is full")
        self.top += 1
        self.items[self.top] = item
    def pop(self):
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        value = self.items[self.top]
        self.items[self.top] = None
        self.top -= 1
        return value
    def peek(self):
        if self.is_empty():
            raise IndexError("Peek from empty stack")
        return self.items[self.top]
    def size(self):
        return self.top + 1