C語(yǔ)言詳解鏈?zhǔn)疥?duì)列與循環(huán)隊(duì)列的實(shí)現(xiàn)
隊(duì)列的實(shí)現(xiàn)
隊(duì)列是一種先進(jìn)先出（First in First Out）的線性表，簡(jiǎn)稱FIFO。與棧不同，棧是一種后進(jìn)先出（先進(jìn)后出）的線性表。在隊(duì)列中，允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭。假設(shè)隊(duì)列是q=（a1,a2,…,an），那么a1就是隊(duì)頭元素，而an是隊(duì)尾元素。這樣我們就可以刪除時(shí)，總是從a1開始，而插入時(shí)，列在最后。這也比較符合我們通常生活中的習(xí)慣，排在第一個(gè)的優(yōu)先出列，最后來的當(dāng)然在隊(duì)伍的最后。隊(duì)列分為順序隊(duì)列和循環(huán)隊(duì)列。順序隊(duì)列我們可以利用數(shù)組或者鏈表實(shí)現(xiàn)。這里，我們選擇用鏈表實(shí)現(xiàn)順序隊(duì)列。
今天主要介紹鏈表實(shí)現(xiàn)的隊(duì)列和循環(huán)隊(duì)列
鏈?zhǔn)疥?duì)列
隊(duì)列主要有哪些基本操作
// 初始化隊(duì)列 void QueueInit(Queue* q); ? // 隊(duì)尾入隊(duì)列 void QueuePush(Queue* q, QDataType data); // 隊(duì)頭出隊(duì)列 void QueuePop(Queue* q); // 獲取隊(duì)列頭部元素 QDataType QueueFront(Queue* q); // 獲取隊(duì)列隊(duì)尾元素 QDataType QueueBack(Queue* q); // 獲取隊(duì)列中有效元素個(gè)數(shù) int QueueSize(Queue* q); // 檢測(cè)隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0 bool QueueEmpty(Queue* q); // 銷毀隊(duì)列 void QueueDestroy(Queue* q);
鏈?zhǔn)疥?duì)列的定義
typedef int QDataType;
// 鏈?zhǔn)浇Y(jié)構(gòu)：表示隊(duì)列
typedef struct QListNode
{
struct QListNode* _next;
QDataType _data;
}QNode;
?
// 隊(duì)列的結(jié)構(gòu)
typedef struct Queue
{
QNode* _front;
QNode* _rear;
}Queue;鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)
1、初始化隊(duì)列
void QueueInit(Queue* q)
{
assert(q);
q->_front = NULL;
q->_rear = NULL;
}2、銷毀隊(duì)列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->_front;
while (cur != NULL)
{
QNode* next = cur->_next;
free(cur);
cur = next;
}
q->_front = q->_rear = NULL;
}3、隊(duì)列判空
bool QueueEmpty(Queue* q)
{
assert(q);
//if (q->_front == NULL)
//{
// return 1;
//}
//else
//{
// return 0;
//}
return q->_front == NULL;
}4、入隊(duì)操作
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
exit(-1);
}
newnode->_data = data;
newnode->_next = NULL;
if (q->_front == NULL)
{
q->_front = q->_rear = newnode;
}
else
{
q->_rear->_next = newnode;
q->_rear = newnode;
}
}5、出隊(duì)操作
void QueuePop(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
QNode* next = q->_front->_next;
free(q->_front);
q->_front = next;
if (q->_front == NULL)
{
q->_rear = NULL;
}
}6、取隊(duì)頭元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->_front->_data;
}7、取隊(duì)尾操作
QDataType QueueBack(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->_rear->_data;
}8、隊(duì)中有效元素個(gè)數(shù)
int QueueSize(Queue* q)
{
assert(q);
int size = 0;
QNode* cur = q->_front;
while (cur)
{
size++;
cur = cur->_next;
}
return size;
}循環(huán)隊(duì)列
循環(huán)隊(duì)列的定義
循環(huán)隊(duì)列就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。在循環(huán)隊(duì)列結(jié)構(gòu)中，當(dāng)存儲(chǔ)空間的最后一個(gè)位置已被使用而再要進(jìn)入隊(duì)運(yùn)算時(shí)，只需要存儲(chǔ)空間的第一個(gè)位置空閑，便可將元素加入到第一個(gè)位置，即將存儲(chǔ)空間的第一個(gè)位置作為隊(duì)尾。循環(huán)隊(duì)列可以更簡(jiǎn)單防止偽溢出的發(fā)生，但隊(duì)列大小是固定的。在循環(huán)隊(duì)列中，當(dāng)隊(duì)列為空時(shí)，有front=rear，而當(dāng)所有隊(duì)列空間全占滿時(shí)，也有front=rear。為了區(qū)別這兩種情況，規(guī)定循環(huán)隊(duì)列最多只能有MaxSize-1個(gè)隊(duì)列元素，當(dāng)循環(huán)隊(duì)列中只剩下一個(gè)空存儲(chǔ)單元時(shí)，隊(duì)列就已經(jīng)滿了。因此，隊(duì)列判空的條件是front=rear，而隊(duì)列判滿的條件是front=（rear+1)%MaxSize。
循環(huán)隊(duì)列的空間可以重復(fù)利用，解決了普通隊(duì)列的空間浪費(fèi)問題
循環(huán)隊(duì)列的實(shí)現(xiàn)
typedef struct {
int *a;
int front;
int tail;
int k;
} MyCircularQueue;
?
//提前聲明判空判滿
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
//創(chuàng)建循環(huán)隊(duì)列
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* cq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
cq->a=(int*)malloc(sizeof(int)*(k+1));
cq->front=cq->tail=0;
cq->k=k;
return cq;
}
//循環(huán)隊(duì)列入隊(duì)
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj)){
return false;
}
obj->a[obj->tail]=value;
obj->tail++;
obj->tail%=(obj->k+1);
?
return true;
}
//循環(huán)隊(duì)列出隊(duì)
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj)){
return false;
}
obj->front++;
obj->front%=(obj->k+1);
return true;
?
}
//循環(huán)隊(duì)列取隊(duì)頭
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj)){
return -1;
}
return obj->a[obj->front];
}
//循環(huán)隊(duì)列取隊(duì)尾
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj)){
return -1;
}
int i=(obj->tail+obj->k)%(obj->k+1);
return obj->a[i];
}
//循環(huán)隊(duì)列判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front==obj->tail;
}
//循環(huán)隊(duì)列判滿
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->tail+1)%(obj->k+1)==obj->front;
}
//銷毀循環(huán)隊(duì)列
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}到此這篇關(guān)于C語(yǔ)言詳解鏈?zhǔn)疥?duì)列與循環(huán)隊(duì)列的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C語(yǔ)言 隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
淺析結(jié)束程序函數(shù)exit, _exit,atexit的區(qū)別
在一個(gè)程序中最多可以用atexit()注冊(cè)32個(gè)處理函數(shù)，這些處理函數(shù)的調(diào)用順序與其注冊(cè)的順序相反，也即最先注冊(cè)的最后調(diào)用，最后注冊(cè)的最先調(diào)用2013-09-09
C語(yǔ)言實(shí)現(xiàn)手寫Map(數(shù)組+鏈表+紅黑樹)的示例代碼
vscode編譯運(yùn)行c語(yǔ)言報(bào)錯(cuò)亂碼的解決
函數(shù)指針的強(qiáng)制類型轉(zhuǎn)換實(shí)現(xiàn)代碼
C語(yǔ)言驅(qū)動(dòng)開發(fā)之判斷自身是否加載成功詳解
C++ map與set封裝實(shí)現(xiàn)過程講解