c語言建立隊(duì)列

• 一、順序隊(duì)列
• • 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)
  • 順序隊(duì)列的討論
  • • "下溢"現(xiàn)象
    • "真上溢"現(xiàn)象
  • "假上溢"現(xiàn)象
• 二、如何解決"假上溢"問題
• 三、循環(huán)隊(duì)列
• • 循環(huán)隊(duì)列說明
  • 循環(huán)隊(duì)列的實(shí)現(xiàn)方法
  • • 1、設(shè)置一個(gè)標(biāo)記以區(qū)別隊(duì)列是空還是滿
    • 2、使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)
    • 3、保留對(duì)空條件，修改隊(duì)滿條件（常用）
  • 循化隊(duì)列的存儲(chǔ)結(jié)構(gòu)定義
  • 初始化隊(duì)列
  • 設(shè)置標(biāo)志
  • • 入隊(duì)操作
    • 出隊(duì)操作
  • 設(shè)置計(jì)數(shù)器方法
  • • 入隊(duì)操作
    • 出隊(duì)操作
  • 方法三
  • • 入隊(duì)操作
    • 出隊(duì)操作
  • 其余操作
• 四、鏈?zhǔn)疥?duì)列
• • 說明
  • 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
  • 入隊(duì)操作
  • 出隊(duì)操作
  • 其余操作

一、順序隊(duì)列

因?yàn)轫樞蜿?duì)列實(shí)現(xiàn)比較簡(jiǎn)單，所以就來談?wù)剬?shí)現(xiàn)的思路和一些注意事項(xiàng)。

隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列，是利用一組連續(xù)的存儲(chǔ)單元(一維數(shù)組)依次存放從隊(duì)首到隊(duì)尾的各個(gè)元素。由于隨著人隊(duì)和出隊(duì)操作的變化，隊(duì)列的隊(duì)頭和隊(duì)尾的位置是變動(dòng)的，所以應(yīng)設(shè)置兩個(gè)整型變量front和rear，分別指示隊(duì)頭和隊(duì)尾在數(shù)組空間中的位置，通常稱from為隊(duì)頭指針，rear為隊(duì)尾指針，它們的初值在隊(duì)列初始化時(shí)均應(yīng)置為0，并約定在非空隊(duì)列里，隊(duì)首指針from始終指向隊(duì)頭元素，隊(duì)尾指針rear始終指向隊(duì)尾元素的下一個(gè)位置。

一般在順序存儲(chǔ)結(jié)構(gòu)中，如果用雙指針來進(jìn)行操作，一般移動(dòng)（或者先移動(dòng)的都是指向最后邊元素的下一個(gè)位置，目的是方便操作。

順序隊(duì)列的討論

"下溢"現(xiàn)象

當(dāng)隊(duì)列為空，即font == rear，若作出出隊(duì)列的操作產(chǎn)生的溢出現(xiàn)象，稱為下溢。

"真上溢"現(xiàn)象

當(dāng)rear == MAXQSIZE時(shí)，若作出入隊(duì)列的操作產(chǎn)生的溢出現(xiàn)象，稱為真上溢。

"假上溢"現(xiàn)象

有真必有假嘛，假上溢指的是隨著隊(duì)列出隊(duì)與入隊(duì)的操作，頭指針和尾指針只增加不減少，致使被刪除元素的空間無法使用。因此，盡管隊(duì)列中實(shí)際元素個(gè)數(shù)可能遠(yuǎn)遠(yuǎn)小于數(shù)組的大小，但可能尾指針可能已經(jīng)超出數(shù)組的大小而無法進(jìn)行入隊(duì)操作，稱為 "假上溢"現(xiàn)象.

二、如何解決"假上溢"問題

• 當(dāng)出現(xiàn)“假上溢”現(xiàn)象時(shí)，把所有的元素向低端移動(dòng)，使得空位從高端區(qū)移向低端區(qū)，顯然這種方法很浪費(fèi)時(shí)間。
• 將存儲(chǔ)隊(duì)列元素的一維數(shù)組首尾相接，形成一個(gè)環(huán)狀。將這種形式表示的隊(duì)列稱為循環(huán)隊(duì)列(Circular Queue)。
• 采用鏈?zhǔn)疥?duì)列。

三、循環(huán)隊(duì)列

循環(huán)隊(duì)列說明

