1.順序隊列的原理
隊列是限制在兩端進行插入操作和删除操作的線性表，允許進行存入操作的一端稱為“隊尾”，允許進行删除操作的一端稱為“隊頭”，當線性表中沒有元素時，稱為“空隊”，特點 ：先進先出（FIFO）。
typedef int datatype;
#define N 128
// 當front和rear的值相同時，表示隊列為空，但對于循環隊列來講，滿隊時，front和rear的值也相同
// 是以對于隊列來說，當隊列隻剩下一個空位置時，即視為滿隊，即，當(rear+1)%N 等于front時，視為滿隊
typedef struct {
datatype data[N];
int front; // 隊頭元素的下标
int rear; // 隊尾元素的下一個位置的下标（待存入值的位置）
}sequeue;
規定：
1.front指向隊頭元素的位置; rear指向隊尾元素的下一個位置。
2.在隊列操作過程中，為了提高效率，以調整指針代替隊列元素的移動，并将數組作為循環隊列的操作空間。
3.為差別空隊和滿隊，滿隊元素個數比數組實際能容納的個數少1。
2.順序隊列的實作
建立隊列與釋放隊列
sequeue * queue_create() {
sequeue *sq;
if ((sq = (sequeue *)malloc(sizeof(sequeue))) == NULL) {
printf("malloc failed\n");
return NULL;
}
memset(sq->data, 0, sizeof(sq->data));
sq->front = sq->rear = 0; // rear指向待插入位置，front指向目前首位置
return sq;
}
sequeue * queue_free(sequeue *sq) {
if (sq == NULL) {
printf("sq is NULL\n");
return NULL;
}
free(sq); // 如果sq中的data用的是指針，那麼data需要在建立時申請記憶體，在此時釋放記憶體
sq = NULL;
return NULL;
}
入隊與出隊
int enqueue(sequeue *sq, datatype x) {
if (sq == NULL) {
printf("sq is NULL\n");
return -1;
}
// 當隊列隻剩下一個空位置時，即視為滿隊，此時rear指向最後一個空位置，
// 若隊尾在記憶體的末端，則此時(rear+1)%N 等于front，若隊尾在記憶體的中間（循環隊列），則rear+1等于front
// 即，當(rear+1)%N 等于front時，視為滿隊
if ((sq->rear + 1) % N == sq->front) {
printf("sequeue is full\n");
return -1;
}
sq->data[sq->rear] = x;
// 這裡對N取餘是為了應對這種情況：循環隊列，rear指向記憶體末端
// 同時front指向記憶體中間，記憶體的前端還有空餘，此時rear+1就超出記憶體範圍了
// 對N取餘後，就會利用上記憶體前端的空間，構成循環隊列
sq->rear = (sq->rear + 1) % N;
return 0;
}
datatype dequeue(sequeue *sq) {
datatype ret; // 用于傳回出隊的值
ret = sq->data[sq->front];
// 隊首到隊尾索引從低到高，是以這裡是+1不是-1
sq->front = (sq->front + 1) % N; // 同時，對N取餘也是為了适應循環隊列
return ret;
}
判斷空隊與滿隊
int queue_empty(sequeue *sq) {
if (sq == NULL) {
printf("sq is NULL\n");
return -1;
}
return (sq->front == sq->rear ? 1 : 0);
}
int queue_full(sequeue *sq) {
if (sq == NULL) {
printf("sq is NULL\n");
return -1;
}
if ((sq->rear + 1) % N == sq->front) {
return 1;
}
else {
return 0;
}
}
清空隊列
int queue_clear(sequeue *sq) {
if (sq == NULL) {
printf("sq is NULL\n");
return -1;
}
sq->front = sq->rear = 0;
return 0;
}
3.鍊式隊列的原理與實作
插入操作在隊尾進行，删除操作在隊頭進行，由隊頭指針和隊尾指針控制隊列的操作。
typedef int data_t;
typedef struct node {
data_t data;
struct node_t *next;
} listnode, *linklist;
typedef struct {
linklist_t front, rear; // 這裡front和rear還是對應位置的索引，不過是以指針的形式，指向節點類型的變量
} linkqueue;
建立和釋放隊列
linkqueue * queue_create() {
linkqueue *lq;
if ((lq = (linkqueue *)malloc(sizeof(linkqueue))) == NULL) {
printf("malloc linkqueue failed\n");
return NULL;
}
// 建立時，front和rear都指向同一個節點，即頭節點，而不是隊頭節點
lq->front = lq->rear = (linklist)malloc(sizeof(listnode));
if (lq->front == NULL) {
printf("malloc node failed\n");
return NULL;
}
lq->front->data = 0;
lq->front->next = NULL; //此時rear也指向頭節點，而不是頭節點中的next，這兩句話用lq->rear代替lq->front依然正确
return lq;
}
linkqueue * queue_free(linkqueue *lq) {
linklist p;
if (lq == NULL) {
printf("lq is NULL\n");
return NULL;
}
while (lq->front) { // 和清空隊列的不同之處在于，頭指針也釋放
p = lq->front;
lq->front = p->next;
printf("free:%d\n", p->data);
free(p);
}
free(lq); // 和清空隊列的不同之處在于，用于描述隊列資訊的結構體也被釋放
lq = NULL;
return NULL;
}
入隊和出隊
int enqueue(linkqueue *lq, datatype x) {
linklist p;
if (lq == NULL) {
printf("lq is NULL\n");
return -1;
}
// 先建立一個節點：1.申請記憶體 2.初始化data和*next
if ((p = (linklist)malloc(sizeof(listnode))) == NULL) {
printf("malloc node failed\n");
return -1;
}
p->data = x;
p->next = NULL;
lq->rear->next = p; // 連上
lq->rear = p; // 移動指針
return 0;
}
datatype dequeue(linkqueue *lq) {
linklist p;
if (lq == NULL) {
printf("lq is NULL\n");
return -1;
}
// 這裡涉及到一個思想，因為鍊式隊列涉及到頭節點，和隊頭可能沖突
// 出隊其實出的應該是隊頭，不應該出頭節點，這裡出隊時，出的是頭節點
// 思想就是：出了頭節點後，認為隊頭就是新的頭節點，隊列中的第二個元素成為新的隊頭
// 如此一來，就相當于把隊頭出掉了，真實情況是隊頭被當作了新的頭節點，它的data值也就每人在乎了
p = lq->front;
lq->front = p->next; // 隊頭成為新的頭節點
free(p);
p = NULL;
return (lq->front->data);
}
隊列是否為空
int queue_empty(linkqueue *lq) {
if (lq == NULL) {
printf("lq is NULL\n");
return -1;
}
return (lq->front == lq->rear ? 1 : 0); // front和rear指向的節點相同，視為空
}
清空隊列
// 由于這是鍊式隊列，是以清空隊列應該是把頭節點外的所有節點都釋放
int queue_clear(linkqueue *lq) {
linklist p;
if (lq == NULL) {
printf("lq is NULL\n");
return -1;
}
while (lq->front->next) { // 這裡保留了頭節點，從隊頭開始釋放
p = lq->front;
lq->front = p->next;
printf("clear free:%d\n", p->data);
free(p);
p = NULL;
}
return 0;
}
4.棧和隊列的應用
球鐘問題
工作原理
問題
為什麼隊列中球數為27：小時容器11個 + 5分鐘容器11個 + 1分鐘容器4個 = 26個，第27個球的作用很特殊，作用是把這26個清空，實作11:59到00:00的轉變。
容器：是棧，有最大容量，故選擇順序棧。
由于循環隊列涉及到取餘操作，鍊式隊列用起來相對簡單，故選擇鍊式隊列。
#include <stdio.h>
#include "linkqueue.h"
#include "sqstack.h"
int check(linkqueue * lq);
int main(int argc, const char *argv[])
{
linkqueue *lq; // 描述鍊式隊列的結構體，裡面有front，rear
sqstack *s_hour, *s_five, *s_min; // 定義了3個結構體指針，指向順序棧對象
int value;
int i, min = 0;
if ((lq = queue_create()) == NULL) { // 建立鍊式隊列
return -1;
}
for (i = 1; i <= 27; i++) { // 将27個球入隊
enqueue(lq, i);
}
if ((s_hour = stack_create(11)) == NULL) { // 建立特定容量的順序棧
return -1;
}
if ((s_five = stack_create(11)) == NULL) {
return -1;
}
if ((s_min = stack_create(4)) == NULL) {
return -1;
}
while (1) {
min++; // 這裡記錄次數，因為題目問的就是min有多少次
if (!queue_empty(lq)) { // 如果隊列還有數
value = dequeue(lq); // 出隊一個數給value，利用value将這個數送入棧
if (!stack_full(s_min)) {
stack_push(s_min, value); // 後面代碼不再執行
} else { // 此時value中的球還沒入棧，else執行，說明min棧滿了，這個球會在後面給到5min棧
while (!stack_empty(s_min)) {
enqueue(lq, stack_pop(s_min)); //*将min棧出棧 同時入隊到隊列，直到棧空為止
}
if (!stack_full(s_five)) { // 這裡注意括号，這個if是在else裡面的，即此時min棧滿了，但又被清空了
stack_push(s_five, value); // min棧滿了，清空min棧後，5min棧入棧一進制素，後面代碼不再執行
} else { // else執行，說明min棧、5min棧都滿了
while (!stack_empty(s_five)) { // while循環，開始清理5min棧
enqueue(lq, stack_pop(s_five)); // 出棧後入隊
}
if (!stack_full(s_hour)) {
stack_push(s_hour, value); // 之前的5min棧滿了，小時棧自然要push一個值，後面不再執行
} else { // 此時的value是第27個球，else執行，說明min棧、5min棧、小時棧都滿了
while (!stack_empty(s_hour)) {
enqueue(lq, stack_pop(s_hour)); // 清空小時棧後入隊
}
enqueue(lq, value); // 這個第27個球，不會入棧，在外邊溜達一圈後直接歸隊
//上面語句執行完後，27個球全部歸隊，時間置為00:00
if (check(lq) == 1) {
break; // 這個break跳出的是while(1)循環，其他while循環均不在break外層
}
}
}
}
}
} // while(1)的回括号
printf("total:%d\n", min);
printf("dequeue:");
while (!queue_empty(lq))
printf("%d ", dequeue(lq));
puts("");
return 0;
} // main的回括号
// 檢查傳入的鍊式隊列，是否為升序，若是傳回1，不是傳回0
int check(linkqueue * lq) {
linklist p;
if (lq == NULL) {
printf("lq is NULL\n");
return -1;
}
p = lq->front->next; // p指向隊頭
while (p && p->next) { // 隊頭和隊頭後面一個元素均非空時
if (p->data < p->next->data) {
p = p->next;
} else {
return 0;
}
}
return 1;
}
相關題目
1、鍊式隊列有假溢出麼？鍊式隊列需要判空判滿麼？為什麼？
2、代碼實作鍊式隊列，輸入數字入隊，輸入字元出隊。
1、鍊式隊列沒有假溢出，鍊式隊列可以判空，不需要判滿，鍊式隊列每次入隊會建立節點，每次出隊會釋放節點，沒有明确的長度限制，故不涉及溢出和滿隊列，當鍊式隊列的front和rear指向同一個節點時，視鍊式隊列為空隊列。
2、可以嘗試下實作輸入多位數。用%d，判斷scanf的傳回值就知道輸入的是字元還是數字了。
int main()
{
int value;
//char ch;
linkqueue lp = listqueue_create();
printf("Please enter a character or a number from 0 to 9:\nEnter '?' to stop.\n");
while (1) {
char ch;
scanf("%c", &ch);
if (isalpha(ch))
printf("%d has dequeued.\n", dequeue(lp));
if (isdigit(ch)) {
ch = (int)(ch - '0');
printf("%d has enqueued.\n", ch);
enqueue(lp, ch);
}
if (ch == '?')
break;
}
while (lp->front->next!= NULL) {
printf("%d ", dequeue(lp));
}
puts("");
return 0;
}