數據結構與算法之八 隊列

視頻課堂https://edu.csdn.net/course/play/7621

目標

在本章中，你將學到：

識別隊列的特性

運用不同類型的隊列

運用隊列來解決編程問題

使用散列法存儲和搜索數據

考慮這樣一種情形，你要創建一個有以下請求集的應用程序：

應用程序可被應用于多用戶的請求。

每次，僅處理一個請求。

先到的請求優先被處理。

然而，這些軟件接受請求的速度要遠大于處理請求的速度。

因此需要將請求存儲在隊列中直到被處理。

你如何解決此問題？

你可以通過以這樣的方式存儲請求來解決該問題，即以請求到達的順序來獲取請求。

稱為隊列的數據結構以數據的到達順序來存儲和獲取它們。

隊列也被稱為先入先出隊列（FIFO）。

一個隊列就是含有一組元素的列，這個列中數據從隊列一端添加，然后從隊列另一端刪除。

插入：指將數據添加到隊列中。

假設希望將元素F添加到隊列中。

因為添加操作發生在末端，元素F將添加到元素D之后。

現在元素F變成了末端。

刪除：指的是將元素從隊列中刪除。

數據從前端被刪除。因此，元素B將從隊列中移走。

現在A變成了隊列的前端。

問題描述：

考慮一個銀行的場景。當客戶來到柜臺并輸入請求，就可以得到一個請求號碼。收到請求號碼后，客戶必須等候一段時間。客戶請求需要進入系統隊列，并按照到達的順序獲得處理。你需要實現一種適當的數據存儲機制在系統中存儲這些請求。

隊列的應用

隊列能在多個領域中得到應用，如：

打印機暫存

CPU調度

郵件服務

鍵盤緩沖

電梯

打印機暫存

打印機可能會在短時間內收到多個打印請求。

收到的打印請求頻率要大于處理請求的頻率。

因此，就需要一個臨時存儲機制來按照到達順序存儲打印請求。

在這種情況下，隊列就是最佳選擇，可以按照先到先服務原則存儲打印請求。

CPU 調度

一個 CPU 同一時間只能處理一個請求。

通常， CPU 接受請求的頻率都大于處理請求的頻率。

因此這些請求都按照到達順序暫時存儲在一個隊列中。

當 CPU 有空時，就會從隊列中一個個地取出請求，并處理它們。

一旦一個請求處理完后，就會從隊列中移出。

CPU 就會取出下一個請求，并處理。

在一個分時系統中（ time sharing system ）， CPU 分配給每個請求的時間都 是固定的。

所有的請求都臨時存儲在隊列中。

CPU 一個個地按固定時間處理每個請求。

如果請求在固定時間段中處理完成，這個請求就會從隊列中移出。

如果一個請求沒有在特定的時間段中處理完成，就會被移到隊列的末尾。

CPU 就會處理隊列中的下一個請求，依此類推。

郵件服務

在許多企業中，許多行為都是通過郵件進行的。

但如果郵件服務器下線了，并且還有人要給你發郵件，郵件就會退回給發件 人。

要避免這樣的情況，許多企業實現了一個 郵件備份服務 。

當郵件服務器發生問題時而導致郵件沒有發送成功，這個郵件就被傳送到一 個備份服務器。

備份服務器將郵件臨時存儲在隊列中。

當郵件服務器恢復工作時，所有的郵件會按到達的順序發送給收件人。

鍵盤緩沖

隊列還被用于存儲你在鍵盤上的每一下敲擊。

有時候你通過鍵盤敲擊的數據并不是立即反映在屏幕上。

這是因為當時處理器忙于處理其他任務，無法處理你的請求。

在這種情況下，數據臨時存儲在隊列中，直到處理器開始處理這個請求。

一旦處理器空閑下來，你所有的敲擊都會按照到達的順序顯示在屏幕上。

電梯

一部電梯也使用隊列來存儲用戶的請求。

假設電梯此時在第一層。有個用戶在底層按了電梯按鈕。同時另一個用戶在 二層也按了電梯按鈕。

那么電梯會前去最先按鈕的一層，也就是說，這些請求會按先到先服務的原 則進行處理。

但是，如果一個用戶在底層，另一個用戶在九層 (9 層往↑往↓ ) ，那么無論 誰先按鈕，電梯都會先去底層，因為去底層的 距離更短 。這種情況下，將需 要使用 優先級隊列 。

執行散列搜索

二叉搜索算法有以下缺點：

它只能搜索排序過的列表。

它還需要一個方法能夠直接訪問列表的中間元素。

能夠克服這些限制并且提供高效率的搜索算法是散列搜索。

散列有兩個限制：

它可能導致沖突。

它不能順序訪問。

定義散列

假設您要搜索與給定記錄列表中的某個給定鍵值相對應的記錄。

要檢索所需記錄，需要順序地搜索整個記錄直到找到具有所需鍵值的記錄。

該方法十分耗時，尤其當列表非常大的時候更加耗時。

一個有效的解決方法是在偏移地址的幫助下搜索該記錄。

可以使用稱為散列法的技術來計算記錄的偏移地址。

散列的基本原理是將鍵值轉換為偏移地址來檢索記錄。

鍵轉換為地址是通過一種關系（公式）來完成的，就是散列

使用散列搜索記錄的過程總結為：

1.? 給定一個鍵，散列函數將它轉換為范圍從 1 到 n 的散列值（位置），其中 n 是已經為這些記 錄分配的存儲（地址）空間的大小。

2. 在產生的位置處檢索到記錄。

散列有兩個限制：

它可能導致沖突。

它不能順序訪問。

選擇散列函數的兩個原則標準是：

簡單并且能夠快速計算。

能夠在地址空間中獲取鍵的均勻分布。

設計一個散列函數有各種技術，其中有：

截取法

模塊法

平方取中法

折疊法

解決沖突

試圖將兩個鍵存儲在同一位置的情形稱為沖突。

兩個記錄不能占用同一個位置。因此，需要注意發生沖突的情況。

沖突可以使用稱為分離鍵的方法得到解決。

使用散列比使用其他搜索方法更快速。

散列效率在理想化的情況下是 O(1) 。

但是，由于沖突，散列的效率會降低。

在這種情況下，散列的效率取決于散列函數的質量。

小結

在本章中，你已經學到：

一個隊列就是線型數據結構，隊列中的元素被插入在隊列末端，然后從隊列前端 刪除。

隊列上可進行的操作有插入和刪除。

可通過使用數組或鏈接列表來實現隊列。

一個使用循環數組實現的隊列能克服線性數組實現的隊列的空間利用率問題。

使用鏈接列表實現的隊列也被稱為鏈接隊列。

隊列能在多個領域中得到應用：

打印機暫存

CPU 調度

郵件服務

鍵盤緩沖

電梯

散列的基本原理是將給定的鍵值轉換成偏移地址以檢索記錄。

在散列中，鍵轉換為地址是通過一個關系（公式）也就是散列函數來完成的。

散列函數為兩個或多個鍵產生相同的散列值，這種情況稱作沖突。

使用一個好的散列函數可以使沖突發生的可能性降至最小。

選擇散列函數的兩個原則標準是：

簡單并且計算快速。

在地址空間中應該達到均衡的鍵分布。

可以使用各種技術來設計散列函數，它們是：

截取法

模塊法

平方取中法

折疊法

沖突問題可以使用稱為分離鏈的方法得到解決。

數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。