栈和队列数据结构的基本概念及其相关的Python实现

时间:2022-08-29 09:16:08

先来回顾一下队列的基本概念:

相同点:从"数据结构"的角度看,它们都是线性结构,即数据元素之间的关系相同。

不同点:栈(Stack)是限定只能在表的一端进行插入和删除操作的线性表。 队列(Queue)是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。它们是完全不同的数据类型。除了它们各自的基本操作集不同外,主要区别是对插入和删除操作的"限定"。

栈必须按"后进先出"的规则进行操作:比如说,小学老师批改学生的作业,如果不打乱作业本的顺序的话,那么老师批改的第一份作业一定是最后那名同学交的那份作业,如果把所有作业本看作是一个栈中的元素,那么最后一个同学交的作业本就是栈顶元素,而第一个同学交的,也就是最低端的作业本,就是栈底元素,这就是对栈的读取规则。

而队列必须按"先进先出"的规则进行操作:打个比方,一些人去银行办理业务,一定是先去排队的最先得到服务,当然他也是第一个走出银行的(假设这些人都在一个窗口排队)。如果把所有这些等候服务的人看作是队的元素,第一个人就是对头元素,相应的,最后一个人就是队尾元素。这是队的读取规则。


Python实现栈,这是Python核心编程里的一个例子:

?
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
49
50
51
52
53
54
#!/usr/bin/env python
 
#定义一个列表来模拟栈
stack = []
 
#进栈,调用列表的append()函数加到列表的末尾,strip()没有参数是去掉首尾的空格
def pushit():
  stack.append(raw_input('Enter new string: ').strip())
 
#出栈,用到了pop()函数
def popit():
  if len(stack) == 0:
    print 'Cannot pop from an empty stack!'
  else:
    print 'Removed [', stack.pop(), ']'
 
#编历栈
def viewstack():
  print stack
 
#CMDs是字典的使用
CMDs = {'u': pushit, 'o': popit, 'v': viewstack}
 
#pr为提示字符
def showmenu():
  pr = """
  p(U)sh
  p(O)p
  (V)iew
  (Q)uit
    Enter choice: """
 
  while True:
    while True:
      try:
        #先用strip()去掉空格,再把第一个字符转换成小写的
        choice = raw_input(pr).strip()[0].lower()
      except (EOFError, KeyboardInterrupt, IndexError):
        choice = 'q'
 
      print '\nYou picked: [%s]' % choice
      if choice not in 'uovq':
        print 'Invalid option, try again'
      else:
        break
 
#CMDs[]根据输入的choice从字典中对应相应的value,比如说输入u,从字典中得到value为pushit,执行pushit()进栈操作
    if choice == 'q':
      break
    CMDs[choice]()
 
#判断是否是从本文件进入,而不是被调用
if __name__ == '__main__':
  showmenu()

 

用Python实现队列:

?
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
#!/usr/bin/env python
 
queue = []
 
def enQ():
  queue.append(raw_input('Enter new string: ').strip())
 
#调用list的列表的pop()函数.pop(0)为列表的第一个元素
def deQ():
  if len(queue) == 0:
    print 'Cannot pop from an empty queue!'
  else:
    print 'Removed [', queue.pop(0) ,']'
 
def viewQ():
  print queue
 
CMDs = {'e': enQ, 'd': deQ, 'v': viewQ}
 
def showmenu():
  pr = """
  (E)nqueue
  (D)equeue
  (V)iew
  (Q)uit
    Enter choice: """
 
  while True:
    while True:
      try:
        choice = raw_input(pr).strip()[0].lower()
      except (EOFError, KeyboardInterrupt, IndexError):
        choice = 'q'
 
      print '\nYou picked: [%s]' % choice
      if choice not in 'devq':
        print 'Invalid option, try again'
      else:
        break
    if choice == 'q':
      break
    CMDs[choice]()
 
if __name__ == '__main__':
  showmenu()