C語言中文網 目錄
首頁 > 編程筆記 > C++筆記 閱讀:659

隊列及特點和應用詳解

與棧一樣,隊列(Queue)也是一種數據結構,它包含一系列元素。但是,隊列訪問元素的順序不是后進先出(LIFO),而是先進先出(FIFO)。隊列中元素的處理就像是站在商店收款臺前排隊等待的顧客:排在最前面的顧客最先結賬。

隊列數據結構常用于計算機操作系統。它們在多用戶/多任務環境中尤為重要,在這種環境中,多個用戶或任務可能同時請求同一資源。例如,打印由隊列控制,因為一次只能打印一個文檔。隊列用于保存由系統用戶提交的打印作業,而打印機則一次處理一個作業。

通信軟件也會使用隊列來保存通過網絡和撥號連接方式接收到的信息。有時,信息傳輸到系統的速度比它能處理的要快,因此在收到信息時會先將其放入隊列中。

順序隊列和鏈隊列

隊列與棧一樣,也可以實現為數組或鏈表。前面介紹過,順序棧與鏈棧相比有兩項優勢,而這樣的優勢在順序隊列與鏈隊列的對比中也同樣存在。實際上,隊列與棧之間的主要區別在于每個結構中數據元素的訪問方式。

隊列操作

隊列和商店收款臺的排隊線一樣,也分前面(以 front 表示)和后面(以 rear 表示),如圖 1 所示。

隊列示意圖
圖 1 隊列示意圖

當一個元素被添加到隊列中時,它被添加到后面。當一個元素從隊列中移除時,它將從前面移除。隊列的兩個主要操作就是入隊(enqueue)和出隊(dequeue)。入隊意味著在隊列的后面插入一個元素,而出隊則意味著從隊列的前面移除一個元素。有若干個算法可以實現這些操作,現在就從最簡單的開始介紹。

假設有一個空的靜態整數隊列,最多能夠保存 3 個值。可以使用該隊列執行入隊操作,示例如下:

enqueue (3);
enqueue (6);
enqueue (9);

圖 2 顯示了執行以上入隊操作之后的隊列狀態。

執行入隊操作之后的隊列狀態
圖 2 執行入隊操作之后的隊列狀態

請注意前面的索引(它是一個持有下標或者指針的變量)總是引用相同的物理元素。而后面的索引則會隨著項目入隊而在數組中移動。現在來看一看出隊操作的執行方式。圖 3 顯示了連續 3 次出隊操作之后的隊列狀態。

出隊操作的執行方式
圖 3 出隊操作的執行方式

在出隊操作中,隊列前面的元素被刪除。這是通過將所有元素向前移動一個位置來完成的。在第一次出隊操作之后,值 3 從隊列中移除,值 6 在前面。在第二次出隊操作之后,值 6 被移除,值 9 在前面。請注意,當只有一個值存儲在隊列中時,該值是 front 和 rear 共同指向的值。

如圖 3 所示,在執行最后的出隊操作之后,隊列變成了空的。通過將表示前面的 front 和表示后面的 rear 兩個索引都設置為 -1,可以表示一個空隊列。

這個算法的問題是效率低下。每當一個項目出隊時,隊列中剩余的項目都被復制到其相鄰元素。隊列中的項目越多,則每次后續的出隊操作所花費的時間就越長。

以下是解決該問題的一種方法:使 front 和 rear 的索引都可以在數組中移動。與以前一樣,當一個項目入隊時,后面的索引被移動以給它生成空間。但是在這個設計中,當一個項目出列時,前面的索引向著隊列后面移動一個元素,這可以從邏輯上將前面的項目從隊列中移除,并且意味著不需要將剩余項目復制到其相鄰的元素。

但是,使用這種方法之后,隨著項目的添加和刪除,隊列會逐漸"爬"向數組的末尾,如圖 4 所示。

解決隊列低效間題的一種設計方案
圖 4 解決隊列低效間題的一種設計方案

這種方法的問題是后面的索引不能超出數組中的最后一個元素。解決的辦法是將數組視為循環而不是線性的。當一個項目移動到一個循環數組的末尾時,它只是簡單地回到了開頭。例如,來看一下如圖 5 所示的隊列。

循環隊列
圖 5 循環隊列

值3位于隊列的后面,值 7 位于隊列的前面。現在,假設要執行入隊操作,將值 4 插入到隊列中。圖 6 顯示了隊列以 rear 表示的尾部如何繞到了數組的開頭。

隊列的尾部繞到了數組的開頭
圖 6 隊列的尾部繞到了數組的開頭

那么,該如何將 rear 標記繞到數組的開頭呢? 一個簡單的方法就是使用 if 語句,示例如下:
if (rear == queueSize - 1)
    rear = 0;
else
    rear++;
另外還有一種方法就是使用求余算術:

rear = (rear + 1) % queueSize;

該語句使用 運算符將 rear 中的值調整到適當的位置。雖然這種方法看起來更優雅,但這兩種方法都可以任意選擇使用。

精美而實用的網站,提供C語言C++STLLinuxShellJavaGo語言等教程,以及socketGCCviSwing設計模式JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo