先來(lái)回顧一下棧和隊(duì)列的基本概念：
相同點(diǎn)：從"數(shù)據(jù)結(jié)構(gòu)"的角度看，它們都是線(xiàn)性結(jié)構(gòu)，即數(shù)據(jù)元素之間的關(guān)系相同。
不同點(diǎn)：棧（Stack）是限定只能在表的一端進(jìn)行插入和刪除操作的線(xiàn)性表。 隊(duì)列（Queue）是限定只能在表的一端進(jìn)行插入和在另一端進(jìn)行刪除操作的線(xiàn)性表。它們是完全不同的數(shù)據(jù)類(lèi)型。除了它們各自的基本操作集不同外，主要區(qū)別是對(duì)插入和刪除操作的"限定"。
棧必須按"后進(jìn)先出"的規(guī)則進(jìn)行操作：比如說(shuō)，小學(xué)老師批改學(xué)生的作業(yè)，如果不打亂作業(yè)本的順序的話(huà)，那么老師批改的第一份作業(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è)列表來(lái)模擬棧 stack = [] #進(jìn)棧,調(diào)用列表的append()函數(shù)加到列表的末尾,strip()沒(méi)有參數(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)換成小寫(xiě)的 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,比如說(shuō)輸入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() 新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
