棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)的基本概念及其相關(guān)的Python實(shí)現(xiàn)

先來回顧一下棧和隊(duì)列的基本概念：

相同點(diǎn)：從"數(shù)據(jù)結(jié)構(gòu)"的角度看，它們都是線性結(jié)構(gòu)，即數(shù)據(jù)元素之間的關(guān)系相同。

不同點(diǎn)：棧（Stack）是限定只能在表的一端進(jìn)行插入和刪除操作的線性表。 隊(duì)列（Queue）是限定只能在表的一端進(jìn)行插入和在另一端進(jìn)行刪除操作的線性表。它們是完全不同的數(shù)據(jù)類型。除了它們各自的基本操作集不同外，主要區(qū)別是對(duì)插入和刪除操作的"限定"。

棧必須按"后進(jìn)先出"的規(guī)則進(jìn)行操作：比如說，小學(xué)老師批改學(xué)生的作業(yè)，如果不打亂作業(yè)本的順序的話，那么老師批改的第一份作業(yè)一定是最后那名同學(xué)交的那份作業(yè)，如果把所有作業(yè)本看作是一個(gè)棧中的元素，那么最后一個(gè)同學(xué)交的作業(yè)本就是棧頂元素，而第一個(gè)同學(xué)交的，也就是最低端的作業(yè)本，就是棧底元素，這就是對(duì)棧的讀取規(guī)則。

而隊(duì)列必須按"先進(jìn)先出"的規(guī)則進(jìn)行操作：打個(gè)比方，一些人去銀行辦理業(yè)務(wù)，一定是先去排隊(duì)的最先得到服務(wù)，當(dāng)然他也是第一個(gè)走出銀行的（假設(shè)這些人都在一個(gè)窗口排隊(duì)）。如果把所有這些等候服務(wù)的人看作是隊(duì)的元素，第一個(gè)人就是對(duì)頭元素，相應(yīng)的，最后一個(gè)人就是隊(duì)尾元素。這是隊(duì)的讀取規(guī)則。
用Python實(shí)現(xiàn)棧，這是Python核心編程里的一個(gè)例子:

'#!/usr/bin/env python
 
#定義一個(gè)列表來模擬棧
stack = []
 
#進(jìn)棧,調(diào)用列表的append()函數(shù)加到列表的末尾,strip()沒有參數(shù)是去掉首尾的空格
def pushit():
  stack.append(raw_input('Enter new string: ').strip())
 
#出棧,用到了pop()函數(shù)
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()去掉空格,再把第一個(gè)字符轉(zhuǎn)換成小寫的
        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[]根據(jù)輸入的choice從字典中對(duì)應(yīng)相應(yīng)的value,比如說輸入u,從字典中得到value為pushit,執(zhí)行pushit()進(jìn)棧操作
    if choice == 'q':
      break
    CMDs[choice]()
 
#判斷是否是從本文件進(jìn)入,而不是被調(diào)用
if __name__ == '__main__':
  showmenu()

用Python實(shí)現(xiàn)隊(duì)列:    
#!/usr/bin/env python
 
queue = []
 
def enQ():
  queue.append(raw_input('Enter new string: ').strip())
 
#調(diào)用list的列表的pop()函數(shù).pop(0)為列表的第一個(gè)元素
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()