一、隊列的基本概念

1.隊列定義

隊列是一種先進先出的線性表數據結構（First in First out）,現實中的例子就是，排隊購票，先排隊的先購票，購完票之后直接從這個隊中離開，后來的在這個隊后面排隊，這就是隊列。

如圖;

這就是一個空的隊列，從隊尾入隊，從隊頭出隊

2.常見的基本操作

• initQueue：初始化隊列
• empty: 判斷隊列是否為空
• push:入隊操作
• pop：出隊操作
• Front:獲取隊頭元素

3.數據結構定義

為了鍛煉高度模塊化（分層設計），這里我們直接嵌套，不在Queue中直接定義數組，而是重新抽象出一個獨立的vector數據結構作為底層容器，讓Queue通過組合的方式使用vector來實現其功能。這種設計強調關注點分離，將內存管理的職責交給vector模塊，而Queue模塊只需專注于隊列特有的邏輯操作。

typedef struct Queue {vector* data;int size,head,tail;//size記錄當前隊列有多少元素
}Queue;

二、代碼實現

首先引用頭文件，宏定義隊列的開始元素為多少，定義vector及Queue

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include <stdbool.h>
#define BEGIN_SIZE 6
typedef struct vector {int* val;int size;//記錄當前容量
}vector;
typedef struct Queue {vector* data;int size,head,tail;//size記錄當前隊列有多少元素
}Queue;

初始化Queue

Queue *initQueue() {Queue* q = (Queue*)malloc(sizeof(Queue));q->data = initVector();q->head = q->tail = q->size = 0;return q;
}

要想初始化Queue，那么也就要初始化vector

vector* initVector()
{vector * v=(vector*)malloc(sizeof(vector));v->size = BEGIN_SIZE;v->val = (int*)malloc(sizeof(int) * BEGIN_SIZE);return v;
}

這樣隊列的初始化就實現了，下來我們依次實現隊列的基本功能：

• empty: 判斷隊列是否為空
• push:入隊操作
• pop：出隊操作
• Front:獲取隊頭元素

empty():

bool empty(Queue* q) {return q->size == 0;//如果當前元素的個數等于 0 ，那么則證明隊列為空
}

push():

int push(Queue* q, int val) {checkFull(q); /*如果隊列已經滿了,擴容隊列*/q->data->val[q->tail++] = val;q->size++;return 1;
}

pop():

int pop(Queue* q) {if (empty(q))/*如果隊列為空的話，則返回-1代表彈出失敗*/ {printf("pop: 隊列為空\n");return -1;}int count = 0;while (count < q->tail - 1) {q->data->val[count] = q->data->val[count + 1];count++;}q->tail--;q->size--;return 1;
}

解釋下，這里為什么count<q->tail-1 為什么不是 count<q->tail呢
例如，隊列中有三個元素，那么tail的值就是3，count從0開始，一共要循環到3次，最后一次的count等于 2 ，這個時候 q->data->val[count] = q->data->val[count + 1];這一句就會變為q->data->val[2] = q->data->val[3];，此時 3 這個位置是tail的位置，在內存中并沒有賦值，內存中的值是未定義的（可能是垃圾值）

Front():

int Front(Queue* q) {if (empty(q)) {printf("Front 隊列為空\n");return -1;}return q->data->val[q->head];
}

反過頭處理checkFull(),檢查隊列是否為滿，滿的話則需要擴容

checkFull():

void checkFull(Queue *q) {if (q->size == q->data->size) {int newSize = q->data->size * 2;int * newVal=(int *)realloc(q->data->val, sizeof(int) * newSize);if (newVal == NULL) {printf("error checkFull\n");exit(-1);}q->data->val = newVal;q->data->size = newSize;}return;
}

查看隊列所有元素

outAll():

void outAll(Queue* q) {printf("Queue: ");for (int i = q->head; i < q->tail; i++) {printf("%3d ", q->data->val[i]);}printf("\n");return;
}

最后釋放內存

freeQueue():

void freeQueue(Queue* q) {freeVector(q->data);free(q);return;
}

freeVector():

void freeVector(vector* v) {free(v->val);free(v);return;
}

main函數(測試函數)

int main() {Queue* q = initQueue();//初始化一個隊列pop(q);//在空隊列時彈出，應該輸出 pop: 隊列為空Front(q);//在空隊列時獲取隊頭元素，應該輸出 Front: 隊列為空srand(time(NULL));
#define MAX_OP 10for (int i = 0; i < MAX_OP; i++) {int op = rand() % 5, val = rand() % 100;switch (op) {case 0://pop操作printf("front of queue %d 彈出此元素\n", Front(q));pop(q);break;case 1:case 2:case 3:case 4://push操作printf("將 %d push進隊列\n", val);push(q, val);break;}outAll(q);}printf("隊頭元素為: %3d\n",Front(q));return 0;
}

完整代碼

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define BEGIN_SIZE 6
typedef struct vector {int* val;int size;//記錄當前容量
}vector;
typedef struct Queue {vector* data;int size, head, tail;//size記錄當前隊列有多少元素
}Queue;
vector* initVector()
{vector * v=(vector*)malloc(sizeof(vector));if (v == NULL) {printf("error initVector\n");exit(-1);}v->size = BEGIN_SIZE;v->val = (int*)malloc(sizeof(int) * BEGIN_SIZE);return v;
}
Queue *initQueue() {Queue *q = (Queue*)malloc(sizeof(Queue));if (q == NULL) {printf("error initQueue\n");exit(-1);}q->data = initVector();q->head = q->tail = q->size = 0;return q;
}
bool empty(Queue* q) {return q->size == 0;
}
void checkFull(Queue *q) {if (q->size == q->data->size) {int newSize = q->data->size * 2;int * newVal=(int *)realloc(q->data->val, sizeof(int) * newSize);if (newVal == NULL) {printf("error checkFull\n");exit(-1);}q->data->val = newVal;q->data->size = newSize;}return;
}
int push(Queue* q, int val) {checkFull(q); /*如果隊列已經滿了,擴容隊列*/q->data->val[q->tail++] = val;q->size++;return 1;
}int pop(Queue* q) {if (empty(q))/*如果隊列為空的話，則返回-1代表彈出失敗*/ {printf("pop: 隊列為空\n");return -1;}int count = 0;while (count < q->tail - 1) {q->data->val[count] = q->data->val[count + 1];count++;}q->tail--;q->size--;return 1;
}int Front(Queue* q) {if (empty(q)) {printf("Front: 隊列為空\n");return -1;}return q->data->val[q->head];
}void outAll(Queue* q) {printf("Queue: ");if (empty(q)) {printf("NULL\n");return;}for (int i = q->head; i < q->tail; i++) {printf("%3d ", q->data->val[i]);}printf("\n");return;
}void freeVector(vector* v) {free(v->val);free(v);return;
}void freeQueue(Queue* q) {freeVector(q->data);free(q);return;
}int main() {Queue* q = initQueue();//初始化一個隊列pop(q);//在空隊列時彈出，應該輸出 pop: 隊列為空Front(q);//在空隊列時獲取隊頭元素，應該輸出 Front: 隊列為空srand(time(NULL));
#define MAX_OP 10for (int i = 0; i < MAX_OP; i++) {int op = rand() % 5, val = rand() % 100;switch (op) {case 0://pop操作printf("front of queue %d 彈出此元素\n", Front(q));pop(q);break;case 1:case 2:case 3:case 4://push操作printf("將 %d push進隊列\n", val);push(q, val);break;}outAll(q);}printf("隊頭元素為: %3d\n",Front(q));return 0;
}