一桩砰、棧

棧（stack）又名堆棧悍及，它是一種運(yùn)算受限的線性表。其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算墩崩。這一端被稱為棧頂昧绣，相對地规肴，把另一端稱為棧底。向一個棧插入新元素又稱作進(jìn)棧夜畴、入椡先校或壓棧，它是把新元素放到棧頂元素的上面贪绘，使之成為新的棧頂元素兑牡；從一個棧刪除元素又稱作出棧或退棧税灌，它是把棧頂元素刪除掉均函，使其相鄰的元素成為新的棧頂元素。

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

• 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)

• 2. 棧的應(yīng)用

1. 檢查程序中成對的符號
   程序的語法錯誤經(jīng)常是由缺少一個符號造成的」プ撸可用棧來檢查符號是否成對殷勘。做一個空棧，如果字符是開放符號('({[')則將其push棧中陋气。如果符號是個閉合符號(')]}'),則當(dāng)椑头停空時報錯，對應(yīng)'()}'的錯誤巩趁。否則痒玩，將棧pop淳附，如果彈出的符號不是對應(yīng)的開放符號，則報錯蠢古，對應(yīng)'(}'的錯誤奴曙。文件末尾，如果棧為空草讶，則報錯洽糟，對應(yīng)'({}'的錯誤。

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

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

   
   
   十進(jìn)制轉(zhuǎn)二進(jìn)制計算

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

3. 后綴記法
   后綴記法(postfix)薪介，使用一個棧，見到一個數(shù)時入棧越驻，遇到一個運(yùn)算符時就作用于從棧彈出的兩個元素汁政，將結(jié)果彈入棧中。
   (7+8)/(3+2)可以寫作7 8 + 3 2 + /

   
   
   后綴記法

def infixtoPostfix(infix):
  a={}
  a['*']=3
  a['/']=3
  a['+']=2
  a['-']=2
  a['(']=1
  stack=Stack()
  post=''
  for i in infix:
    if i not in a and i!=')':
      post+=i
    elif i=='(':
      stack.push(i)
    elif i==')':
      top=stack.pop()
      while top!='(':
        post+=top
        top=stack.pop()
    else:     
      while not stack.isEmpty() and a[i]<=a[stack.peek()]:
        post+=stack.pop()
      stack.push(i)
  while not stack.isEmpty():
    post+=stack.pop()
  return post
           
def postfixExp(postfix):
  stack=Stack()
  postlist=postfix.split()
  for i in postlist:
    if i not in '+-*/':
      stack.push(i)
    else:
      a=stack.pop()
      b=stack.pop()
      result=math(i,b,a)
      stack.push(result)
  return stack.pop()
def math(x,y,z):
  if x=='+':
    return float(y)+float(z)
  if x=='-':
    return float(y)-float(z)
  if x=='*':
    return float(y)*float(z)
  if x=='/':
    return float(y)/float(z)

二缀旁、隊列

隊列是一種特殊的線性表记劈，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作并巍，和棧一樣目木，隊列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊尾履澳，進(jìn)行刪除操作的端稱為隊頭嘶窄。
隊列(queue)也是表怀跛，使用隊列時插入和刪除在不同的端進(jìn)行距贷。隊列的基本操作是Enqueue(入隊)，在表的末端(rear)插入一個元素吻谋，還有出列(Dequeue)忠蝗，刪除表開頭的元素。

• 1. 隊列的實現(xiàn)

class Queue(object):
  def __init__(self):
    self.queue=[]
  def isEmpty(self):
    return self.queue==[]
  def enqueue(self,x):
    self.queue.append(x)
  def dequeue(self):
    if self.queue:
      a=self.queue[0]
      self.queue.remove(a)
      return a
    else:
      raise IndexError,'queue is empty'
  def size(self):
    return len(self.queue)