在循化隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時(shí)，隊(duì)頭和對(duì)尾指針仍要加1。只不過當(dāng)首、隊(duì)尾指針指向數(shù)組上界( (MAXSIZE?1) )時(shí)，其加1操作的結(jié)果是指向數(shù)組的下界0，循環(huán)隊(duì)列不會(huì)上溢。同樣是約定在非空循環(huán)隊(duì)列里，隊(duì)首指針始終指向隊(duì)頭元素，隊(duì)尾指針始終指向隊(duì)尾元素的下一個(gè)位置。因此，真正實(shí)用的順序隊(duì)列是循環(huán)隊(duì)列。

循環(huán)隊(duì)列的實(shí)現(xiàn)方法

1、設(shè)置一個(gè)標(biāo)記以區(qū)別隊(duì)列是空還是滿

設(shè)置標(biāo)志flag，當(dāng)Q.font ==Q.rear 且flag = 0時(shí)為隊(duì)空，當(dāng)Q.font ==Q.rear 且flag = 1時(shí)為隊(duì)滿。

2、使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)

設(shè)置一個(gè)變量count 來記錄元素中的個(gè)數(shù)，當(dāng)count ==0時(shí)為空，當(dāng)count = =MAXQSIZE -1 時(shí)為滿

3、保留對(duì)空條件，修改隊(duì)滿條件（常用）

少用一個(gè)元素的存儲(chǔ)單元，未用單元不確定在哪一個(gè)位置，約定以“隊(duì)列頭指針在隊(duì)列尾指針的下一位置(指環(huán)狀的下一位置)上”作為隊(duì)列呈“滿”狀態(tài)的標(biāo)志。當(dāng)存儲(chǔ)循環(huán)隊(duì)列的數(shù)組中只有一個(gè)空閑單元時(shí)，將循環(huán)隊(duì)列視為隊(duì)滿，此時(shí)隊(duì)尾指針和隊(duì)頭指針正好相差1，因此，隊(duì)滿條件為 。(Q?rear+1)%MAXQSIZE=Q.font。

循化隊(duì)列的存儲(chǔ)結(jié)構(gòu)定義

# define MAXQSIZE 100 //定義隊(duì)列最大容量（長度） #define QElemType int //定義隊(duì)列元素類型typedef struct {QElemType base[MAXQSIZE];int font, rear; }SqQueue;

初始化隊(duì)列

//初始化一個(gè)隊(duì)列 void init(SqQueue& Q) {Q.font = 0;Q.rear = 0; }

設(shè)置標(biāo)志

入隊(duì)操作

void push(SqQueue& Q, int val){if(flag == 1){printf("隊(duì)列已滿\n");return;}Q.base[Q.rear] = val; //添加到隊(duì)列Q.rear++;if(Q.rear == MAXQSIZE)flag =1; }

出隊(duì)操作

//出隊(duì)操作 int pop(SqQueue& Q) {if (!flag) {printf("隊(duì)列為空\n");return 0;}int val = Q.base[Q.font];Q.font--;if(Q.font == Q.rear)flag = 0;return val; }

設(shè)置計(jì)數(shù)器方法

入隊(duì)操作

void push(SqQueue& Q, int val){if(count== MAXQSIZE){printf("隊(duì)列已滿\n");return;}Q.base[Q.rear] = val; //添加到隊(duì)列Q.rear++;count ++; }

出隊(duì)操作

//出隊(duì)操作 int pop(SqQueue& Q) {if (count == 0) {printf("隊(duì)列為空\n");return 0;}int val = Q.base[Q.font];Q.font--;Q.count --;return val; }

方法三

入隊(duì)操作

// 入隊(duì)列操作 void push(SqQueue& Q, int val) {if ((Q.rear + 1) % MAXQSIZE == Q.font) {printf("隊(duì)列已滿\n");return;}Q.base[Q.rear] = val; //添加到隊(duì)列Q.rear = (Q.rear + 1) % MAXQSIZE; //隊(duì)尾指針后移 }

出隊(duì)操作

//出隊(duì)操作 int pop(SqQueue& Q) {if (Q.font == Q.rear) {printf("隊(duì)列為空\n");return 0;}int val = Q.base[Q.font];Q.font = (Q.font + 1) % MAXQSIZE;return val; }

其余操作

//判斷隊(duì)列是否為空 int empty(SqQueue& Q) {if (Q.font == Q.rear)return 1;elsereturn 0; }// 返回隊(duì)列第一個(gè)元素int font(SqQueue& Q) {if (Q.font == Q.rear) {printf("隊(duì)列為空\n");return 0;}return Q.base[Q.font]; }//返回隊(duì)列中最后一個(gè)元素 int back(SqQueue& Q) {if (Q.font == Q.rear) {printf("隊(duì)列為空\n");return 0;}return Q.base[Q.rear]; }//返回隊(duì)列中元素個(gè)數(shù) int size(SqQueue& Q) {return (Q.rear - Q.font + MAXQSIZE) % MAXQSIZE; }//打印所以元素 void show(SqQueue Q) {while (!empty(Q)) {printf("%d ", pop(Q));} }

四、鏈?zhǔn)疥?duì)列

