模擬棧

Stack() 創(chuàng)建一個(gè)空的新棧。 它不需要參數(shù)，并返回一個(gè)空棧。 push(item)將一個(gè)新項(xiàng)添加到棧的頂部。它需要 item 做參數(shù)并不返回任何內(nèi)容。 pop() 從棧中刪除頂部項(xiàng)。它不需要參數(shù)并返回 item 。棧被修改。 peek() 從棧返回頂部項(xiàng)，但不會(huì)刪除它。不需要參數(shù)。 不修改棧。 isEmpty() 測(cè)試棧是否為空。不需要參數(shù)，并返回布爾值。 size() 返回棧中的 item 數(shù)量。不需要參數(shù)，并返回一個(gè)整數(shù)。

class Stack(): def __init__(self): self.items = [] def push(self,item): self.items.append(item) def pop(self): return self.items.pop() def peek(self): return len(self.items) - 1 def isEmpty(self): return self.items == [] def size(self): return len(self.items)s = Stack()s.push(1)s.push(2)s.push(3)print(s.pop())print(s.pop())print(s.pop())print(s.isEmpty())

模擬隊(duì)列

Queue() 創(chuàng)建一個(gè)空的新隊(duì)列。 它不需要參數(shù)，并返回一個(gè)空隊(duì)列。 enqueue(item) 將新項(xiàng)添加到隊(duì)尾。 它需要 item 作為參數(shù)，并不返回任何內(nèi)容。 dequeue() 從隊(duì)首移除項(xiàng)。它不需要參數(shù)并返回 item。 隊(duì)列被修改。 isEmpty() 查看隊(duì)列是否為空。它不需要參數(shù)，并返回布爾值。 size() 返回隊(duì)列中的項(xiàng)數(shù)。它不需要參數(shù)，并返回一個(gè)整數(shù)。

class Queue(): def __init__(self): self.items = [] def enqueue(self,item): self.items.insert(0,item) def dequeue(self): return self.items.pop() def isEmpty(self): return self.items == [] def size(self): return len(self.items)q = Queue()q.enqueue(1)q.enqueue(2)q.enqueue(3)print(q.dequeue())print(q.dequeue())print(q.dequeue())

案例：燙手山芋

燙手山芋游戲介紹：6個(gè)孩子圍城一個(gè)圈，排列順序孩子們自己指定。第一個(gè)孩子手里有一個(gè)燙手的山芋，需要在計(jì)時(shí)器計(jì)時(shí)1秒后將山芋傳遞給下一個(gè)孩子，依次類推。規(guī)則是，在計(jì)時(shí)器每計(jì)時(shí)7秒時(shí)，手里有山芋的孩子退出游戲。該游戲直到剩下一個(gè)孩子時(shí)結(jié)束，最后剩下的孩子獲勝。請(qǐng)使用隊(duì)列實(shí)現(xiàn)該游戲策略，排在第幾個(gè)位置最終會(huì)獲勝。

準(zhǔn)則：隊(duì)頭孩子的手里永遠(yuǎn)要有山芋。

queue = Queue()kids = [’A’,’B’,’C’,’D’,’E’,’F’]#將六個(gè)孩子添加到隊(duì)列中，A是隊(duì)頭位置的孩子for kid in kids: queue.enqueue(kid)while queue.size() > 1: #在7秒之內(nèi)山芋會(huì)被傳遞6次 for i in range(6): kid = queue.dequeue() queue.enqueue(kid) queue.dequeue()print(’獲勝者為：’,queue.dequeue())

模擬雙端隊(duì)列

同同列相比，有兩個(gè)頭部和尾部。可以在雙端進(jìn)行數(shù)據(jù)的插入和刪除，提供了單數(shù)據(jù)結(jié)構(gòu)中棧和隊(duì)列的特性

Deque() 創(chuàng)建一個(gè)空的新deque。它不需要參數(shù)，并返回空的deque。 addFront(item) 將一個(gè)新項(xiàng)添加到deque的首部。它需要item參數(shù)并不返回任何內(nèi)容。 addRear(item) 將一個(gè)新項(xiàng)添加到deque的尾部。它需要item參數(shù)并不返回任何內(nèi)容。 removeFront() 從deque中刪除首項(xiàng)。它不需要參數(shù)并返回item。deque被修改。 removeRear() 從deque中刪除尾項(xiàng)。它不需要參數(shù)并返回item。deque被修改。 isEmpty() 測(cè)試deque是否為空。它不需要參數(shù)，并返回布爾值。 size() 返回deque中的項(xiàng)數(shù)。它不需要參數(shù)，并返回一個(gè)整數(shù)。

案例：回文檢查

回文是一個(gè)字符串，讀取首尾相同的字符，例如，radar toot madam。

def isHuiWen(s): ex = True q = Dequeue() # 將字符串的每一個(gè)字符添加到雙端隊(duì)列中 for ch in s: q.addFront(ch) for i in range(len(s) // 2): font = q.removeFront() rear = q.removeRear() if font != rear: ex = False break return ex

模擬鏈表

. is_empty()：鏈表是否為空 . length()：鏈表長度 . travel()：遍歷整個(gè)鏈表 . add(item)：鏈表頭部添加元素 . append(item)：鏈表尾部添加元素 . insert(pos, item)：指定位置添加元素 . remove(item)：刪除節(jié)點(diǎn) . search(item)：查找節(jié)點(diǎn)是否存在

結(jié)點(diǎn)對(duì)象：

class Node(): def __init__(self,item): self.item = item self.next = None

鏈表對(duì)象：

class Link(): #構(gòu)建出一個(gè)空的鏈表 def __init__(self): self._head = None #永遠(yuǎn)指向鏈表中的頭節(jié)點(diǎn) #想鏈表的頭部插入節(jié)點(diǎn) def add(self,item): node = Node(item) node.next = self._head self._head = node def travel(self): cur = self._head #鏈表為空則輸出‘鏈表為空’ if self._head == None: print(’鏈表為空！’) while cur: print(cur.item) cur = cur.next def isEmpty(self): return self._head == None def length(self): cur = self._head count = 0 while cur: count += 1 cur = cur.next return count def search(self,item): cur = self._head find = False while cur: if cur.item == item:find = Truebreak cur = cur.next return find def append(self,item): node = Node(item) #鏈表為空的情況 if self._head == None: self._head = node return cur = self._head #頭節(jié)點(diǎn) pre = None #cur的前一個(gè)節(jié)點(diǎn) while cur: pre = cur cur = cur.next pre.next = node def insert(self,pos,item): node = Node(item) if pos < 0 or pos > self.length(): print(’重新給pos賦值?。?！’) return cur = self._head pre = None for i in range(pos): pre = cur cur = cur.next pre.next = node node.next = cur def remove(self,item): cur = self._head pre = None if self._head == None:#鏈表為空 print(’鏈表為空，沒有可刪除的節(jié)點(diǎn)??！1’) return #刪除的是第一個(gè)節(jié)點(diǎn)的情況 if self._head.item == item: self._head = self._head.next return #刪除的是非第一個(gè)節(jié)點(diǎn)的情況 while cur: pre = cur cur = cur.next if cur.item == item:pre.next = cur.nextreturn

以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持好吧啦網(wǎng)。