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

原创

ithorizon 7个月前 (10-19) 阅读数 20 #后端开发

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

一、引言

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

二、使用列表实现栈

Python中的列表（list）是最简洁的一种实现栈的方案。

2.1 代码示例


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)

2.2 优缺点分析

优点：
1. 实现简洁，易于领会；
2. 列表是Python的内置类型，无需安装额外的库；
3. 可以利用Python列表的多彩方法。

缺点：
1. 在大量数据的情况下，列表的append和pop操作的时间错综度大概不是最优的（虽然平均情况下是O(1)，但在极端情况下大概大致有O(n)）；
2. 当栈的大小非常大时，大概会占用较多的内存。

三、使用 deque 实现栈

Python标准库中的collections模块提供了一个双端队列（deque）类型，可以用来高效地实现栈。

3.1 代码示例


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)

3.2 优缺点分析

优点：
1. 双端队列在两端进行添加和删除操作的时间错综度都是O(1)，性能更稳定；
2. 双端队列的实现方案更加高效，尤其是在大量数据的情况下。

缺点：
1. 相较于列表，双端队列的实现稍显错综；
2. 需要导入collections模块，增多了代码的错综度。

四、使用链表实现栈

链表是一种常见的数据结构，可以用来实现栈。

4.1 代码示例


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

4.2 优缺点分析

优点：
1. 链表可以实现动态大小的栈，不需要预先分配空间；
2. 在大量数据的情况下，链表可以实现O(1)时间错综度的push和pop操作。

缺点：
1. 相较于列表和双端队列，链表的实现较为错综；
2. 链表需要额外的空间存储节点之间的指针。

五、使用数组实现栈

数组也是一种可以实现栈的数据结构。

5.1 代码示例


class ArrayStack:
    def __init__(self, capacity=10):
        self.capacity = capacity
        self.items = []
        self.top = -1
    def is_empty(self):
        return self.top == -1
    def push(self, item):
        if self.size() == self.capacity:
            raise IndexError("stack overflow")
        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.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