【原】[快學(xué)Python3]數(shù)據(jù)結(jié)構(gòu)-堆棧

開源優(yōu)測(cè) 2021-12-09

展開全文

概述

什么是堆棧，簡(jiǎn)單而言：后進(jìn)先出。

算法原理

進(jìn)棧（PUSH）算法

若TOP≥n時(shí)，則給出溢出信息，作出錯(cuò)處理（進(jìn)棧前首先檢查棧是否已滿，滿則溢出；不滿則作2）
置TOP=TOP+1（棧指針加1，指向進(jìn)棧地址）
S(TOP)=X，結(jié)束（X為新進(jìn)棧的元素）

退棧（POP）算法

若TOP≤0，則給出下溢信息，作出錯(cuò)處理(退棧前先檢查是否已為空棧，空則下溢；不空則作2)
X=S(TOP)，（退棧后的元素賦給X）
TOP=TOP-1，結(jié)束（棧指針減1，指向棧頂）

算法實(shí)現(xiàn)

# -*- coding:utf-8 -*-

__author__ = '苦葉子'


class Stack:
    def __init__(self, size=30):
        # 初始化堆棧大小
        self.size = size        

        # 初始化堆棧列表
        self.stack = []        
        
        # 初始化堆棧默認(rèn)top值
        self.top = -1

    # 設(shè)置堆棧大小
    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    
    
    # 打印堆棧里所有內(nèi)容
    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("堆棧實(shí)現(xiàn)示例")    
    # 初始一個(gè)長(zhǎng)度為5的堆棧實(shí)例
    stack = Stack(5)    
    
    # 入棧 整數(shù)1-5
    for index in range(1, 6):
        stack.push(index)    

    # 打印下堆棧的內(nèi)容
    stack.show()    
    
    # 出棧, data的值應(yīng)該為5
    data = stack.pop()
    print(data)    
    
    # 打印下堆棧的內(nèi)容，此時(shí)應(yīng)該是[1,2,3,4]
    stack.show()