1. 棧

棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。

棧(Stack)是限制插入和刪除操作只能在一個位置進行的表，該位置是表的末端，稱為棧的頂(top)。棧的基本操作有PUSH(入棧)和POP(出棧)。棧又被稱為LIFO(后入先出)表。

1.1 棧的實現(xiàn)

class Stack(object):  def __init__(self):    self.stack=[]  def isEmpty(self):    return self.stack==[]  def push(self,item):    self.stack.append(item)  def pop(self):    if self.isEmpty():      raise IndexError,'pop from empty stack'    return self.stack.pop()  def peek(self):    return self.stack[-1]  def size(self):    return len(self.stack)

1.2 棧應用

1.2.1 檢查程序中成對的符號

程序的語法錯誤經(jīng)常是由缺少一個符號造成的。可用棧來檢查符號是否成對。做一個空棧，如果字符是開放符號('({[')則將其push棧中。如果符號是個閉合符號(')]}'),則當棧空時報錯，對應'()}'的錯誤。否則，將棧pop，如果彈出的符號不是對應的開放符號，則報錯，對應'(}'的錯誤。文件末尾，如果棧為空，則報錯，對應'({}'的錯誤。

def match(i,j):  opens='([{'  closes=')]}'  return opens.index(i)==closes.index(j)def syntaxChecker(string):  stack=Stack()  balanced=True  for i in string:    if i in '([{':      stack.push(i)    elif i in ')]}':      if stack.isEmpty():        balanced=False        break      else:        j=stack.pop()        if not match(j,i):          balanced=False          break  if not stack.isEmpty():    balanced=False  return balanced

1.2.2 進制轉(zhuǎn)換

十進制轉(zhuǎn)換二進制：把十進制轉(zhuǎn)成二進制一直分解至商數(shù)為0。從最底左邊數(shù)字開始讀，之后讀右邊的數(shù)字，從下讀到上。

來自《Problem Solving with Algorithms and Data Structures》的圖片：

代碼：

def decimal_to_bin(dec):  stack=Stack()  cur=dec  while cur>0:    a=cur%2    cur=cur/2    stack.push(a)  binstr=''  while not stack.isEmpty():    binstr+=str(stack.pop())  return binstr

1.2.3 后綴記法

后綴記法(postfix)，使用一個棧，見到一個數(shù)時入棧，遇到一個運算符時就作用于從棧彈出的兩個元素，將結(jié)果彈入棧中。

(7+8)/(3+2)可以寫作7 8 + 3 2 + /

來自《Problem Solving with Algorithms and Data Structures》的圖片：