栈的顺序存储结构（Python版）

84 阅读 0 评论 56 点赞

我是靠谱客的博主拼搏流沙，最近开发中收集的这篇文章主要介绍栈的顺序存储结构（Python版），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

何为“栈”：

要搞清楚这个概念，首先要明白”栈“原来的意思，如此才能把握本质。"栈“者,存储货物或供旅客住宿的地方,可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方，所以才有进栈、出栈的说法。

栈的定义：

栈是一个后进先出的线性表，它要求只在表尾进行删除和插入操作。所谓栈是一种特殊的线性表（顺序表和链表），但是它在操作上有一些特殊的要求和限制；栈的元素必须后进先出；栈的操作只能在这个线性表的表尾进行；对于栈来说，这个表尾称为栈的栈顶；相应的表头称为栈底；栈的插入操作，称作进栈，也称为压栈；栈的出栈称为出栈，或者弹栈；

栈的顺序存储结构：

因为栈的本质是一个线性表，线性表有两种存储形式，那么栈有也有两种分为栈的顺序存储结构和栈的链式存储结构；
最开始，栈中不含有任何数据，叫做空栈，此时栈顶就是栈底；然后数据从栈底进入，栈顶栈底分离，栈的容量变大；数据出栈时从栈顶弹出，整个栈的容量变小。

首先，我们先来了解栈的顺序存储结构如何去实现

# 栈的顺序存储
# 栈的初始化
class SequenceStack:
    def __init__(self):
        self.MaxStrackSize = 10    # 最大存储单元个数
        self.s = [None for x in range(0,self.MaxStrackSize)]
        self.top = -1

# 输出当前栈长度
    def GetStackLength(self):
        if self.IsEmptyStack():
            print('栈为空')
            return
        else:
            return self.top+1

# 判断栈是否为空
    def IsEmptyStack(self):
        if self.top == -1:
            itop = True
        else:
            itop = False

# 通过输入元素创建一个顺序栈
    def CreatStackByInput(self):
        data = input('请输入元素，以#结束输入:')
        while data!='#':
            self.PushStack(data)
            data = input('请继续输入元素，以#结束输入：')

# 入栈函数
    def PushStack(self,x):
        if self.top < self.MaxStrackSize-1:
            self.top = self.top+1
            self.s[self.top] = x
        else:
            print('栈满')
            return

# 出栈函数
    def PopStach(self):
        if self.IsEmptyStack():
            print('栈空')
            return
        else:
            itop = self.top
            self.top = self.top-1
            return self.s[itop]

# 遍历栈内元素
    def StcakTrave(self):
        if self.IsEmptyStack():
            print('栈空')
            return
        else:
            for i in range(0,self.top+1):
                print(self.s[i],end='')

# 编写测试函数
ss = SequenceStack()
ss.CreatStackByInput()
ss.StcakTrave()
ss.PopStach()
ss.StcakTrave()