大家在學(xué)習編程時(shí)或程序開(kāi)發(fā)中，經(jīng)常提到數據結構中的“隊列”和“?！?。那么他們分別具有什么結構特點(diǎn)？底層實(shí)現原理是什么？他們在STL中是如何實(shí)現的呢？都有哪些應用場(chǎng)景呢？

書(shū)接上文<數據結構的棧(stack)是如何實(shí)現的？>，本文講解數據結構中的隊列(queue)。

1.引言

棧和隊列是兩種特殊的線(xiàn)性表，是操作受限的線(xiàn)性表，稱(chēng)限定性DS。

通常稱(chēng)，棧和隊列是限定插入和刪除只能在表的“端點(diǎn)”進(jìn)行的線(xiàn)性表。

舉例：

線(xiàn)性表 Insert(L, i, x) 1≤i≤n+1 Delete(L, i) 1≤i≤n //任意位置插入和刪除

棧 Insert(S, n+1, x) Delete(S, n) //同一個(gè)口插入和刪除

隊列 Insert(Q, n+1, x) Delete(Q, 1) //一個(gè)口插入，另一個(gè)口刪除

2.隊列的定義和特點(diǎn)

隊列有單向隊列(queue)和雙向隊列(deque)之分，本文重點(diǎn)講述單向隊列。

2.1.單向隊列(queue，本文簡(jiǎn)稱(chēng)隊列)：

是一種先進(jìn)先出(First In First Out,FIFO)的數據結構。它有兩個(gè)出口，形式如下圖所示。

圖片來(lái)自<STL源碼剖析>

queue允許新增元素、移除元素、從最底端加人元素、從最頂端取出元素。但除了最底端可以加入、最頂端可以取出外，沒(méi)有任何其它方法可以存取queue的其它元素。換言之，queue不允許有遍歷行為。

將元素推入queue的操作稱(chēng)為push,將元素推出queue的操作稱(chēng)為pop。

定義：隊列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線(xiàn)性表

隊尾(rear)——允許插入的一端

隊頭(front)——允許刪除的一端

特點(diǎn)：先進(jìn)先出(FIFO)

單向隊列示意圖：

2.2.雙向隊列(deque)：

deque是一種雙向開(kāi)口的連續線(xiàn)性空間(STL中vector也是連續線(xiàn)性空間，但是vector是單向開(kāi)口，即主要在后面進(jìn)行插入)。所謂雙向開(kāi)口，意思是可以在頭尾兩端分別做元素的插人和刪除操作，如下圖所示。

圖片來(lái)自<STL源碼剖析>

vector當然也可以在頭尾兩端進(jìn)行操作（從技術(shù)觀(guān)點(diǎn))，但是其頭部操作效率奇差，無(wú)法被接受。

STL的deque和vector的最大差異，一在于deque允許于常數時(shí)間內對起頭端進(jìn)行元素的插入或移除操作，二在于deque沒(méi)有所謂容量(capacity)觀(guān)念，因為它是動(dòng)態(tài)地以分段連續空間組合而成，隨時(shí)可以增加一段新的空間并鏈接起來(lái)。換句話(huà)說(shuō)，像vector那樣“因舊空間不足而重新配置一塊更大空間，然后復制元素，再釋放舊空間”這樣的事情在deque是不會(huì )發(fā)生的。也因此，deque沒(méi)有必要提供所謂的空間保留(reserve)功能。

也因此，STL的deque提供的迭代器內部實(shí)現特別復雜。因此，除非必要，我們應盡可能選擇使用vector而非deque。對deque進(jìn)行的排序操作，為了最高效率，可將deque先完整復制到一個(gè)vector身上，將vector排序后（利用STL sort算法），再復制回deque。

雙向隊列示意圖：

STL的deque內部空間結構示意圖：

圖片來(lái)自<STL源碼剖析>

圖片來(lái)自<STL源碼剖析>

3.queue的實(shí)現原理

隊列分為“鏈隊列”和“順序結構隊列”兩類(lèi)。

3.1.鏈隊列

利用單向鏈表存儲數據元素、也可以使用STL的list進(jìn)行實(shí)現。

鏈隊列結構定義：

//結點(diǎn)類(lèi)型

typedef struct QNode

{

QElemType data;

struct QNode *next;

} QNode, *QueuePtr;

// 鏈隊列類(lèi)型

typedef struct {

QueuePtr front; // 隊頭指針

QueuePtr rear; // 隊尾指針

} LinkQueue;

示意圖：

3.2.順序結構隊列

可以用普通的一維數組實(shí)現，也可以使用STL的deque進(jìn)行實(shí)現。

下面咱們先以一維數組為底層結構的方式進(jìn)行講解。

示意圖：

定義一個(gè)一維數組sq用于存儲數據，定義front和rear兩個(gè)指針用于控制入隊和出隊操作。

以一維數組為底層結構的隊列處理方式

一維數組機構存在的問(wèn)題：

設數組大小為M，則：

當front=0,rear=M時(shí)，再有元素入隊發(fā)生溢出——真溢出

當front≠0,rear=M時(shí)，再有元素入隊發(fā)生溢出——假溢出

解決方案:

1. 隊首固定，每次出隊剩余元素向下移動(dòng)——浪費時(shí)間，效率低
2. 發(fā)生假溢出時(shí)再移動(dòng)
3. 循環(huán)隊列

