隊列的順序實現
#define MaxSize 10//定義隊列中元素的最大個數
typedef struct {int data[MaxSize];//用靜態數組存放隊列元素int front, rear;//隊頭指針和隊尾指針
} SqQueue;void testQueue() {SqQueue Q;//聲明一個隊列(順序存儲)
}隊列的初始化操作和判空
//初始化隊列
void InitQueue(SqQueue& Q) {//初始時 隊頭、隊尾指針指向0Q->rear = Q->front = 0;
}
//判斷隊列是否為空
bool QueueEmpty(SqQueue Q) {if (q.rear == Q.front) {//判空條件return true;}else {return false;}
}循環隊列——入隊操作
以下情況我們重點先考慮尾指針指向隊尾元素的后一位情況
隊列的入隊操作只能從隊尾入隊(插入)
//入隊
bool EnQueue(SqQueue& Q, int x) {if (Q.rear + 1) % MaxSize == Q.front){//判斷隊滿return false;//隊滿報錯}else {Q.data[Q.rear] = x;//新元素插入隊尾Q.rear = (Q.rear + 1) % MaxSize;//隊尾指針加1取模，隊尾指針后移return true;}
}該函數中的
Q.rear = (Q.rear + 1) % MaxSize;//隊尾指針加1取模這一行代碼實則是將一個順序隊列變成了循環隊列
循環隊列——入隊操作
//出隊（刪除一個隊頭元素，并用x返回）
bool DeQueue(SqQueue& Q, int& x) {if (Q.rear == Q.front) {//判斷隊空return false;//隊空則報錯}else {x = Q.data[Q.front];Q.front = (Q.front + 1) & MaxSize;//隊頭指針后移return true;}
}
循環隊列——讀取隊頭操作
讀取隊頭的操作和出隊操作很類似，只是將表格引用符號去掉，并且不要讓隊頭指針往后移就行
//獲得隊頭元素的值，用x返回
bool GetHead(SqQueue Q, int& x) {if (Q.rear == Q.front) {//判斷隊空return false;//隊空則報錯}else {x = Q.data[Q.front];return true;}
}
void testQueue() {SqQueue Q;//聲明一個隊列(順序存儲)
}計算隊列元素個數：
(rear+MaxSize-front)%MaxSize方法二：增加一個輔助變量size判斷空判滿
由于剛剛第一種方法判空和判滿會造成一些不必要的內存空間浪費，于是我們在隊列中添加一個size來表示隊列的長度，并且記錄隊列的入隊和出隊變化
typedef struct {int data[MaxSize];//用靜態數組存放隊列元素int front,rear;//隊頭指針和隊尾指針int size;//隊列當前長度
} SqQueue;
//初始化隊列
void InitQueue(SqQueue& Q) {//初始時 隊頭、隊尾指針指向0Q.rear = Q.front = 0;Q.size=0;
}
方法三：增加一個輔助變量tag判斷空判滿?
#define MaxSize 10//定義隊列中元素的最大個數
typedef struct {int data[MaxSize];//用靜態數組存放隊列元素int front,rear;//隊頭指針和隊尾指針int tag;//最近進行的是刪除為0/插入為1
} SqQueue;
例子：
// 初始化隊列
void InitQueue(SqQueue *Q) {Q->front = Q->rear = 0;Q->tag = 0;
}// 判斷隊列是否為空
int IsEmpty(SqQueue Q) {return Q.front == Q.rear && Q.tag == 0;
}// 判斷隊列是否已滿
int IsFull(SqQueue Q) {return Q.front == Q.rear && Q.tag == 1;
}// 入隊操作
int EnQueue(SqQueue *Q, int x) {if (IsFull(*Q)) {return 0; // 隊列已滿，入隊失敗}Q->data[Q->rear] = x;Q->rear = (Q->rear + 1) % MaxSize; // 循環使用數組Q->tag = 1;return 1; // 入隊成功
}// 出隊操作
int DeQueue(SqQueue *Q, int *x) {if (IsEmpty(*Q)) {return 0; // 隊列為空，出隊失敗}*x = Q->data[Q->front];Q->front = (Q->front + 1) % MaxSize; // 循環使用數組Q->tag = 0;return 1; // 出隊成功
}
?總結：
