了解 Python 中的堆栈实现

0 Shares

理解数据结构：栈及其在 Python 中的应用

在计算机编程领域，数据结构扮演着至关重要的角色。它们是组织和存储数据的方式，能够显著影响程序的效率和性能。其中，栈（Stack）是一种基础而又强大的数据结构，值得我们深入研究。

本文将带你了解栈的概念，并探讨如何在 Python 中实现它。让我们开始吧！

栈是什么？

栈的概念可以类比于现实生活中堆叠起来的物品，例如一摞书或一堆盘子。其核心特点是“后进先出”（LIFO，Last-In-First-Out）原则。这意味着，最后放入栈中的元素将最先被取出。这种特性使得栈在处理特定类型的问题时非常有效。

想象一下，你有一堆书，你想取出最下面的那本。按照常规做法，你必须先移除它上面的所有书。在这个过程中，最先放上去的书最后才会被取出来。栈在计算机科学中也遵循相同的LIFO原则。

栈的基本操作

栈主要有两种基本操作：

1. 入栈（Push）

入栈操作是指将一个新元素添加到栈的顶部。

2. 出栈（Pop）

出栈操作是指从栈的顶部移除一个元素，并返回该元素的值。

下图展示了入栈和出栈操作的示意图：

除了基本操作，我们还经常需要一些辅助函数来获取关于栈的更多信息，例如:

查看栈顶元素（Peek）

查看栈顶元素，即返回栈顶的元素值，但不将其移除。

判断栈是否为空（isEmpty）

判断栈是否为空，如果栈中没有元素，则返回真（True），否则返回假（False）。

现在你已经掌握了栈的基本概念。让我们开始探索如何在 Python 中实现它。

假设你已经安装了 Python 环境，如果没有，也可以使用在线 Python 编译器。

Python 中的栈实现

相较于其他数据结构，栈的实现相对简单。Python 提供了多种方式来实现栈的功能。接下来，我们将逐一介绍。

方法一：使用列表（List）

我们可以利用 Python 中的列表数据类型来模拟栈的行为。以下是逐步实现的过程：

步骤一：创建一个名为 Stack 的类。

class Stack:
    pass

步骤二：在 Stack 类中，我们使用一个空列表来存储栈中的元素。

class Stack:
    def __init__(self):
        self.elements = []

步骤三：实现入栈操作，定义一个名为 push 的方法，该方法接收一个数据作为参数，并将其添加到列表的末尾。

class Stack:
    def __init__(self):
        self.elements = []

    def push(self, data):
        self.elements.append(data)
        return data

步骤四：实现出栈操作，定义一个名为 pop 的方法，使用列表的 pop 方法移除并返回列表的最后一个元素（即栈顶元素）。

class Stack:
    ## ...
    def pop(self):
        return self.elements.pop()

至此，我们已经完成了栈的基本操作。现在，让我们添加辅助函数以获取有关栈的更多信息。

步骤五：使用负索引来访问栈顶元素。代码 elements[-1] 返回列表的最后一个元素，即栈顶元素。

class Stack:
    ## ...

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

步骤六：当列表的长度为 0 时，栈为空。定义一个方法来检查栈是否为空。

class Stack:
    ## ...
    def is_empty(self):
        return len(self.elements) == 0

我们已经完成了使用列表数据类型来实现栈的功能。

别着急，我们还没有看到如何使用它。下面让我们看看如何使用它。我们必须为 Stack 类创建一个对象才能使用它。

class Stack: 
      ## ...

  if __name__ == '__main__':
      stack = Stack()

我们已经创建了一个 Stack 对象，现在可以测试它的操作了。请按照以下步骤操作：

使用 is_empty 方法检查栈是否为空，应该返回 True。
使用 push 方法依次将数字 1、2、3、4、5 入栈。
再次使用 is_empty 方法，应该返回 False。
使用 peek 方法打印栈顶元素。
使用 pop 方法从栈中弹出一个元素。
再次使用 peek 方法查看栈顶元素，应该返回 4。
依次弹出栈中剩余的所有元素。
最后使用 is_empty 方法，应该返回 True。

如果按照上述步骤，我们的栈实现就没有问题。请尝试编写以上步骤的代码。

代码写好了吗？如果没有，请查看以下代码：

class Stack: 
    def __init__(self): 
        self.elements = [] 
    
    def push(self, data): 
        self.elements.append(data) 
        return data 
    
    def pop(self): 
        return self.elements.pop() 
        
    def peek(self): 
        return self.elements[-1] 
        
    def is_empty(self): 
        return len(self.elements) == 0

  if __name__ == '__main__':
      stack = Stack()
    
      ## checking is_empty method -> true
      print(stack.is_empty())

      ## pushing the elements
      stack.push(1)
      stack.push(2)
      stack.push(3)
      stack.push(4)
      stack.push(5)

      ## again checking is_empty method -> false
      print(stack.is_empty())

      ## printing the topmost element of the stack -> 5
      print(stack.peek())

      ## popping the topmost element -> 5
      stack.pop()

      ## checking the topmost element using peek method -> 4
      print(stack.peek())

      ## popping all the elements
      stack.pop()
      stack.pop() 
      stack.pop() 
      stack.pop() 

      ## checking the is_empty method for the last time -> true
      print(stack.is_empty())

如果运行以上代码，你会得到如下输出：

True
False
5
4
True

我们也可以直接使用列表数据类型作为栈。以上栈的实现有助于理解其他编程语言中栈的实现原理。

你还可以查看这些与列表相关的文章。

接下来，让我们看看如何使用内置的 collections 模块中的双端队列（deque）来实现栈的功能。

方法二：使用 collections 中的双端队列

