【原】棧的內(nèi)涵定義

算法與編程之美 2025-06-17 發(fā)布于四川

展開(kāi)全文

1 問(wèn)題

①棧的內(nèi)涵定義。

②棧的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算算法的實(shí)現(xiàn)。

③如順序棧的應(yīng)用算法（實(shí)例）

2 方法

詳細(xì)閱讀并理解教材得知：棧是一種只能在同一端進(jìn)行插入或刪除操作的線性表，并且棧分為棧頂（top）和棧底（base）。棧的插入操作通常叫作進(jìn)棧、入棧和壓棧（push），棧的刪除操作通常稱(chēng)為退棧和出棧（pop），當(dāng)棧中沒(méi)有數(shù)據(jù)元素時(shí)叫作空棧。（下圖為棧在日常生活中的實(shí)例）

通過(guò)教材得知，順序棧的基本算法包括：判斷棧是否為空、將元素壓棧、將元素出棧、獲取棧頂元素和獲取棧的長(zhǎng)度。（代碼如下）

解決算法設(shè)計(jì)思路：利用順序棧品導(dǎo)用戶(hù)輸入的表達(dá)式中的括號(hào)是否配對(duì)（假設(shè)表達(dá)式中可能含有圓括號(hào)、方括號(hào)、花括號(hào)），并用相關(guān)數(shù)據(jù)進(jìn)行檢測(cè)。（運(yùn)行代碼如下）

通過(guò)老師上課講解可知道，棧的使用與線性表的使用相似，可同理思考問(wèn)題。通過(guò)實(shí)驗(yàn)、實(shí)踐等證明提出的方法是有效的，是能夠解決開(kāi)頭提出的問(wèn)題。

代碼清單 1

#構(gòu)造方法

class SqStack:
def __init__(self) :
self.data=[] #存放棧中元素，初始為空
#判斷棧是否為空
def empty(self):
if len(self.data)==0:
return True
return False
#進(jìn)棧
def push(self,a): #元素a進(jìn)棧
self.data.append(a) #直接用append加入
#出棧
def pop(self):
assert not self.empty() #檢測(cè)棧為空
return self.data.pop()
#獲取棧頂元素
def gettop(self):
assert not self.empty()
return self.data[-1]
#棧的長(zhǎng)度
def long(self):
n = len(self.data)
return n

3 結(jié)語(yǔ)

針對(duì)上述四個(gè)問(wèn)題，通過(guò)自學(xué)，自查方法，時(shí)能懂得大概含義，再加上上課聽(tīng)老師的思路，能夠更加理解其根本含義。通過(guò)實(shí)踐檢驗(yàn)的實(shí)驗(yàn)，證明該方法是有效的，本文的方法在自查有許多獲取只是途徑?jīng)]用上，未來(lái)可以繼續(xù)探討有關(guān)棧的問(wèn)題。