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

概述

什么是堆栈，简单而言：后进先出。

算法原理

若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作2）

置TOP=TOP+1（栈指针加1，指向进栈地址）

S(TOP)=X，结束（X为新进栈的元素）

若TOP≤0大数据堆栈，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作2)

X=S(TOP)，（退栈后的元素赋给X）

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

扫一扫加我微信，入群一起讨论交流各种开源测试技术、工具、经验和解决方案。

（编辑：92站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!