Python数据结构之栈、队列的实现代码分享

1. 栈

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈(Stack)是限制插入和删除操作只能在一个位置进行的表，该位置是表的末端，称为栈的顶(top)。栈的基本操作有PUSH(入栈)和POP(出栈)。栈又被称为LIFO(后入先出)表。

1.1 栈的实现

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 检查程序中成对的符号

程序的语法错误经常是由缺少一个符号造成的。可用栈来检查符号是否成对。做一个空栈，如果字符是开放符号('({[')则将其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 进制转换

十进制转换二进制：把十进制转成二进制一直分解至商数为0。从最底左边数字开始读，之后读右边的数字，从下读到上。

来自《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)，使用一个栈，见到一个数时入栈，遇到一个运算符时就作用于从栈弹出的两个元素，将结果弹入栈中。

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

来自《Problem Solving with Algorithms and Data Structures》的图片：

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)

2 队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列(queue)也是表，使用队列时插入和删除在不同的端进行。队列的基本操作是Enqueue(入队)，在表的末端(rear)插入一个元素，还有出列(Dequeue)，删除表开头的元素。

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)

来源：http://www.cnblogs.com/linxiyue/p/3556875.html