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