一搭伤、隊列的相關(guān)概念和定義
試想一下弄唧，有的時候電腦像死機一樣，鼠標(biāo)點什么都沒用险毁。而過了一會卻好像酒醒了一樣把你剛才的操作都順序執(zhí)行了一遍制圈。這其實是因為操作系統(tǒng)中的多個程序因需要通過一個通道輸出，而按先后次序排隊等待造成的畔况。這實際上是一種先進先出的思想鲸鹦，我們稱之為隊列。
隊列的應(yīng)用非常廣泛：
舉例：鍵盤輸入跷跪，顯示器上記事本軟件的輸出等等馋嗜。。包括操作系統(tǒng)的各種準(zhǔn)備隊列吵瞻，就緒隊列葛菇。甘磨。都是先進先出的典型。
隊列的定義：是只允許在一端進行插入操作眯停，而在另一端進行刪除操作的線性表（First in first out济舆，F(xiàn)IFO，先進先出）莺债。
循環(huán)隊列
隊列作為一個線性表滋觉，也有順序存儲和鏈?zhǔn)酱鎯?/strong>兩種方式。
隊列順序存儲的不足：
- 首先齐邦，隊列順序存儲一個固定長度的序列椎瘟，并向其中添加n個元素。若再添加元素只需加到隊尾即可侄旬，時間復(fù)雜度為O(1)肺蔚。
- 然而，出棧時是隊頭出棧儡羔。因此宣羊，如果下次想再讓隊頭出棧，則需要把所有元素往前移動一位汰蜘，即把下標(biāo)為1的元素移動到下標(biāo)為0的地方仇冯，時間復(fù)雜度為O(n)，并且是每次出棧一個元素就要重復(fù)執(zhí)行一次族操。
- 為避免這種情況苛坚，我們就引入兩個指針front和rear分別指向隊頭和隊尾。令front==rear時色难，隊列為空泼舱。rear指向末尾元素的后面一位。這樣可以避免隊列滿時也會出現(xiàn)front==rear的情況枷莉。
問題1：當(dāng)最后一個元素插到分配地址的末尾娇昙，而前面有空位置，那么rear指針何去何從笤妙？
答：再重頭開始冒掌，將rear指針插到最前面的分配的地址空間。
我們將這種隊列稱之為循環(huán)隊列蹲盘。
問題2：rear可能比front大股毫，也可能比front小，那么如何判斷召衔？
答：兩者最少相差1的內(nèi)存空間（可能只相差1個位置铃诬，也可能是一圈，看rear在前面還是后面），這個時間我們就判斷是滿了氧急。若隊列的最大尺寸是Queuesize，那么隊列滿了的條件是(rear+1)%Queuesize==front（取模以后就整合了rear與front的大小前后兩個位置各自的問題）毫深。
問題3：隊列長度計算公式：
- rear>front時吩坝，長度為rear-front。
- rear<front時哑蔫，分兩段钉寝。第一段為Queuesize-front，第二段為0+rear闸迷，合起來就是rear-front+Queuesize嵌纲。
因此通用計算長度為(rear-front+Queuesize)%Queuesize。
注意：此為順序存儲結(jié)構(gòu)的方法腥沽。
鏈?zhǔn)疥犃?/h4>
鏈?zhǔn)疥犃袑嶋H上就是線性表的單鏈表逮走，只不過它只能尾進頭出而已。尾進就用尾插法今阳，頭出可以參考一下棧的Pop（）函數(shù)师溅。
此時，rear沒有必要空出一個元素盾舌，因為鏈?zhǔn)疥犃写鎯臻g一般是用不完的墓臭，除非內(nèi)存已滿。
二妖谴、隊列的代碼實現(xiàn)
循環(huán)隊列
//SeqQueue.h
#ifndef SEQQUEUE_H_
#define SEQQUEUE_H_
const int Queuesize = 10;
class SeqQueue
{
private:
int num[Queuesize];
int front;
int rear;
public:
SeqQueue();
~SeqQueue();
void EnQueue(int e);
void DeQueue();
int length();
void Print();
};
#endif
//SeqQueue.cpp
#include<iostream>
#include"SeqQueue.h"
using std::cout;
using std::endl;
SeqQueue::SeqQueue()
{
front = rear = 0;
}
SeqQueue::~SeqQueue()
{
}
void SeqQueue::EnQueue(int e)
{
if((rear+1)%Queuesize == front)//判斷是否為滿隊列
return;
num[rear] = e;//把尾部加上元素
rear = (rear+1)%Queuesize;//尾部向后一位
}
void SeqQueue::DeQueue()
{
if(front == rear)//判斷是否為空隊列
return;
front = (front+1)%Queuesize;//front向后一位
}
int SeqQueue::length()
{
return (rear-front+Queuesize)%Queuesize;
}
void SeqQueue::Print()
{
for (int i=front;i!=rear;i=(i+1)%Queuesize)
{
cout << num[i] << " ";
}
cout << endl;
cout << "Length: " << length() << endl;
}
//Test.cpp
#include<iostream>
#include"SeqQueue.h"
using namespace std;
int main()
{
SeqQueue S;
for (int i=0;i<5;i++)
{
S.EnQueue(i);
S.Print();
}
for (int i=0;i<2;i++)
{
S.DeQueue();
S.Print();
}
return 0;
}
輸出結(jié)果：
鏈?zhǔn)疥犃谢貋碓傺a窿锉。
