隊列的基本概念
遵循先入先出的原則，即：先存入隊列的數(shù)據(jù)，要先取出，后存入的要后取出。
就像排隊打飯一樣，來的早，走的也早（此早非彼早）
示意圖：自己腦補
隊列最基本的兩個操作：
入隊（enqueue），放一個數(shù)據(jù)到隊列的尾部；
出隊（dequeue）從隊列頭部取一個元素。
順序隊列和鏈式隊列
用數(shù)組實現(xiàn)的隊列叫順序隊列，用鏈表實現(xiàn)的隊列叫鏈式隊列。
我們先分析下基于數(shù)組實現(xiàn)的順序隊列：比如這里有一個Length為4的隊列，默認是空值，啥也沒有存入
隊列有兩個指針，隊頭，Head，隊尾，Rear
隊列初始狀態(tài)
- head = 0; 隊頭
- rear = 0; 隊尾
隊列的大小為size，隊列數(shù)組的第一個元素下標為0，最后一個元素的下標為size-1。
代碼如下
private int head=0;//隊頭
private int rear=0;//隊尾
private int size=0;//長度
private int[] arr;//隊列數(shù)組
//用構(gòu)造函數(shù)初始化隊列
public Queue(int size)
{
this.size = size;
arr = new int[size];
}
入隊
給數(shù)組隊列加入數(shù)據(jù)6，7
每加入一個數(shù)據(jù)，rear(隊尾) 就向后移動一位，隊頭(Head) 不動，當tail == size 時表示隊列已滿。
代碼如下：
//入隊
public void AddData(int num)
{
//判斷是否已滿
if (size==rear)
{
Console.WriteLine("添加失敗，隊列已滿");
return;
}
arr[rear] = num;
rear++;
Console.WriteLine(num+"：加入隊列");
}
出隊
即 按照先進先出的原則，取出數(shù)據(jù)
當6出隊之后，隊頭(Head) 指針向后移動一個位置，隊尾指針rear指向不變，當head == rear 時表示隊列為空。
代碼如下：
//出隊
public Integer dequeue() {
// 判斷隊列是否為空
if(head == rear) {
return null;
}
int item = arr[head];
head++;
return item;
}
話不多說，奉上全部代碼
private int head=0;//隊頭
private int rear=0;//隊尾
private int size=0;//長度
private int[] arr;//隊列數(shù)組
//初始化隊列
public Queue(int size)
{
this.size = size;
arr = new int[size];
}
//入隊
public void AddData(int num)
{
//判斷是否已滿
if (size==rear)
{
Console.WriteLine("添加失敗，隊列已滿");
return;
}
arr[rear] = num;
rear++;
Console.WriteLine(num+"：加入隊列");
}
//出隊
public Integer dequeue() {
// 判斷隊列是否為空
if(head == rear) {
return null;
}
int item = arr[head];
head++;
return item;
}
//獲取隊列首位元素
public void GetOneElement()
{
if (head==rear)
{
Console.WriteLine("獲取失敗，隊列為空");
return;
}
Console.WriteLine("首位元素：" + arr[head]);
}
//元素
public void QueueList()
{
if (head==rear)
{
throw new Exception("隊列為空");
}
Console.WriteLine("--------------------遍歷隊列-----------------------");
foreach (var a in arr)
{
Console.Write(" "+a);
}
Console.WriteLine();
}
實現(xiàn)以上代碼后，問題來了！?。?/h3>
首先我這里重新定義一下隊頭和隊尾
隊尾：Head，隊頭：Tail
這里有兩個需要特別注意的地方
- 入隊時判斷隊列已滿條件
tail == size - 出隊時判斷隊列為空條件
head == tail
隨著不斷的入隊和出隊操作，最后head和tail都會一直向隊尾移動，當head == tail && tail == size的時候，如下圖所示，即使隊列有空閑空間也無法向隊列中添加任何元素了，也就是說，我們上面創(chuàng)建的隊列只能使用一次。
如何解決這個問題呢，我們可以使用循環(huán)隊列，現(xiàn)在的隊列是一條直線，如果我們把首尾相連就形成了一個環(huán)，如下圖所示：
循環(huán)隊列
我可以用循環(huán)隊列來解決順序隊列只能使用一次的問題。在循環(huán)隊列中，我們依然需要使用兩個變量head（指向隊列中的第一個元素，初始值為0）和tail（指向隊列中最后一個元素的下一個位置，初始值為0）。
在順序隊列中，我們需要判斷隊空和隊滿的情況，同樣在循環(huán)隊列也需要判斷隊滿和隊空的情況。
上圖中這個隊列大小size為8，開始隊列空時head和tail都指向下標0。依次添加元素a、b，此時如上圖所示head位置不變，tail向后移指向下標為2的位置。繼續(xù)添加元素c、d、e、f、g， 此時tail指向了最后一個位置。
數(shù)組實現(xiàn)的非循環(huán)隊列中，隊空的情況是head == tail，循環(huán)隊列中隊空的情況也是head == tail。非循環(huán)隊列中隊滿的情況是tail == size，循環(huán)隊列中隊滿的情況是(tail + 1) % size == head。
上圖可以看出，當隊列滿時，tail指向的位置是沒有存儲元素的。如果我們想要最后一個位置也存儲元素，那么tail需要繼續(xù)向后移動一個位置，此時tail和head指向了同一個位置，與隊列為空的情況是一樣的條件head == tail，
所以我們約定犧牲一個存儲空間來區(qū)分隊空和隊滿的情況。
同樣可以計算出隊列中實際有效元素的個數(shù)為 (tail + size - head) % size。
下面我們使用代碼來實現(xiàn)循環(huán)隊列：
private int[] arr;
private int size;
private int tail = 0;
private int head = 0;
public QueueLoop(int size)
{
this.size = size;
arr = new int[size];
}
//入列
public void Add(int num)
{
//判斷隊列是否已滿
if ((tail + 1) % size == head)
{
Console.WriteLine("隊列已滿，不能再添加");
return;
}
arr[tail] = num;
// (n+1) % size 相當于取 1~size的范圍，（不包含size）
tail = (tail + 1) % size;
}
//出列
public void DeQueue()
{
//判斷隊列是否為空
if (head == tail)
{
Console.WriteLine("隊列元素為空");
return;
}
Console.Write(" " + arr[head]);
head = (head + 1) % size;
}
//獲取頭元素
public void GetHeadElement()
{
//判斷隊列是否為空
if (head == tail)
{
Console.WriteLine("隊列元素為空");
return;
}
Console.WriteLine("頭元素" + arr[head]);
}
public void QueueList()
{
// 實際有效元素個數(shù)
int num = (tail + size - head) % size;
for (int i = head, len = head + num; i < len; i++)
{
Console.Write(" "+arr[i % size]);
}
}
注意：素材來源于網(wǎng)絡(luò)，僅作為學習筆記記錄
本人充分尊重原創(chuàng)勞動成果：如有侵權(quán)糾紛，請留言反饋，謝謝