說明

鏈?zhǔn)疥?duì)列與鏈?zhǔn)綏Ｓ幸稽c(diǎn)不同是，鏈?zhǔn)綏Ｊ菦]有頭結(jié)點(diǎn)的單鏈表，而鏈?zhǔn)疥?duì)列是由頭結(jié)點(diǎn)的，剛開始頭指針與尾指針同時(shí)指向頭節(jié)點(diǎn)。

區(qū)別于順序存儲(chǔ)的的雙指針，尾指針是指向最后一個(gè)節(jié)點(diǎn)。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

#define QElemType int //元素類型typedef struct QNode { //隊(duì)列的節(jié)點(diǎn)結(jié)構(gòu)QElemType data;QNode* next; }QNode, * Queueptr;typedef struct {Queueptr font; //隊(duì)頭指針Queueptr rear; //隊(duì)尾指針 }LinkQueue;

入隊(duì)操作

//入隊(duì)操作 void push(LinkQueue& Q, QElemType val) {//創(chuàng)建新節(jié)點(diǎn)QNode* node;node = (QNode*)malloc(sizeof(QNode));if (!node) {printf("分配內(nèi)存失敗\n");return;}node->data = val; node->next = NULL; //形成新節(jié)點(diǎn)Q.rear->next = node; //新節(jié)點(diǎn)插入隊(duì)尾，Q.rear 相當(dāng)于取得一個(gè)節(jié)點(diǎn)的地址Q.rear = node; //尾指針后移 }

出隊(duì)操作

**注意：**當(dāng)鏈?zhǔn)疥?duì)列只有一個(gè)節(jié)點(diǎn)時(shí)，如果直接刪除節(jié)點(diǎn)，因?yàn)槲仓羔樦赶蛟摴?jié)點(diǎn)會(huì)導(dǎo)致失去尾指針，所以在刪除前要先將頭指針賦值給尾指針。

//出隊(duì)操作 QElemType pop(LinkQueue& Q) {if (Q.font == Q.rear) {printf("隊(duì)列為空\n");return 0;}QNode* p = Q.font->next;//取出隊(duì)頭指針QElemType val = p->data; //取出隊(duì)頭數(shù)據(jù)Q.font->next = p->next;//頭指針后移if (p == Q.rear)Q.rear = Q.font; //防止只有一個(gè)節(jié)點(diǎn)時(shí)丟失尾指針free(p);//釋放空間return val; }

其余操作

//初始化隊(duì)列 void init(LinkQueue& Q) {Q.font = Q.rear = (QNode*)malloc(sizeof(QNode));if (!Q.font) {printf("分配內(nèi)存失敗\n");return;}Q.font->next = NULL; } //判斷隊(duì)列是否為空 int empty(LinkQueue Q) {if (Q.font == Q.rear)return 1;elsereturn 0; }//讀取對(duì)頭元素 QElemType font(LinkQueue& Q) {if (Q.font == Q.rear) {printf("隊(duì)列為空\n");return -1;}QElemType val = Q.font->next->data;/*可以分解為* QNode * p = Q.font->next;* QElemType val = p->data;*/return val; }//讀取隊(duì)尾元素 QElemType back(LinkQueue& Q) {if (Q.font == Q.rear) {printf("隊(duì)列為空\n");return -1;}QElemType val = Q.rear->data;return val; }//銷毀隊(duì)列 void clear(LinkQueue& Q) {//引用型while (Q.font) {Q.rear = Q.font->next; //令尾指針指向隊(duì)列的第一個(gè)元素free(Q.font); //在釋放后可以不用將，指針置為空，不容易出現(xiàn)野指針Q.font = Q.rear; //第一次是頭結(jié)點(diǎn)，后面的是元素節(jié)點(diǎn)} }

總結(jié)

以上是生活随笔為你收集整理的c语言建立队列（顺序队列、循化队列和链式队列）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。