理解Python中的堆栈实现

作者姚伟斌

数据结构在编程世界中起着关键作用。它们帮助我们以高效的方式组织数据。堆栈是最简单的数据结构之一。

让我们学习一下堆栈及其在Python中的实现。

什么是堆栈？

堆栈类似于现实生活中的书堆、椅子堆等等。它遵循先进后出（LIFO）原则。这是最简单的数据结构。让我们通过一个现实世界的例子来看一下情况。

假设我们有一堆书如下所示。

当我们想要从顶部取出第三本书时，我们必须先将前两本书从顶部移除。在这里，最顶部的书最后放入书堆，并且最先从书堆取出。数据结构堆栈在编程中遵循相同的先进后出（LIFO）原则。

堆栈的操作

堆栈有两个主要操作

1. push(data)

将数据添加或推入堆栈。

2. pop()

从堆栈中移除或弹出最顶部的元素。

请看下面关于push和pop操作的说明。

我们将编写一些辅助函数，以帮助我们获取有关堆栈的更多信息。

让我们来看看它们。

peek()

返回堆栈的最顶部元素。

is_empty()

返回堆栈是否为空。

足够的关于堆栈数据结构的概念知识。让我们马上进入实现的部分。

我假设你的PC上有python installed，如果没有，你也可以尝试online compiler。

堆栈的实现

与其他数据结构的实现相比，堆栈的实现是最简单的。我们可以在Python中以多种方式实现堆栈。

让我们逐个看看它们。

#1. 列表

我们将使用列表在一个类中实现堆栈。让我们看看堆栈的逐步实现。

第1步: 编写一个名为Stack的类。

class Stack:
	pass

第2步: 我们需要在堆栈类中使用一个列表来存储数据。让我们在Stack类中添加一个名为elements的空列表。

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

第3步: 为了将元素推入堆栈，我们需要一个方法。让我们编写一个名为push的方法，该方法接受数据作为参数，并将其追加到elements列表中。

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

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

第4步: 类似地，让我们编写pop方法，它从堆栈中弹出最顶部的元素。我们可以使用列表数据类型的pop方法。

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

我们已经完成了具有所需操作的堆栈实现。现在，让我们添加辅助函数以获取有关堆栈的更多信息。

第5步：我们可以使用负索引从堆栈中获取最顶部的元素。代码element[-1]返回列表的最后一个元素。在我们的情况下，它是堆栈的最顶部元素。

class Stack:
	## ...

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

第6步：如果elements列表的长度为0，则堆栈为空。让我们编写一个方法，返回元素是否为空。

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

我们已经使用列表（list）数据类型完成了栈的实现。

哦！等等，我们刚刚完成了它。但是，我们没有看到如何使用它。那么要如何使用它呢？

来看看如何实现它。我们需要为Stack类创建一个对象才能使用它。这不是什么大问题。让我们首先做这件事。

<class Stack:
## …

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

我们已经创建了栈对象并且准备好使用它。让我们按照以下步骤测试栈的操作。

  • 使用is_empty方法检查栈是否为空。它应该返回True。
  • 使用push方法将数字1、2、3、4、5压入栈中。
  • is_empty方法应该返回False。进行检查。
  • 使用peek方法打印栈顶元素。
  • 使用pop方法从栈中弹出元素。
  • 检查peek元素。它应该返回元素4。
  • 现在，从栈中弹出所有元素。
  • is_empty方法应该返回True。进行检查。

如果通过了上述所有步骤，我们的栈实现就已经完成了。尝试编写上述步骤的代码。

你写代码了吗？不，不要担心，检查下面的代码。

true
print(stack.is_empty())

## 压入元素
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)

## 再次检查is_empty方法 -> false
print(stack.is_empty())

## 打印栈顶元素 -> 5
print(stack.peek())

## 弹出栈顶元素 -> 5
stack.pop()

## 使用peek方法检查栈顶元素 -> 4
print(stack.peek())

## 弹出所有元素
stack.pop()
stack.pop()
stack.pop()
stack.pop()

## 最后一次检查is_empty方法 -> true
print(stack.is_empty())

太棒了！我们已经使用列表（list）数据类型从头开始完成了栈的实现。如果你运行上面的代码，你将会看到下面提到的输出。

True
False
5
4
True

我们可以直接使用列表（list）数据类型作为栈。上述栈的实现还帮助你理解其他编程语言中的栈实现。

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

让我们来看看内置模块collections中的deque，它可以作为栈来使用。

#2. collections中的deque

它是作为双向队列实现的。由于它支持从两端添加和删除元素。因此我们可以将其用作栈。我们可以使其遵循栈的LIFO原则。

它是使用其他数据结构实现的，称为双向链表。因此，插入和删除元素的性能是一致的。从链表中间访问元素需要O(n)的时间。由于不需要从堆栈中访问中间元素，因此我们可以将其用作堆栈。

