了解 Python 中的堆栈实现

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

让我们了解堆栈及其在 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

栈的应用

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

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

让我们看一些例子。

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

输出:平衡

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

输出:不平衡

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

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

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

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

结论

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

快乐编码🙂👨‍💻