什么是隊列？

上一篇文章寫了什么是棧，用C語言實現了棧，既然說了棧，不說隊列，感覺總是少了點什么，所以就順手寫一個隊列，而且最近做項目也用到這個隊列的代碼。

棧的特點是先進后出，隊列的特點是先進先出，從這個特點可以知道，隊列是比較友好的，不像棧那樣最開始進去排隊的人，竟然是最后一個出來的。

新建一個隊列

因為我這個例程是使用鏈表實現隊列的，所以新建一個隊列，實際上就是開辟一個內存空間，用來存儲隊列的頭部。跟棧一樣，我們理解了建立一個隊列就是需要建立一個頭，開辟的這個空間，代表的是這個隊列，就好比，你老爸就可以代表你們家庭，不管你家有多少人，有多少個小孩，你老爸始終都是這個家庭的戶主。

/*創建隊列，外部釋放內存*/ QueueInfo_st *createQueue(void) { QueueInfo_st *queue = (QueueInfo_st *)malloc(sizeof(QueueInfo_st)); if(NULL == queue) { printf("malloc failed\n"); return NULL; } queue->next = NULL; return queue; }

向隊列中插入數據

向隊列插入數據，我做的有點麻煩，先是遍歷鏈表，找到這個鏈表的尾部，然后再在鏈表的尾部插入數據，看文章的大神，有好的方法可以指出來，我覺得應該有更加優秀的方法的。

/*入隊列，0表示成，非0表示出錯*/ int queue_push(QueueInfo_st *s,ElementType value) { /*用來保存尾部指針*/ QueueInfo_st *temp = (QueueInfo_st *)malloc(sizeof(QueueInfo_st)); if(NULL == temp) { printf("malloc failed\n"); return FAILURE; } /*找到鏈表的尾部*/ while(s->next != NULL) { s = s->next; } temp->value = value; temp->next = s->next; s->next = temp; return SUCCESS; }

取出隊列的數據

取出隊列的數據，也就是把頭部指向的下一個鏈表里面的數據給取出來，取出來要記得釋放內存哈，這一步尤其重要。

/*出隊列*/ int queue_pop(QueueInfo_st *s,ElementType *value) { /*首先判斷隊列是否為空*/ if(queue_is_empty(s)) return FAILURE; /*找出隊列頂元素*/ *value = s->next->value; /*保存等下需要free的指針*/ QueueInfo_st *temp = s->next; /*更換隊列頂的位置*/ s->next = s->next->next; /*釋放隊列頂節點內存*/ if(temp!=NULL)/*先判斷指針是否為空*/ free(temp); temp = NULL; return SUCCESS; }

源碼例程

#include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <stdbool.h> typedef int32_t ElementType; /*隊列元素類型*/ #define SUCCESS 0 #define FAILURE -1 /*定義隊列結構*/ typedef struct QueueInfo { ElementType value; /*隊列存儲的數據*/ struct QueueInfo *next; /*指向隊列的下一個元素*/ }QueueInfo_st; /*函數聲明*/ QueueInfo_st *createQueue(void); int queue_push(QueueInfo_st *s,ElementType value); int queue_pop(QueueInfo_st *s,ElementType *value); int queue_top(QueueInfo_st *s,ElementType *value); int queue_is_empty(QueueInfo_st *s); /*創建隊列，外部釋放內存*/ QueueInfo_st *createQueue(void) { QueueInfo_st *queue = (QueueInfo_st *)malloc(sizeof(QueueInfo_st)); if(NULL == queue) { printf("malloc failed\n"); return NULL; } queue->next = NULL; return queue; } /*入隊列，0表示成，非0表示出錯*/ int queue_push(QueueInfo_st *s,ElementType value) { /*用來保存尾部指針*/ QueueInfo_st *temp = (QueueInfo_st *)malloc(sizeof(QueueInfo_st)); if(NULL == temp) { printf("malloc failed\n"); return FAILURE; } /*找到鏈表的尾部*/ while(s->next != NULL) { s = s->next; } temp->value = value; temp->next = s->next; s->next = temp; return SUCCESS; } /*出隊列*/ int queue_pop(QueueInfo_st *s,ElementType *value) { /*首先判斷隊列是否為空*/ if(queue_is_empty(s)) return FAILURE; /*找出隊列頂元素*/ *value = s->next->value; /*保存等下需要free的指針*/ QueueInfo_st *temp = s->next; /*更換隊列頂的位置*/ s->next = s->next->next; /*釋放隊列頂節點內存*/ if(temp!=NULL)/*先判斷指針是否為空*/ free(temp); temp = NULL; return SUCCESS; } /*訪問隊列頂元素*/ int queue_top(QueueInfo_st *s,ElementType *value) { /*首先判斷隊列是否為空*/ if(queue_is_empty(s)) { return FAILURE; } *value = s->next->value; return SUCCESS; } /*判斷隊列是否為空，空返回1，未空返回0*/ int queue_is_empty(QueueInfo_st *s) { /*隊列頂指針為空，則隊列為空*/ if(s->next == NULL) { printf("隊列為空\n"); return true; } return false; } int main(void) { int i = 0; int data = 0; QueueInfo_st * queue; queue = createQueue(); for(i = 0 ;i< 20;i++) { queue_push(queue,i); } for(i = 0;i<20;i++) { data = 0; queue_pop(queue,&data); printf("%d \n",data); } }

總結

隊列是基本的數據結構，考試和筆試應該會經常遇到，希望大家在面試的時候，還是能隨手就寫出一個隊列，秒殺其他同學，在實際項目中還需要了解環形隊列，也是先進先出的隊列，但是環形隊列它還體現在環上，我們上面建立的隊列是沒有大小限制的，但是環形隊列是有大小限制的，如果插入的數據大于環形隊列的大小，就會把第一個數據給覆蓋，或者插入失敗，至于是什么邏輯，都是代碼實現的，都要去看代碼理解其中的原理。

附加題（使用C++實現棧）

關于這個附加題，我想起來我有一個鄰居，他女兒現在是小學一年級，班里面的同學讀書都非常厲害，如果考試考個90分以下的，基本就是班級里面的倒數了，現在的行業競爭非常激烈，小學也是一樣，你們以為考試考100分就是第一名了嗎？那么你就是真的想多了，考試考105分都是并列幾個第一名的，所以我們這個題目也是一樣，使用C++來實現一個棧，這個跟上一次的文章剛好呼應，體現了幾個問題，一個是C 和C++的不同，通過面向對象的思想實現棧，代碼會少很多，而且封裝也很好。對于初學者也可以理解類的思想，構造函數和析構函數等等。

這個代碼就無償奉獻給大家，希望這個附加題讓大家比其他同學多5分。

掃碼或長按關注回復「加群?」進入技術群聊

總結

以上是生活随笔為你收集整理的队列，C语言实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。