首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[快学Python3]数据结构-堆栈

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

作者头像
苦叶子
发布2018-04-09 10:34:53
1K0
发布2018-04-09 10:34:53
举报
文章被收录于专栏:开源优测开源优测

概述

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

算法原理

  • 进栈(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的特性,实现了堆栈的算法原理,大家可以尝试进一步完善。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2017-07-14,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 开源优测 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 算法原理
  • 算法实现
  • 小结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档