知識星球（點選上方公眾號，可快速關註）
轉自：melonstreet
https://www.cnblogs.com/qg-whz/p/5171123.html
佇列簡介
佇列的特點
佇列（Queue）與棧一樣，是一種線性儲存結構，它具有如下特點：
1、佇列中的資料元素遵循“先進先出”（First In First Out）的原則，簡稱FIFO結構。
2、在隊尾新增元素，在隊頭新增元素。
佇列的相關概念
1、隊頭與隊尾： 允許元素插入的一端稱為隊尾，允許元素刪除的一端稱為隊頭。
2、入隊：佇列的插入操作。
3、出隊：佇列的刪除操作。
例如我們有一個儲存整型元素的佇列，我們依次入隊：{1，2，3}
新增元素時，元素只能從隊尾一端進入佇列，也即是2只能跟在1後面，3只能跟在2後面。
如果佇列中的元素要出隊：
元素只能從隊首出佇列，出佇列的順序為：1、2、3，與入隊時的順序一致，這就是所謂的“先進先出”。
佇列的操作
佇列通常提供的操作：
1、入隊： 通常命名為push()
2、出隊： 通常命名為pop()
3、求佇列中元素個數
4、判斷佇列是否為空
5、獲取隊首元素
佇列的儲存結構
佇列與棧一樣是一種線性結構，因此以常見的線性表如陣列、連結串列作為底層的資料結構。
本文中，我們以陣列、連結串列為底層資料結構構建佇列。
基於陣列的迴圈佇列實現
以陣列作為底層資料結構時，一般講佇列實現為迴圈佇列。
這是因為佇列在順序儲存上的不足：每次從陣列頭部刪除元素（出隊）後，需要將頭部以後的所有元素往前移動一個位置，這是一個時間複雜度為O（n）的操作：
可能有人說，把隊首標誌往後移動不就不用移動元素了嗎？的確，但那樣會造成陣列空間的“流失”。
我們希望佇列的插入與刪除操作都是O(1)的時間複雜度，同時不會造成陣列空間的浪費，我們應該使用迴圈佇列。
所謂的迴圈佇列，可以把陣列看出一個首尾相連的圓環，刪除元素時將隊首標誌往後移動，新增元素時若陣列尾部已經沒有空間，則考慮陣列頭部的空間是否空閑，如果是，則在陣列頭部進行插入。
那麼我們如何判斷佇列是空佇列還是已滿呢？
1、棧空： 隊首標誌=隊尾標誌時，表示棧空，即紅綠兩個標誌在圖中重疊時為棧空。
2、棧滿 : 隊尾+1 = 隊首時，表示棧空。圖三最下麵的佇列即為一個滿佇列。儘管還有一個空位，我們不儲存元素。
迴圈佇列的抽象資料型別
template <typename T>
class LoopQueue
{
public:
LoopQueue(int c = 10);
~LoopQueue();
public:
bool isEmpty(); //佇列的判空
int size(); //佇列的大小
bool push(T t); //入佇列
bool pop(); //出佇列
T front(); //隊首元素
private:
int capacity;
int begin;
int end;
T* queue;
};
1、begin：隊首標誌
2、end：隊尾標誌
3、capacity：陣列容量
4、queue：陣列
佇列的具體實現
佇列的操作非常簡單，這裡不再多說
template<typename T>
LoopQueue<T>::LoopQueue(int c = 10)
: capacity(c), begin(0), end(0), queue(nullptr)
{
queue = new T[capacity];
};
template<typename T>
LoopQueue<T>::~LoopQueue()
{
delete[]queue;
}
template <typename T>
bool LoopQueue<T>::isEmpty()
{
if (begin == end)
return true;
return false;
};
template<typename T>
int LoopQueue<T>::size()
{
return (end–begin+capacity)%capacity; //計算佇列長度
};
template<typename T>
bool LoopQueue<T>::push(T t)
{
if (end + 1 % capacity == begin) //判斷佇列是否已滿
{
return false;
}
queue[end] = t;
end = (end + 1) % capacity;
return true;
};
template <typename T>
bool LoopQueue<T>::pop()
{
if (end == begin) //判斷佇列是否為空
{
return false;
}
begin = (begin + 1) % capacity;
return true;
};
template <typename T>
T LoopQueue<T>::front()
{
if (end == begin)
{
return false;
}
return queue[begin];
};
迴圈佇列程式碼測試
int main()
{
LoopQueue<string> queue(6);
queue.push(“one”);
queue.push(“two”);
queue.push(“three”);
queue.push(“four”);
queue.push(“five”);
cout << “佇列長度” << queue.size() << endl;
while (!queue.isEmpty())
{
cout << queue.front() << endl;
queue.pop();
}
getchar();
return 0;
}
測試結果：
佇列的大小 5
one
two
three
four
five
鏈佇列
鏈佇列是基於連結串列實現的佇列，它不存在陣列的O（n）的元素移動問題或空間浪費問題。我們所要確定的就是連結串列哪頭做隊首，哪頭做隊尾。
顯然我們應該以連結串列頭部為隊首，連結串列尾部為隊尾。儲存一個指向隊尾的指標，方便從連結串列尾插入元素；使用帶頭節點的連結串列，方便從連結串列頭刪除元素。
連結串列節點
template<typename T>
struct Node
{
Node(T t) :value(t), next(nullptr){}
Node() = default;
T value;
Node<T> * next;
1、vaule : 連結串列節點的值
2、next : 指標，指向下一個節點
佇列的抽象資料型別
鏈佇列提供的介面與迴圈佇列一致
template<typename T>
class LinkQueue
{
public:
LinkQueue();
~LinkQueue();
bool isEmpty();
int size();
bool pop();
void push(T t);
T front();
private:
Node<T>* phead;
Node<T>* pend;
int count;
};
佇列的具體實現
template<typename T>
LinkQueue<T>::LinkQueue()
:phead(nullptr),pend(nullptr),count(0)
{
phead = new Node<T>();
pend = phead;
count = 0;
};
template <typename T>
LinkQueue<T>::~LinkQueue()
{
while (phead->next != nullptr)
{
Node<T> * pnode = phead;
phead = phead->next;
}
};
template <typename T>
bool LinkQueue<T>:: isEmpty()
{
return count==0;
};
template <typename T>
int LinkQueue<T>::size()
{
return count;
};
//在隊尾插入
template <typename T>
void LinkQueue<T>::push(T t)
{
Node<T>* pnode = new Node<T>(t);
pend->next = pnode;
pend = pnode;
count++;
};
//在隊首彈出
template <typename T>
bool LinkQueue<T>::pop()
{
if (count == 0)
return false;
Node<T>* pnode = phead->next;
phead->next = phead->next->next;
delete pnode;
count—;
return true;
};
//獲取隊首元素
template<typename T>
T LinkQueue<T>::front()
{
return phead->next->value;
};
佇列的程式碼測試
int _tmain(int argc, _TCHAR* argv[])
{
LinkQueue<string> lqueue;
lqueue.push(“one”);
lqueue.push(“two”);
lqueue.push(“three”);
lqueue.push(“four”);
lqueue.push(“five”);
cout << “佇列的大小” << lqueue.size() << endl;
while (!lqueue.isEmpty())
{
cout << lqueue.front() << endl;
lqueue.pop();
}
getchar();
return 0;
}
結果：
佇列的大小 5
one
two
three
four
five
覺得本文有幫助？請分享給更多人
關註「演演算法愛好者」，修煉程式設計內功
