Python数据结构——栈、队列的实现(一)
1. 栈
栈(Stack)是限制插入和删除操作只能在一个位置进行的表,该位置是表的末端,称为栈的顶(top)。栈的基本操作有PUSH(入栈)和POP(出栈)。栈又被称为LIFO(后入先出)表。
1.1 栈的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 |
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,如果弹出的符号不是对应的开放符号,则报错,对应‘(}‘的错误。文件末尾,如果栈为空,则报错,对应‘({}‘的错误。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 |
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》的图片:
代码:
1
2
3
4
5
6
7
8
9
10
11 |
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》的图片:
中缀到后缀的转换:当读到一个操作数的时候,放到输出中。读到操作符(+,-,*,/)时,如果栈为空,则压入栈中,否则弹出栈元素放到输出中直到发现优先级更低的元素为止。读到‘(‘,压入栈中,读到‘)‘,弹出栈元素并发到输出中直到发现‘(‘为止。在末尾,将栈元素弹出直到该栈变成空栈。
来自《Problem Solving with Algorithms and Data Structures》的图片:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48 |
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 队列
队列(queue)也是表,使用队列时插入和删除在不同的端进行。队列的基本操作是Enqueue(入队),在表的末端(rear)插入一个元素,还有出列(Dequeue),删除表开头的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13 |
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 ): a = self .queue[ 0 ] self .queue.remove(a) return
a def
size( self ): return
len ( self .queue) |
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。