更新時(shí)間:2023-03-28 來(lái)源:黑馬程序員 瀏覽量:
隊(duì)列和棧是常見的數(shù)據(jù)結(jié)構(gòu),它們都用于存儲(chǔ)和管理數(shù)據(jù),但是它們?cè)诖鎯?chǔ)和訪問(wèn)數(shù)據(jù)的方式上有所不同。
隊(duì)列是一種先進(jìn)先出(FIFO)的數(shù)據(jù)結(jié)構(gòu),類似于排隊(duì)。新的元素被添加到隊(duì)列的尾部,而從隊(duì)列中刪除元素時(shí),總是刪除隊(duì)列頭部的元素。隊(duì)列的常見操作包括入隊(duì)(enqueue)和出隊(duì)(dequeue)。
棧是一種后進(jìn)先出(LIFO)的數(shù)據(jù)結(jié)構(gòu),類似于一摞書。新的元素被添加到棧的頂部,而從棧中刪除元素時(shí),總是刪除棧頂?shù)脑亍5某R姴僮靼ㄈ霔?push)和出棧(pop)。
我們用一段Python代碼來(lái)加以說(shuō)明:
# 隊(duì)列的實(shí)現(xiàn) class Queue: def __init__(self): self.items = [] def enqueue(self, item): self.items.append(item) def dequeue(self): if self.is_empty(): return None return self.items.pop(0) def is_empty(self): return len(self.items) == 0 def size(self): return len(self.items) # 棧的實(shí)現(xiàn) class Stack: def __init__(self): self.items = [] def push(self, item): self.items.append(item) def pop(self): if self.is_empty(): return None return self.items.pop() def is_empty(self): return len(self.items) == 0 def size(self): return len(self.items)
在上面的代碼中,我們使用Python的列表來(lái)實(shí)現(xiàn)隊(duì)列和棧。在隊(duì)列中,我們使用append()方法將元素添加到列表的尾部,并使用pop(0)方法從列表的頭部刪除元素。在棧中,我們使用append()方法將元素添加到列表的末尾,并使用pop()方法從列表的末尾刪除元素。
以下是使用隊(duì)列和棧的示例代碼:
# 使用隊(duì)列實(shí)現(xiàn)廣度優(yōu)先搜索 def bfs(graph, start): visited = set() queue = Queue() queue.enqueue(start) while not queue.is_empty(): vertex = queue.dequeue() if vertex not in visited: visited.add(vertex) for neighbor in graph[vertex]: queue.enqueue(neighbor) return visited # 使用棧實(shí)現(xiàn)深度優(yōu)先搜索 def dfs(graph, start): visited = set() stack = Stack() stack.push(start) while not stack.is_empty(): vertex = stack.pop() if vertex not in visited: visited.add(vertex) for neighbor in graph[vertex]: stack.push(neighbor) return visited
在上面的代碼中,我們使用隊(duì)列實(shí)現(xiàn)了廣度優(yōu)先搜索(BFS),并使用棧實(shí)現(xiàn)了深度優(yōu)先搜索(DFS)。BFS和DFS是圖論中常見的搜索算法,它們可以用來(lái)解決許多問(wèn)題,例如尋找最短路徑或拓?fù)渑判虻取?/p>