python实现栈

系统管理员 2022-10-28 10:10 194阅读 0赞

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

这里借用一个百度百科的图片展示入栈和出栈的过程：  
![在这里插入图片描述][20210205184932713.png_pic_center]栈是后入先出（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()

输出为：

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

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

![在这里插入图片描述][20210205193925268.png]利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。  
两个栈的栈顶指针都指向栈顶元素，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

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

[20210205184932713.png_pic_center]: /images/20221024/3567d5986a8e4275a2a8c77498c15277.png
[20210205192045312.png]: /images/20221024/f4e088cd80174cd78290ef02d4de4ed9.png
[20210205193925268.png]: /images/20221024/676c23fbad7e4a21a636e2693a5a44e8.png
[20210205194944372.png]: /images/20221024/ea6235362e8a4207af8a3aa7e5de411f.png