2022年 11月 3日

python实现栈

python-栈的实现
栈(Stack)的定义:只允许在一端进行插入或者删除操作的线性表。
栈顶(Top):线性表允许插入和删除的那一端。
栈底(Bottom):固定的，不允许进行插入和删除的那一端。
空栈：不含任何元素的空表。

这里借用一个百度百科的图片展示入栈和出栈的过程：
在这里插入图片描述栈是后入先出（LIFO，last-in-first-out）的数据结构，假设栈中原始数据为(2,7,1)
该图展示了8和2依次入栈(Push())
以及(2,8,1)依次出栈(Pop())的过程。
栈的基本操作：
IniStack():初始化一个空栈
isempty():判空
isfull():判满
Push():若栈未满，则入栈
Pop():若栈非空，则出栈
GetTop():获取栈顶元素

顺序栈的实现：

# 后进先出
class myStack():
    def __init__(self,size):
        self.size=size  #栈的大小
        self.stack=[]	#定义一个空栈
        self.top=-1		#指示栈的存储情况，初始为-1，表示空栈，每入栈一个元素，top增加1，每出栈一个元素，top减少1

    def push(self, x): # 入栈之前检查栈是否已满
        if self.isfull():
            print("stack is full")
            return False
        else:
            self.stack.append(x)
            self.top = self.top + 1
            return True

    def pop(self):# 出栈之前检查栈是否为空
        if self.isempty():
            print("stack is empty")
            return False
        else:
            self.top = self.top - 1
            self.stack.pop()
            return True
    def gettop(self):
        if self.top!=-1:
            return self.stack[self.top]
    def isfull(self):
        return self.top+1 == self.size
    def isempty(self):
        return self.top == '-1'
    def showStack(self):
        print(self.stack)


s=myStack(10)
for i in range(10):
    s.push(i)
s.showStack()
print(s.gettop())

s.push("100")
for i in range(6):
    s.pop()
s.showStack()
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47

输出为：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
9
stack is full
[0, 1, 2, 3]
  • 1
  • 2
  • 3
  • 4

需要注意的地方：
1)入栈的时候：元素先入栈,top再增1；出栈时：top先减1，元素后出栈
2)top初值为-1表示空栈，top+1==size表示满栈
在这里插入图片描述共享栈：

在这里插入图片描述利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。
两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=maxSize时1号栈为空，仅当两个栈顶相邻时栈满:top1-top0==1
入栈时，top0先加1再赋值；top1先减1再赋值
定义共享栈：

class myStack():
    def __init__(self,maxSize):
        self.stack0=[]	
        self.stack1=[]
        self.top0=-1
        self.top1=maxSize
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

其他方法对照顺序栈即可。
链栈：
采用链式存储结构的栈，不存在栈满溢出的情况，便于节点的插入和删除，通常用单链表实现，并规定所有的操作都是在表头进行的。
下图的链栈没有头结点，Lhead指向栈顶元素。
在这里插入图片描述