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

更新時間：2015年08月24日 15:54:32 作者：buaa_shang

這篇文章主要介紹了棧和隊列數(shù)據(jù)結(jié)構(gòu)的基本概念及其相關(guān)的Python實現(xiàn),先進先出和后進先出的知識也已經(jīng)成為了計算機學習中的老生常談了:D需要的朋友可以參考下

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

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

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

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

而隊列必須按"先進先出"的規(guī)則進行操作：打個比方，一些人去銀行辦理業(yè)務，一定是先去排隊的最先得到服務，當然他也是第一個走出銀行的（假設(shè)這些人都在一個窗口排隊）。如果把所有這些等候服務的人看作是隊的元素，第一個人就是對頭元素，相應的，最后一個人就是隊尾元素。這是隊的讀取規(guī)則。

用Python實現(xiàn)棧，這是Python核心編程里的一個例子:

#!/usr/bin/env python 
 
#定義一個列表來模擬棧 
stack = [] 
 
#進棧,調(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()去掉空格,再把第一個字符轉(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從字典中對應相應的value,比如說輸入u,從字典中得到value為pushit,執(zhí)行pushit()進棧操作 
    if choice == 'q': 
      break 
    CMDs[choice]() 
 
#判斷是否是從本文件進入,而不是被調(diào)用 
if __name__ == '__main__': 
  showmenu()

用Python實現(xiàn)隊列:

#!/usr/bin/env python 
 
queue = [] 
 
def enQ(): 
  queue.append(raw_input('Enter new string: ').strip()) 
 
#調(diào)用list的列表的pop()函數(shù).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()

您可能感興趣的文章: