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)
总结
以上就是本文关于Python数据结构之栈、队列的实现代码分享的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com