了解 Python 中的堆栈实现

0 Shares

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

让我们了解堆栈及其在 Python 中的实现。

什么是堆栈？

一堆类似于现实生活中的一堆书、椅子等。它遵循后进先出 (LIFO) 原则。它是最简单的数据结构。让我们用一个真实的例子来看一下这个场景。

假设我们有一堆书如下。

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

堆栈操作

一个栈中主要有两个操作

1.推送（数据）

将数据添加或压入堆栈。

2.弹出（）

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

请参见下图的推送和弹出操作说明。

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

让我们看看他们。

窥视（）

返回栈顶的元素。

是空的（）

返回堆栈是否为空。

堆栈数据结构的概念方面已经足够了。让我们进入实施，不用多说。

我假设您的 PC 上安装了 python，如果没有，您也可以尝试使用在线编译器。

堆栈实现

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

让我们一一看看。

#1。列表

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

Step1：编写一个名为Stack的类。

class Stack:
	pass

第 2 步：我们必须在列表中维护数据。让我们在 Stack 类中添加一个带有名称元素的空列表。

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

Step3：要将元素压入栈中，我们需要一个方法。让我们编写一个 push 方法，它将数据作为参数并将其附加到元素列表。

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

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

Step4：同样，我们来写弹出栈顶元素的pop方法。我们可以使用list数据类型的pop方法。

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

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

Step5：我们可以使用负索引从堆栈中获取最顶层元素。代码元素[-1] 返回列表的最后一个。在我们的例子中，它是堆栈的最顶层元素。

class Stack:
	## ...

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

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

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

我们已经完成了使用列表数据类型实现堆栈。

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

快来看看如何实现吧。我们必须为 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。核实。

如何检查 PC 中的显卡 (GPU)

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

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

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 内置模块的内置双端队列，它可以充当堆栈。

#2。来自集合的双端队列

它被实现为一个双端队列。由于它支持从两端添加和删除元素。因此我们可以将它用作堆栈。我们可以让它遵循栈的后进先出原则。

它是使用称为双向链表的其他数据结构实现的。所以元素的插入和删除的表现是一致的。从中间链表访问元素花费了 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 内置模块中的双端队列来实现堆栈。如果执行上述程序，您将获得如下所示的输出。

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

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

面向初学者的 DevOps 简介

#3。后进队列

LifoQueue 这个名字本身就表明它遵循 LIFO 原则。因此我们可以毫无疑问地将它用作堆栈。它来自内置模块队列。 LifoQueue 提供了一些在堆栈实现中很有用的便捷方法。让我们看看他们

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

让我们使用队列模块中的 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

栈的应用

现在，您对堆栈有了足够的了解，可以将其应用到编程问题中。让我们看一个问题并使用堆栈解决它。

给定一个表达式，编写一个程序来检查括号、大括号、大括号是否正确平衡。

让我们看一些例子。

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

输出：平衡

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

Netflix 有 Jujutsu Kaisen 吗？

输出：不平衡

我们可以使用栈来解决上面的问题。让我们看看解决问题的步骤。

创建一个堆栈来存储字符。
如果表达式的长度是奇数，则表达式是不平衡的
遍历给定的表达式。
- 如果当前字符是 ( 或 { 或 [, then push it to stack.
- Else if the current character is a closing bracket ) or } or ]，然后从堆栈中弹出。
- 如果弹出的字符与起始括号匹配，则继续，否则括号不平衡。
迭代后，如果堆栈为空，则方程是平衡的，否则方程是不平衡的。

我们可以使用 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")

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

结论

呀！您已完成本教程。我希望你在制作教程时和我一样喜欢它。本教程就是这样。

快乐编码🙂👨‍💻

什么是堆栈？

堆栈操作

1.推送（数据）

2.弹出（）

窥视（）

是空的（）

堆栈实现

#1。 列表

#2。 来自集合的双端队列

#3。 后进队列

栈的应用

结论

You might also like

修复 Roku 低功耗错误

如何修复事件 ID 1001

如何在 Ubuntu 服务器上的 Webmin 中设置 NFS 共享

#1。列表

#2。来自集合的双端队列

#3。后进队列