双端队列（deque）是一种允许在两端进行插入和删除操作的数据结构。因此，我们可以利用其特性来模拟栈的行为，让它遵循“后进先出”的原则。

双端队列内部使用双向链表实现，因此在两端插入和删除元素都具有高效的性能。尽管访问中间元素的时间复杂度为 O(n)，但由于栈操作主要集中在栈顶，因此不影响我们将其用作栈。

在实现栈之前，我们先来看看使用双端队列实现栈的关键方法：

append(data)：用于将元素压入栈顶。
pop()：用于从栈顶移除元素。

对于 peek() 和 is_empty() 操作，我们可以打印整个栈来代替 peek() 方法。我们可以使用 len() 函数检查栈是否为空。

现在，我们使用 collections 模块中的 deque 来实现栈：

from collections import deque

  ## creating deque object
  stack = deque()

  ## checking whether stack is empty or not -> true
  print(len(stack) == 0)

  ## pushing the elements
  stack.append(1)
  stack.append(2)
  stack.append(3)
  stack.append(4)
  stack.append(5)

  ## again checking whether stack is empty or not -> false
  print(len(stack) == 0)

  ## printing the stack
  print(stack)

  ## popping the topmost element -> 5
  stack.pop()

  ## printing the stack
  print(stack)

  ## popping all the elements
  stack.pop()
  stack.pop() 
  stack.pop() 
  stack.pop() 

  ## checking the whether stack is empty or not for the last time -> true
  print(len(stack) == 0)

这样就完成了使用 collections 模块中的 deque 实现栈的功能。如果执行上述代码，你将得到如下输出：

True
False
deque([1, 2, 3, 4, 5])
deque([1, 2, 3, 4])
True

到目前为止，我们已经看到了两种实现栈的方法。还有其他实现栈的方法吗？是的！让我们来看看本教程中实现栈的最后一种方法。

方法三：使用 LifoQueue（后进先出队列）

LifoQueue 这个名称已经表明它遵循 LIFO 原则。因此，我们可以直接将它作为栈来使用。LifoQueue 来自内置的 queue 模块，并提供了一些便捷的方法来操作栈。让我们来看看这些方法：

put(data)：将数据添加到栈顶，相当于入栈操作。
get()：从栈顶移除一个元素并返回其值，相当于出栈操作。
empty()：检查栈是否为空。
qsize()：返回栈中元素的个数。

现在，我们使用 queue 模块中的 LifoQueue 来实现栈：

from queue import LifoQueue

  ## creating LifoQueue object
  stack = LifoQueue()

  ## checking whether stack is empty or not -> true
  print(stack.empty())

  ## pushing the elements
  stack.put(1)
  stack.put(2)
  stack.put(3)
  stack.put(4)
  stack.put(5)

  ## again checking whether stack is empty or not -> false
  print(stack.empty())

  ## popping all the elements
  print(stack.get())
  print(stack.get())
  print(stack.get())

  ## checking the stack size
  print("Size", stack.qsize())

  print(stack.get())
  print(stack.get())

  ## checking the whether stack is empty or not for the last time -> true
  print(stack.empty())

如果执行上述代码，你会得到如下输出：

True
False
5
4
3
Size 2
2
1
True

栈的应用

现在你已经对栈有了充分的了解，可以将其应用到实际的编程问题中。让我们来看一个常见的例子：

问题：给定一个包含括号、大括号和中括号的表达式，编写程序检查表达式中的括号是否正确配对。

例如：

输入："[{}]([])"

输出：平衡

输入："{[}]([])"

输出：不平衡

我们可以使用栈来解决这个问题。以下是解决问题的步骤：

创建一个栈来存储字符。
如果表达式的长度为奇数，则表达式是不平衡的。
遍历给定的表达式：
- 如果当前字符是 (、{ 或 [，则将其压入栈中。
- 否则，如果当前字符是闭括号 )、} 或 ]，则从栈中弹出一个元素。
- 如果弹出的字符与当前闭括号匹配，则继续，否则括号不平衡。
迭代完成后，如果栈为空，则表达式是平衡的，否则是不平衡的。

我们可以使用 set 数据类型来快速判断括号是否匹配。

## stack
class Stack: 
    def __init__(self): 
        self.elements = [] 
    
    def push(self, data): 
        self.elements.append(data) 
        return data 
        
    def pop(self): 
        return self.elements.pop() 
    
    def peek(self): 
        return self.elements[-1] 
        
    def is_empty(self): 
        return len(self.elements) == 0

def balance_check(expression):
    ## checking the length of the expression
    if len(expression) % 2 != 0:
        ## not balanced if the length is odd
        return False
    
    ## for checking
    opening_brackets = set('([{') 
    pairs = set([ ('(',')'), ('[',']'), ('{','}') ]) 
    
    ## stack initialization
    stack = Stack()
    
    ## iterating through the given expression
    for bracket in expression:

        ## checking whether the current bracket is opened or not        
        if bracket in opening_brackets:
            ## adding to the stack 
            stack.push(bracket)
        else:
            ## popping out the last bracket from the stack
            popped_bracket = stack.pop()
        
            ## checking whether popped and current bracket pair
            if (popped_bracket, bracket) not in pairs:
                return False
    
    return stack.is_empty()

if __name__ == '__main__':
    if balance_check('[{}]([])'):
        print("Balanced")
    else:
        print("Not Balanced")
    
    if balance_check('{[}]([])'):
        print("Balanced")
    else:
        print("Not Balanced")

我们可以使用栈来解决更多类型的问题。尝试在你认为合适的地方应用栈的概念。

总结

恭喜你！你已经完成了本教程。希望你像我一样喜欢它。本教程到此结束。

祝你编程愉快！ 🙂👨‍💻