• 基本思想：把隊列設想成環(huán)形，讓sq[0]接在sq[M-1]之后，若rear==M,則令rear=0;
• 實(shí)現：利用“取?！边\算
• 入隊： sq[rear]=x; rear=(rear+1)%M;
• 出隊： x=sq[front]; front=(front+1)%M;
• 隊滿(mǎn)、隊空的判定條件

循環(huán)隊列示意圖：

循環(huán)隊列運行效果示例：

全出隊后隊空狀態(tài)，入隊后隊滿(mǎn)狀態(tài)

循環(huán)隊列發(fā)現問(wèn)題：

當前無(wú)法區分隊列是滿(mǎn)還是空！

• 隊空的判斷條件：front==rear
• 隊滿(mǎn)的判斷條件：front==rear

解決對策：

1.另外設一個(gè)標志以區別隊空、隊滿(mǎn)

2.少用一個(gè)元素空間：

隊空：front == rear

隊滿(mǎn)：(rear+1)% M == front

紅框表示新輸入的數據，此時(shí)為隊滿(mǎn)狀態(tài)

4.STL中的queue實(shí)現

對于queue，在STL中是如何實(shí)現的呢？又有哪些特點(diǎn)呢？

①SGI STL以deque作為缺省情況下的queue底部結構

以某種既有容器為底部結構，將其接口改變，使其符合“先進(jìn)先出”的特性，形成一個(gè)queue是很容易做到的。deque是雙向開(kāi)口的數據結構，若以deque為底部結構并封閉其底端的出口和前端的入口，便輕而易舉地形成了一個(gè)queue。因此，SGI STL便以deque作為缺省情況下的queue底部結構，queue的實(shí)現因而非常簡(jiǎn)單，源代碼十分簡(jiǎn)短。

template <class T, class Sequence = deque<T> >

class queue {

friend bool operator== __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);

friend bool operator< __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);

public:

typedef typename Sequence::value_type value_type;

typedef typename Sequence::size_type size_type;

typedef typename Sequence::reference reference;

typedef typename Sequence::const_reference const_reference;

protected:

Sequence c;// 底層容器

public:

// 以下完全利用 Sequence c 的操作，完成 queue 的操作。

bool empty() const { return c.empty(); }

size_type size() const { return c.size(); }

reference front() { return c.front(); }

const_reference front() const { return c.front(); }

reference back() { return c.back(); }

const_reference back() const { return c.back(); }

// deque 是兩頭可進(jìn)出，queue 是末端進(jìn)，前端出（所以先進(jìn)者先出）。

void push(const value_type& x) { c.push_back(x); }

void pop() { c.pop_front(); }

};

template <class T, class Sequence>

bool operator==(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {

return x.c == y.c;

}

template <class T, class Sequence>

bool operator<(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {

return x.c < y.c;

}

②queue沒(méi)有提供迭代器

queue所有元素的進(jìn)出都必須符合“先進(jìn)先出”的條件，只有queue頂端的元素，才有機會(huì )被外界取用。queue不提供走訪(fǎng)功能，也不提供迭代器。

③可以使用list作為queue的底層容器。(對應前面提到的“順序結構隊列”)

除了deque之外，Iist也是雙向開(kāi)口的數據結構。上述queue源代碼中使用的底層容器的函數list都具備。因此，若以list為底部結構并半封閉其頭端開(kāi)口，一樣能夠輕易形成一個(gè)queue。

測試代碼：

參考文章最后的附錄。

測試程序運行效果：

分別使用STL的deque、list作為stack的底層容器，進(jìn)行同樣數據的入棧和出棧。

注意：STL的vector不能作為STL stack的底層容器，因為queue的pop()函數最終使用的'pop_front'不是 'std::vector' 的成員。

附錄：

測試代碼源碼。

#include <iostream>

#include <queue>

#include <list>

#include <vector>

#include <algorithm>

using namespace std;

template <class T, class Sequence = deque<T> >

void queue_fun_test(queue<T, Sequence>& list_queue)

{

cout << ' ' << __FUNCTION__ << endl;

//入隊列

list_queue.push(1);

list_queue.push(2);

list_queue.push(3);

list_queue.push(4);

list_queue.push(5);

list_queue.push(6);

list_queue.push(7);

if (true != list_queue.empty())

{

cout << ' 隊列內元素個(gè)數:' << list_queue.size() << endl;

cout << ' 當前隊列頭' << list_queue.front() << endl;

}

cout << endl << ' 元素依次出隊列:' << endl;

// 元素依次出隊列

while (true != list_queue.empty())

{

// 打印隊列頂元素

cout << ' ' << list_queue.front() << '出隊列!' << endl;

// 出隊列

list_queue.pop();

}

}

//以deque作為缺省情況下的queue底部結構

void queue_fun_deque_test()

{

cout << endl << __FUNCTION__ << endl;

queue<int> list_queue; //創(chuàng )建queue

queue_fun_test(list_queue);

}

//以list作為queue底部結構

void queue_fun_list_test()

{

cout << endl << __FUNCTION__ << endl;

queue<int, list<int>> list_queue; //創(chuàng )建queue

queue_fun_test(list_queue);

}

/*

//vector是不能作為STL queue底部結構的

void queue_fun_vector_test()

{

cout << endl << __FUNCTION__ << endl;

queue<int, vector<int>> list_queue; // error C2039: 'pop_front': 不是 'std::vector<int,std::allocator<int>>' 的成員

queue_fun_test(list_queue);

}

*/

int queue_main(int argc, char* argv[])

{

queue_fun_deque_test();

queue_fun_list_test();

//queue_fun_vector_test();

return 0;

}