一、キューの抽象データ型の説明#
型名：キュー（Queue）
データオブジェクトの集合：0 個以上の要素を持つ有限線形リスト
操作の集合：長さが MaxSize のキュー Q∈Queue、キューの要素 item∈ElementType
1. 長さが MaxSize の空のキューを生成する
Queue CreatQueue(int MaxSize);
2. キュー Q が満杯かどうかを判断する
bool IsFullQ(Queue Q, int MaxSize);
3. データ要素 item をキュー Q に挿入する
bool AddQ(Queue Q, ElementType item);
4. キュー Q が空かどうかを判断する
bool IsEmptyQ(Queue Q);
5. キューの先頭要素を削除して返す
ElementType DeleteQ(Queue Q);
二、キューの順序保存実装#
1. 定義#
キューの順序保存構造は通常、1 次元配列とキューの先頭要素の位置を記録する変数 frontとキューの末尾要素の位置を記録する変数 rearから構成されます。
配列を移動して、環状になり、循環キューになります。
キューの空と満杯を判断するために、循環キューは n-1 個の配列スペースのみを使用します。
以下は定義のコードです
typedef struct QNode *Queue;
struct QNode {
ElementType Data[MaxSize];//1次元配列
int rear;//キューの末尾要素の位置を記録
int front;//キューの先頭要素の位置を記録
int MaxSize;
//実際にはfrontはキューの先頭要素のインデックスの前を指しています
};
2. 操作#
(1) 循環キューの作成（CreateQueue）#
Queue CreateQueue( int MaxSize ) {
Queue Q = (Queue)malloc(sizeof(struct QNode));
Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
Q->front = Q->rear = 0;
Q->MaxSize = MaxSize;
return Q;
}
(2) キューが満杯かどうかを判断する（IsFull）#
bool IsFull( Queue PtrQ ) {//frontとrear+1の剰余が等しい場合、キューは満杯です
return ((PtrQ->rear+1) % PtrQ->MaxSize == PtrQ->front);
}
(3) キューに要素を追加する（AddQ）#
キューが満杯かどうかを判断する必要があります
bool AddQ(Queue PtrQ, ElementType item) {
if ( IsFull(PtrQ) ) {
printf("キューは満杯です");//frontとrear+1の剰余が等しい場合、キューは満杯です
return false;
} else {
PtrQ->rear = (PtrQ->rear+1) % PtrQ->MaxSize;
//キューの末尾rearを移動するために剰余演算を使用して循環を実現します
PtrQ->Data[PtrQ->rear] = item;
return true;
}
}
(4) キューが空かどうかを判断する（IsEmpty）#
bool IsEmpty(Queue PtrQ) {
return ( PtrQ->front == PtrQ->rear );
}
(5) キューから要素を削除する（DeleteQ）#
キューが空かどうかを判断してから削除します
ElementType DeleteQ(Queue PtrQ) {
if(IsEmpty(PtrQ)) {//rearとfrontが等しい場合、キューは空です
printf("キューは空です");
return false;
} else {
PtrQ->front = (PtrQ->front+1) % PtrQ->MaxSize;//キューの先頭frontを移動する
return PtrQ->Data[PtrQ->front];
}
}
三、キューの連結保存実装#
1. 定義#
キューの連結保存構造は、単方向リストを使用して実装することもできます。挿入と削除操作はリストの両端で行います。キューポインタ front はリストの先頭を指す必要があります。
struct Node {
ElementType Data;
struct Node * Next;
}
struct QNode {//リンクキュー構造
struct Node *rear; //キューの末尾ノードを指す
struct Node *front; //キューの先頭ノードを指す
};
typedef struct QNode *Queue;
Queue PtrQ;
2. 操作#
(1) ヘッドノードを持たない連結キューの初期化（CreateQueue）#
Queue CreateQueue() {
Queue Q;
Q = (Queue)malloc(sizeof(struct QNode));
Q->front = Q->rear = NULL;//両方のポインタがNULLです
return Q;
}
(2) ヘッドノードを持たない連結キューへの要素の追加（AddQ）#
bool AddQ(Queue PtrQ, ElementType item) {
struct Node *RearCell = PtrQ->rear;//末尾要素を指すポインタ
struct Node *Temp = (struct Node *) malloc(sizeof(struct Node));
Tmp->Data = X;
Tmp->Next = NULL;
if ( PtrQ->front == NULL ) {//キューが空の場合、最初の要素を追加します
PtrQ->rear = PtrQ->front = Tmp;
} else {
RearCell->Next = Tmp;
PtrQ->rear = Tmp;
}
return true;
}
(3) ヘッドノードを持たない連結キューから要素を削除する（DeleteQ）#
ElementType DeleteQ(Queue PtrQ) {
struct Node * FrontCell;
ElementType FrontElem;//先頭要素の値
if (PtrQ->front == NULL) {//1.空かどうかを先に判断し、空の場合は削除操作を行えません
printf("キューは空です");
return ERROR;
}
FrontCell = PtrQ->front;
if(PtrQ->front == PtrQ->rear) //キューに要素が1つだけある場合、削除後にキューを空にします
PtrQ->front = PtrQ->rear = NULL;
else
PtrQ->front = FrontCell->Next;
FrontElem = FrontCell->Data;
free(FrontCell); //削除されたノードの領域を解放します
return FrontElem;
}