單棧和雙棧的區別，1.2 棧

1.2.1 棧的概念

棧，就像放在箱子里的衣服，疊成一摞的盤子：先放進去的后拿出來，后放進去的先拿出來（沒準底下的永遠都用不到）

實際的應用場景很多，比如計算數學表達式，遞歸函數等。

1.2.2 棧的基本操作

1.2.3 棧的線性表實現（順序表實現、鏈表實現）

注意到：當用順序表實現堆棧的時候，應該用表尾作為操作的出口，因為如果在開頭加入元素復雜度是O(n),尾部插入是O（1）。

順序表實現

class List_stack():def __init__(self,top=-1,full=20):self._top = topself._stack=[]self.full = fulldef is__full(self):return self.full == self._top+1def is_empty(self):return self._top == -1def put(self,x):if self.full == self._top:print("堆棧已滿")else:self._stack.append(x)self._top += 1def pop(self):if self._top == -1:print("堆棧為空，不可彈出")else:self._top -= 1return self._stack[self._top+1]

鏈表實現（在鏈表的基礎上定義子類）

class Lnote():  #先定義一個最小元素類，節點def __init__(self,ele,next_=None):  #  非常值得注意的是：next_存的不是所謂的下一個節點的地址，而是下一個節點！！！self.next_ = next_self.elem = eleclass Llist(): # 實現節點鏈接對象def __init__(self):self._head = None  # 表頭節點def delete_list(self):self._head = None #  注意，頭部變量一直都是一個節點類def is_empty (self):return self._head ==Nonedef insert_ele(self,i,ele):if i ==0 :#首端插入self._head = Lnote(ele,self._head) # 新的節點，賦予給表頭self.head ，另外：原表頭的表頭變量  給 新表頭的_nextif i != 0:p = self._headwhile p is not None and i>1:  # 找到第 i-1 個元素i -= 1p = p.next_pre = pnew_note = Lnote(ele,pre.next_)pre.next_ = new_notedef list_elements(self):   #  就是一個生成器了，生成器會自動提供遍歷機制（相當一個列表了）比較規范p = self._headwhile p is not None:yield p.elemp = p.next_def print_me(self):for i in self.list_elements():print(i)def pop_me(self,i):p = self._head   #  這一點很重要while p  is not None and i>1:i -= 1p = p.next_if i==0 and p is not None:p0 =pp = p.next_self._head = preturn p0.elem else:p.next_ =p.next_.next_self._head = pdef  find_it(self,n):  #  找到第一個值，第二個為n的元素？利用生成器阿for i ,j in enumerate(self.list_elements()):  # 生成器可以看成 既定列表 牛逼if n == j :print(i)

單棧和雙棧的區別、子類：

#  棧的鏈表實現
#  由鏈表的表頭為棧的進出口，
#因為top指向無法往回，即指針無法向棧底運動from noteList import Llistclass l2_stack(Llist):def __init__(self):super().__init__()self._data = Llist()def is_empty(self):return self._data._head ==Nonedef push(self,ele):self._data.insert_ele(0,ele)def pop(self):if self._data._head ==None:print("棧內無元素")else:return self._data.pop_me(0)

1.2.4 練習題

1. 括號匹配

p140

2. 表達式的計算

p143

棧字取名的意思。3. 棧與遞歸

p151