一篇博客学会一个point | 计算机数据结构:栈-Python实现代码加可视化

1.栈的定义

堆栈(英语:stack)又称为栈或堆叠,是计算机科学中的一种抽象资料类型,只允许在有序的线性资料集合的一端(称为堆栈顶端,英语:top)进行加入数据(英语:push)和移除数据(英语:pop)的运算。因而按照后进先出(LIFO, Last In First Out)的原理运作,堆栈常用一维数组或链表来实现。常与另一种有序的线性资料集合队列相提并论。

一篇博客学会一个point | 计算机数据结构:栈-Python实现代码加可视化_第1张图片

 也可以表示为:

一篇博客学会一个point | 计算机数据结构:栈-Python实现代码加可视化_第2张图片

 

2.栈的操作

  • Stack() 创建一个空的新栈
  • push(item)将一个新项添加到栈的顶部
  • pop() 从栈中删除顶部项
  • peek() 从栈返回顶部项,但不会删除它
  • is_Empty() 测试栈是否为空
  • size() 返回栈中的 item 数量

3.栈的Pytorch实现

class Stack(object):
    def __init__(self):  # 初始化栈为空列表
        self.items = []
    def is_empty(self):  # 判断栈是否为空,返回布尔值
        return self.items == []
    def peek(self):  # 返回栈顶元素
        return self.items[len(self.items) - 1]
    def size(self):  # 返回栈的大小
        return len(self.items)
    def push(self, item):  # 把新的元素堆进栈里面(入栈)
        self.items.append(item)
    def pop(self, item):  # 把栈顶元素丢出去(出栈)
        return self.items.pop()
if __name__ == '__main__':

    stack_=Stack()
    #stack_.push("香蕉","苹果","橘子")出错,一次只能push一个元素
    stack_.push('香蕉')#第一个输入的元素,就是最底下的元素
    stack_.push('苹果')
    stack_.push('橘子')#栈顶的元素
    print(stack_.size())#查看栈大小
    print(stack_.peek())#打印栈顶元素
    print(stack_.pop('苹果'))#删除顶部元素,就算定义删除中间的,也默认删除与顶部元素
    print(stack_.peek())#所以上面删掉了香蕉,现在上面的是苹果
    print(stack_.is_empty())  # 判断栈是不是空了?

结果:

一篇博客学会一个point | 计算机数据结构:栈-Python实现代码加可视化_第3张图片

4.实现可视化

一篇博客学会一个point | 计算机数据结构:栈-Python实现代码加可视化_第4张图片

一篇博客学会一个point | 计算机数据结构:栈-Python实现代码加可视化_第5张图片

 5.栈的应用

5.1.括号匹配(LeetCode题)

分析:如果我们把一个python列表看作一个栈,且列表末尾为栈顶。那么我们可以使用list.append来为实现push操作(为栈顶添加元素)。使用内置的pop函数来弹出栈顶元素。每遇到一个左括号就将其压入栈,每遇到一个右括号就和栈顶元素匹配,如果匹配成功则栈顶元素弹出。判断结果为:当循环完成时,栈为空,则返回True,否则返回False。

5.2.表达式转换

5.3.10进制转2进制

参考文献:

【1】https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

你可能感兴趣的