Python 是一种面向对象解释型计算机程序设计语言, 由 Guido van Rossum 于 1989 年底发明, 第一个公开发行版发行于 1991 年 Python 语法简洁而清晰, 具有丰富和强大的类库它常被昵称为胶水语言, 它能够把用其他语言制作的各种模块 (尤其是 C/C++) 很轻松地联结在一起
这篇文章主要介绍了 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.phperz.com/article/18/0218/361495.html