棧和隊列數據結構的基本概念及其相關的Python實現

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

相同點：從"數據結構"的角度看，它們都是線性結構，即數據元素之間的關系相同。

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

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

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

'#!/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實現隊列:    
#!/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()