目錄
一、前言
二、基本概念
三、順序佇列
四、鏈佇列
五、回圈佇列
六、總結與提高
一、前言
- 佇列在程式設計中經常出現，如：作業系統中的排隊問題，
- 這篇文章主要介紹了佇列的基本概念、性質，順序、鏈、回圈三種不同的方法實作佇列，順序和回圈佇列在演算法中比較常用
二、基本概念
定義：佇列是允許在一端插入，另一端洗掉的線性表
隊頭（front）：允許洗掉的一端
隊尾（rear）：允許插入的一端
特點：先進先出
三、順序佇列
動態圖：
演算法講解：
- 圖解：入隊，rear++，出隊，front++
- 真溢位：front==0，rear==n-1
- 假溢位：front ! = 0，rear==n-1
結構體：
#define MAXQSIZE 100;
Typedef struct{
QElemType element[MAXQSIZE]; //佇列的元素空間
int front; //頭指標，若佇列不空，指向隊頭元素；
int rear; //尾指標，若佇列不空，指向隊尾元素的下一個位置
}SeqQueue;四、鏈佇列
- 定義：用鏈表實作的佇列，為了操作方便，通常采用帶頭結點的鏈表結構，設定一個隊頭指標和隊尾指標
- 隊頭指標：始終指向頭結點
- 隊尾指標：指向當前最后一個元素
- 空的鏈佇列：隊頭指標和隊尾指標均指向頭結點
入隊：
int EnterQueue ( LinkQueue *Q; QElemType x ) {
//1. 為待插入結點開辟存盤空間
p = ( LinkQueueNode ) malloc ( sizeof ( QNode ) );
if (p==NULL ) return ( FALSE ); // 存盤空間分配失敗
//2. 將值 x放入新結點的資料域,令新結點的指標域為空
p->data = x; p->next = NULL;
// 3. 將新結點插入到佇列 Q 的尾, 并修改佇列 Q 的隊尾指標
Q->rear->next = p;
Q->rear = p;
return (TRUE);
} // EnterQueue出隊：
int DeleteQueue ( LinkQueue *Q, QElemType *x ) {
// 1.如果佇列為空則無法進行洗掉，則回傳 ERROR
if ( Q->front = = Q->rear ) return (FALSE);
// 2.令 p 指向佇列 Q 的頭, 并將隊頭結點的值取出并放入 x
p = Q->front->next; x = p->data;
//3. 修改隊頭指標
Q->front->next = p->next;
// 4. 若隊中只有一個元素，則P出隊后成為空隊
if ( Q->rear = = p ) Q->rear = Q->front;
free ( p ); // 釋放隊頭元素所占空間
return (TRUE);
} // DeleteQueue
五、回圈佇列
- 概念：佇列的一種順序表示和實作方法，與順序堆疊類似
動態圖：
演算法講解：
- A B C D入隊時，頭指標front不動，rear=(rear+1)%n
- A B C D出隊時，尾指標rear不動，front=(front+1)%n
入隊：
int EnterQueue(SeqQueue *Q,QueueElementType x)
{
//1. 判斷佇列是否已經滿了
if((Q->rear+1)%MAXSIZE==Q->front)
return (FALSE);
//2. 新元素x入隊
Q->element[Q->rear]=x;
// 3. 重新設定隊尾指標
Q->rear=(Q->rear+1)%MAXSIZE;
return (TRUE);
}出隊：
int DeleteQueue(SeqQueue *Q,QueueElementType *x)
{
//1. 判斷佇列是否已經空了
if(Q->front==Q->rear)
return(FALSE);
//2. 洗掉佇列的隊頭元素，用x回傳其值
*x=Q->element[Q->front];
// 3. 重新設定隊頭指標
Q->front=(Q->front+1)%MAXSIZE;
return(TRUE);
}特點：
- 隊空： rear==front
- 隊滿：(rear+1)%n==front
- 入隊：rear=(rear+1)%n
- 出隊：front=(front+1)%n
- 隊中元素個數：（rear-front+n）%n
六、總結與提高
- 對于使用C++編程來說，上文佇列的判空、判滿、插入、洗掉等等一系列代碼，不需要你完全掌握，C++的STL標準庫中為你準備好了函式等你呼叫，
C++queue頭檔案：
#include<queue>
//#include<bits/stdc++.h>或者萬能頭檔案
using namespace std;
C++queue具體操作：
- 用queue定義q類（定義什么都可以，只要把s變成定義的字母就可以呼叫C++中的函式）,具體使用方法為：
| 函式 | 用法 |
| q.empty() | 判斷佇列是否為空，不為慷訓傳1，為慷訓傳0 |
| q.size() | 回傳佇列中元素個數 |
| q.pop() | 洗掉佇列首元素 |
| q.front() | 回傳佇列首元素，不洗掉該元素 |
| q.back() | 回傳佇列尾元素，不洗掉該元素 |
| s.push() | 隊尾插入新的元素 |
力扣習題：
一、用佇列實作堆疊
二、設計回圈佇列
三、動物收容所
四、無法吃午餐的學生數量
五、Dota2參議院
六、滑動視窗
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/393928.html
標籤：其他
上一篇：Python資料結構-串列