前言：上次我們已經(jīng)學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)中一個(gè)重要的線性表—棧，那么我們這一次就來(lái)學(xué)習(xí)另外一個(gè)重要的線性表—隊(duì)列。
目錄：
一、
隊(duì)列的概念
二、
隊(duì)列的實(shí)現(xiàn)：
1.隊(duì)列的創(chuàng)建
三、
隊(duì)列的操作
1.初始化隊(duì)列
2.隊(duì)尾入隊(duì)列
3.隊(duì)頭出隊(duì)列
4.獲取隊(duì)列頭部元素
5.獲取隊(duì)列隊(duì)尾元素
6.獲取隊(duì)列中有效元素個(gè)數(shù)
7.檢測(cè)隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0
8.銷毀隊(duì)列
四、
完整代碼展示
隊(duì)列的概念
隊(duì)列的概念及結(jié)構(gòu)：隊(duì)列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊(duì)列具有先進(jìn)先出FIFO(First In First Out) 入隊(duì)列：進(jìn)行插入操作的一端稱為隊(duì)尾 出隊(duì)列：進(jìn)行刪除操作的一端稱為隊(duì)頭。
隊(duì)列的實(shí)現(xiàn)
隊(duì)列也可以數(shù)組和鏈表的結(jié)構(gòu)實(shí)現(xiàn)，使用鏈表的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些，因?yàn)槿绻褂脭?shù)組的結(jié)構(gòu)，出隊(duì)列在數(shù)組頭上出數(shù)據(jù)，效率會(huì)比較低。
我們用三個(gè)文件來(lái)完成對(duì)它的操作。
隊(duì)列的創(chuàng)建：
typedef int QDataType;
// 鏈?zhǔn)浇Y(jié)構(gòu)：表示隊(duì)列
typedef struct QueueNode
{
QDataType val;
struct QueueNode* next;
}QNode;
// 隊(duì)列的結(jié)構(gòu)
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
隊(duì)列的實(shí)現(xiàn)：
隊(duì)列的初始化：
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
隊(duì)列里的頭和尾都為空。
隊(duì)尾入隊(duì)列：
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->val = x;
newnode->next = NULL;
if (pq->ptail == NULL)
{
pq->ptail = pq->phead = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
如果我們的隊(duì)尾元素為空，那么我們的隊(duì)尾就是newnode，如果我們的隊(duì)尾不為空，我們的ptail的下一個(gè)指向newnode，現(xiàn)在的隊(duì)尾就為newnode。
隊(duì)頭出隊(duì)列：
void QueuePop(Queue* pq)
{
assert(pq);
//
assert(pq->phead);
QNode* del = pq->phead;
pq->phead = pq->phead->next;
free(del);
del = NULL;
if (pq->phead == NULL)
pq->ptail = NULL;
pq->size--;
}
如果我們直接刪除隊(duì)頭元素那么我們就無(wú)法訪問(wèn)下一個(gè)元素，所以我們先把隊(duì)頭元素保存起來(lái)，讓現(xiàn)在的隊(duì)頭元素為原來(lái)隊(duì)頭元素的下一個(gè)元素，在給原來(lái)的隊(duì)頭元素刪除。
獲取隊(duì)列頭部元素：
QDataType QueueFront(Queue* pq)
{
assert(pq);
//
assert(pq->phead);
return pq->phead->val;
}
獲取隊(duì)列隊(duì)尾元素：
QDataType QueueBack(Queue* pq)
{
assert(pq);
//
assert(pq->ptail);
return pq->ptail->val;
}
獲取隊(duì)列中有效元素個(gè)數(shù)：
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
size就是我們有效元素的個(gè)數(shù)，這里返回size就可以了。
檢測(cè)隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0：
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL;
}
隊(duì)列為空返回0，不為空返回非0，后面測(cè)試代碼的循環(huán)條件就是不為0，就輸出，為0就跳出循環(huán)。
銷毀隊(duì)列：
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
完整代碼展示：
Queue.h：
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
QDataType val;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
Queue.c：
#include"Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->val = x;
newnode->next = NULL;
if (pq->ptail == NULL)
{
pq->ptail = pq->phead = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
void QueuePop(Queue* pq)
{
assert(pq);
//
assert(pq->phead);
QNode* del = pq->phead;
pq->phead = pq->phead->next;
free(del);
del = NULL;
if (pq->phead == NULL)
pq->ptail = NULL;
pq->size--;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
//
assert(pq->phead);
return pq->phead->val;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
//
assert(pq->ptail);
return pq->ptail->val;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
代碼測(cè)試：
test.c:
#include"Queue.h"
int main()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
printf("%d ", QueueFront(&q));
QueuePop(&q);
printf("%d ", QueueFront(&q));
QueuePop(&q);
QueuePush(&q, 4);
QueuePush(&q, 5);
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
QueueDestroy(&q);
return 0;
}
這里我們先入隊(duì)1,2，3，隊(duì)頭就是1，隊(duì)尾就是3，我們?cè)诔鲫?duì)，先輸出1，在把1出隊(duì)，這樣我們就訪問(wèn)2，在輸出2之后把2出隊(duì)，入隊(duì)4,5，如果我們的隊(duì)列不為0就輸出3,4，5。最后輸出的結(jié)果如下圖：
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-759921.html
相信大家一定可以完美的拿捏隊(duì)列，感謝各位小伙伴的支持，我們下期再見(jiàn)！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-759921.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)—隊(duì)列的實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