在实现堆栈之前，让我们看一下使用队列实现堆栈的方法。

  • append(data) – 用于将数据推入堆栈
  • pop() – 用于从堆栈中移除顶部元素

对于peek和is_empty没有替代方法。我们可以打印整个堆栈来代替peek方法。接下来，我们可以使用len方法来检查堆栈是否为空。

让我们使用collections模块中的deque来实现堆栈。

from collections import deque

## 创建deque对象
stack = deque()

## 检查堆栈是否为空-> True
print(len(stack) == 0)

## 推入元素
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)

## 再次检查堆栈是否为空-> False
print(len(stack) == 0)

## 打印堆栈
print(stack)

## 弹出顶部元素-> 5
stack.pop()

## 打印堆栈
print(stack)

## 弹出所有元素
stack.pop()
stack.pop() 
stack.pop() 
stack.pop() 

## 最后一次检查堆栈是否为空-> True
print(len(stack) == 0)

这就是了。我们已经学习了如何使用内置模块collections的deque来实现堆栈。如果您执行上面的程序，您将得到以下输出。

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

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

#3. LifoQueue

名称LifoQueue本身就说明了它遵循LIFO原则。因此我们可以毫不犹豫地将其用作堆栈。它来自内置模块queue。 LifoQueue提供了一些在堆栈实现中有用的便捷方法。让我们看看它们

  • put(data) – 添加或推入数据到队列
  • get() – 从队列中删除或弹出顶部元素
  • empty() – 返回堆栈是否为空
  • qsize() – 返回队列的长度

让我们使用queue模块中的LifoQueue来实现堆栈。

from queue import LifoQueue

## 创建LifoQueue对象
stack = LifoQueue()

## 检查堆栈是否为空-> True
print(stack.empty())

## 推入元素
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)

## 再次检查堆栈是否为空-> False
print(stack.empty())

## 弹出所有元素
print(stack.get())
print(stack.get())
print(stack.get())

## 检查堆栈大小
print("Size", stack.qsize())

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

## 最后一次检查堆栈是否为空-> True
print(stack.empty())

如果您执行以上程序而不更改它，您将得到下面提到的输出。

True
False
5
4
3
Size 2
2
1
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

def balance_check(expression):
    ## 检查表达式的长度
    if len(expression) % 2 != 0:
        ## 长度为奇数时不平衡
        return False
    
    ## 用于检查
    opening_brackets = set('([{') 
    pairs = set([ ('(',')'), ('[',']'), ('{','}') ]) 
    
    ## 栈初始化
    stack = Stack()
    
    ## 遍历给定的表达式
    for bracket in expression:

        ## 检查当前括号是否打开    
        if bracket in opening_brackets:
            ## 添加到栈中
            stack.push(bracket)
        else:
            ## 弹出栈中的最后一个括号
            popped_bracket = stack.pop()
        
            ## 检查弹出的括号和当前括号是否配对
            if (popped_bracket, bracket) not in pairs:
                return False
    
    return stack.is_empty()

if __name__ == '__main__':
    if balance_check('[{}]([])'):
        print("平衡")
    else:
        print("不平衡")
    
    if balance_check('{[}]([])'):
        print("平衡")
    else:
        print("不平衡")

    我们可以使用栈来解决更多问题。上述问题就是其中之一。尽量在你认为最适合的地方应用栈的概念。

    结论

    耶！你已经完成了教程。希望你在制作教程时和我一样享受。教程到此结束。

    编码愉快 🙂 👨‍💻

姚伟斌

程序猿

我是姚伟斌，也被称为文景。我的专业领域涵盖了开放源代码的深度探索、网络编程和网络建站。我热衷于分享我的编程和建站实践经验，尤其擅长于Nginx和Proxy服务器的管理。此外，我还对Python和NodeJS这两种编程语言有着深刻的理解和独到的见解。

最近，我致力于爬虫技术的研究，探索如何通过高效的数据抓取为项目增添价值。我的目标是通过持续的学习和创新，为开放源代码社区贡献我的力量，并帮助那些对网络编程和网站建设感兴趣的人士。

类似文章

7个最佳的Project Zomboid服务器托管为更好的游戏体验

7个最佳的Project Zomboid服务器托管为更好的游戏体验

作者姚伟斌

短缺和资源管理方面的挑战。在这个游戏中，玩家需要采集资源、建立庇护所、研究和制作物品，以生存下去并尽可能长时间地抵抗僵尸的袭击。这款游戏的图形和音效效果非常出色，为玩家提供了一个逼真而吸引人的僵尸世界。无论你是新手还是经验丰富的玩家，都可以在Project Zomboid中找到乐趣。快来体验这个刺激而令人上瘾的僵尸游戏吧！