[快学Python3]数据结构-堆栈

概述

什么是堆栈,简单而言:后进先出。

算法原理

  • 进栈(PUSH)算法
  1. 若TOP≥n时,则给出溢出信息,作出错处理(进栈前首先检查栈是否已满,满则溢出;不满则作2)
  2. 置TOP=TOP+1(栈指针加1,指向进栈地址)
  3. S(TOP)=X,结束(X为新进栈的元素)
  • 退栈(POP)算法
  1. 若TOP≤0,则给出下溢信息,作出错处理(退栈前先检查是否已为空栈, 空则下溢;不空则作2)
  2. X=S(TOP),(退栈后的元素赋给X)
  3. TOP=TOP-1,结束(栈指针减1,指向栈顶)

算法实现

# -*- coding:utf-8 -*-

__author__ = '苦叶子'


class Stack:
    def __init__(self, size=30):
        # 初始化堆栈大小
        self.size = size        

        # 初始化堆栈列表
        self.stack = []        
        
        # 初始化堆栈默认top值
        self.top = -1

    # 设置堆栈大小
    def set_size(self, size):
        self.size = size    

    # 判断堆栈是否为空
    def is_empty(self):
        res = False
        if self.top == -1:
            res = True

        return res    
        
    # 判断堆栈是否满了
    def is_full(self):
        res = False
        if self.top + 1 == self.size:
            res = True

        return res    
    
    # 打印堆栈里所有内容
    def show(self):
        print(self.stack)    # 入栈
    def push(self, obj):
        if self.is_full():            
            raise Exception("堆栈满啦……")        
        else:
            self.stack.append(obj)
            self.top += 1

    # 出栈
    def pop(self):
        if self.is_empty():     
            raise Exception("堆栈是空的……")
        else:
            self.top -= 1
            return self.stack.pop()
        
        
if __name__ == "__main__":

    print("堆栈实现示例")    
    # 初始一个长度为5的堆栈实例
    stack = Stack(5)    
    
    # 入栈 整数1-5
    for index in range(1, 6):
        stack.push(index)    

    # 打印下堆栈的内容
    stack.show()    
    
    # 出栈, data的值应该为5
    data = stack.pop()
    print(data)    
    
    # 打印下堆栈的内容,此时应该是[1,2,3,4]
    stack.show()

小结

在本示例中我们使用了python list的特性,实现了堆栈的算法原理,大家可以尝试进一步完善。

原文发布于微信公众号 - 开源优测(DeepTest)

原文发表时间:2017-07-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏写代码的海盗

scala与java之间的那些事

  scala与java之间的关系,我认为可以用一句话来开头:scala来源于java,但又高于java。   scala的设计者Martin Odersky就...

37450
来自专栏码匠的流水账

聊聊storm trident的state

storm-2.0.0/storm-client/src/jvm/org/apache/storm/trident/state/StateType.java

24840
来自专栏增长技术

采用现代Objective-C

多年来,Objective-C语言已经有了革命性的发展。虽然核心理念和实践保持不变, 但语言中的部分内容经历了重大的变化和改进。现代化的Objective-C在...

8930
来自专栏hbbliyong

一个小程序引发的思考

   既然是一个小程序引发的思考,那么我们就先看看这个小程序,看看他有何神奇之处: namespace ConsoleApplication1 { cl...

25040
来自专栏刘望舒

设计模式(九)模版方法模式

1.模版方法模式简介 模版方法模式介绍 在软件开发中,有时会遇到类似的情况,某个方法的实现需要多个步骤,其中有些步骤是固定的,而有些步骤并不固定,存在可变性。为...

20660
来自专栏F_Alex

数据结构与算法(六)-背包、栈和队列

  前言:许多基础数据类型都和对象的集合有关。具体来说,数据类型的值就是一组对象的集合,所有操作都是关于添加、删除或是访问集合中的对象。而且有很多高级数据结构都...

12740
来自专栏java工会

面试官最喜欢问的十道java面试题

20380
来自专栏码代码的陈同学

JVM 栈和栈帧

对于没有深度递归的函数来说,无需担心上篇文章中的算法。当知道正在处理数据集有限时,我会使用这种简单的基本递归形式。由于你并不知道在应用程序中会处理多少数据,因此...

78290
来自专栏码匠的流水账

聊聊flink的SourceFunction

flink-streaming-java_2.11-1.6.2-sources.jar!/org/apache/flink/streaming/api/func...

22020
来自专栏黑泽君的专栏

【Java面试复习经典】传智播客Java就业班入学测试题及答案解析(2014年版)

39020

扫码关注云+社区

领取腾讯云代金券