概述
顧名思義坷随，隊(duì)列其實(shí)就類似于我們現(xiàn)實(shí)生活中的排隊(duì)。在計(jì)算機(jī)科學(xué)中驻龟，隊(duì)列是一種特殊的抽象數(shù)據(jù)類型(ADT)或集合温眉，保存在這個(gè)集合中的實(shí)體按線性的邏輯次序排列。對(duì)隊(duì)列中元素的操作翁狐，僅限于在隊(duì)尾和隊(duì)首進(jìn)行类溢，其中包括在隊(duì)尾添加元素（入隊(duì)，enqueue）以及移除隊(duì)首的元素（出隊(duì)露懒，dequeue）闯冷，這就使隊(duì)列成為一種先進(jìn)先出（FIFO，F(xiàn)irst-In-First-Out）的數(shù)據(jù)結(jié)構(gòu)懈词。
就像大家都知道的前兩天剛發(fā)生的 ofo 總部排隊(duì)退押金時(shí)間蛇耀，也可以看作是一個(gè)隊(duì)列。
在這里插句題外話钦睡，最近太多關(guān)于該不該向小黃車要押金的爭(zhēng)論了蒂窒，不管誰對(duì)誰錯(cuò)，畢竟小黃車也是曾經(jīng)給我們帶來過便利的荞怒，希望小黃車這次能夠挺過去洒琢！
言歸正傳，在先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)中褐桌，第一個(gè)被添加到隊(duì)列中的元素也會(huì)被第一個(gè)移除衰抑，這相當(dāng)于在添加新元素之后，必須在刪除新元素之前刪除之前添加的所有元素荧嵌。隊(duì)列是線性數(shù)據(jù)結(jié)構(gòu)的一個(gè)例子呛踊，或者更抽象地說是順序集合。
隊(duì)列提供計(jì)算機(jī)科學(xué)啦撮、傳輸和運(yùn)籌學(xué)方面的服務(wù)谭网，在這些服務(wù)中，各種實(shí)體(如數(shù)據(jù)赃春、對(duì)象愉择、人員或事件)被保存在隊(duì)列中以供稍后處理，此時(shí)，隊(duì)列實(shí)際上是作為緩沖區(qū)來使用锥涕。
ADT 接口
作為一種抽象數(shù)據(jù)類型衷戈，與棧類似，隊(duì)列結(jié)構(gòu)也有自己的操作接口层坠。如下表所示殖妇。
| 操作 | 功能 |
|---|---|
| size() | 報(bào)告隊(duì)列的規(guī)模（元素總數(shù)） |
| empty() | 判斷隊(duì)列是否為空 |
| enqueue(e) | 將 e 插入隊(duì)尾 |
| dequeue() | 刪除隊(duì)首對(duì)象 |
| front() | 引用隊(duì)首對(duì)象 |
實(shí)現(xiàn)
隊(duì)列常見的實(shí)現(xiàn)方式有兩種，一種是基于鏈表的普通隊(duì)列破花，另一種是基于數(shù)組的循環(huán)隊(duì)列谦趣。
基于鏈表的普通隊(duì)列
在此前的一篇文章中，我介紹了鏈表的實(shí)現(xiàn)方式座每，沒有讀過的朋友可以看看蔚润，手把手教你實(shí)現(xiàn)一個(gè)鏈表。在這一節(jié)中尺栖，我們將在這篇文章的基礎(chǔ)上來實(shí)現(xiàn)隊(duì)列。按照上文中描述的隊(duì)列的操作接口烦租，可實(shí)現(xiàn) Queue 模板類如下：
#pragma once
#include "LinkedList.h"
template <typename T> class Queue {
private:
LinkedList<T> list;
public:
int size() {
return list.size();
}
bool empty() {
return list.empty();
}
void enqueue(T const& e) { //入隊(duì)延赌，從尾部插入
list.insertAsLast(e);
}
T dequeue() { //出隊(duì)，從首部刪除
return list.remove(list.first());
}
T& front() { //隊(duì)首
return list.first()->data;
}
};
這種基于鏈表的實(shí)現(xiàn)方式比較簡(jiǎn)單叉橱，也容易理解挫以。而且它還繼承了鏈表的最大的優(yōu)點(diǎn)，那就是在內(nèi)存允許的情況下窃祝，可以無限地往里面添加元素掐松，也就是進(jìn)行入隊(duì)操作。
基于數(shù)組的循環(huán)隊(duì)列
大家都知道粪小，數(shù)組是一種順序存儲(chǔ)結(jié)構(gòu)大磺。如果單純地用數(shù)組模擬隊(duì)列，那么隨著出隊(duì)入隊(duì)的操作探膊，很容易導(dǎo)致「假溢出」杠愧。
系統(tǒng)作為隊(duì)列用的存儲(chǔ)區(qū)還沒有滿,但隊(duì)列卻發(fā)生了溢出,我們把這種現(xiàn)象稱為「假溢出」。
但是如果在邏輯上逞壁，我們將其想象成一個(gè)環(huán)，那么除非數(shù)組空間被占滿，否則可以一直往里添加元素未蝌，這樣就不會(huì)造成空間的浪費(fèi)樟遣，有效地避免了「假溢出」。
下面是 C++ 代碼實(shí)現(xiàn)：
#pragma once
#define MAX_SIZE 10 //最大容量
template <typename T> class CircularQueue {
private:
int _size = 0; //隊(duì)列當(dāng)前規(guī)模
int _front = 0; //隊(duì)首指針
int _rear = 0; //隊(duì)尾指針
T* _elem; //數(shù)據(jù)區(qū)
public:
CircularQueue() {
_elem = new T[MAX_SIZE];
}
int size() {
return _size;
}
bool empty() {
/*隊(duì)空或隊(duì)滿時(shí)姿骏，隊(duì)首指針和隊(duì)尾指針都會(huì)相遇糖声，此時(shí)應(yīng)該根據(jù)隊(duì)列的規(guī)模 size 來判斷
若 size=0，則隊(duì)空，若 size=max_size姨丈，則隊(duì)滿*/
return _front == _rear && _size == 0;
}
bool enqueue(T const& e) { //入隊(duì)
if (_size == MAX_SIZE) return false; //若隊(duì)已滿畅卓，則返回false
_elem[_rear] = e;
_rear = (_rear + 1) % MAX_SIZE;
_size++;
return true;
}
T dequeue() { //出隊(duì)
if (empty()) return 0;
T e = _elem[_front];
_front = (_front + 1) % MAX_SIZE;
_size--;
return e;
}
T& front() {
return _elem[_front];
}
};
當(dāng)隊(duì)首指針 _front=MAX_SIZE-1 后，再前進(jìn)一個(gè)位置就自動(dòng)到 0蟋恬，所以在元素出隊(duì)之后翁潘，我們利用了求余操作來更新隊(duì)首指針。同理歼争，更新隊(duì)尾指針時(shí)也是這樣拜马。使用循環(huán)隊(duì)列時(shí)，用戶必須提前預(yù)知隊(duì)列的最大容量沐绒，且一旦最大容量固定下來俩莽，就不可更改。
以上就是向大家介紹的隊(duì)列的全部?jī)?nèi)容了乔遮。本篇文章中的代碼已上傳至 GitHub扮超，點(diǎn)擊這里即可獲得。這是 2018 年的最后一篇推送了蹋肮，祝大家新年快樂出刷！2019 年再見哦！
歡迎關(guān)注我的微信公眾號(hào)坯辩，掃描下方二維碼或微信搜索：AProgrammer馁龟，就可以找到我，我會(huì)持續(xù)為你分享 IT 技術(shù)漆魔。
