??文章主頁(yè)：阿博歷練記
??文章專欄：數(shù)據(jù)結(jié)構(gòu)與算法
??代碼倉(cāng)庫(kù)：阿博編程日記
??歡迎關(guān)注：歡迎友友們點(diǎn)贊收藏+關(guān)注哦??
??前言
友友們，上期阿博給大家介紹了棧的實(shí)現(xiàn)，今天阿博給大家介紹一種新的數(shù)據(jù)結(jié)構(gòu):隊(duì)列.
隊(duì)列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊(duì)列具有先進(jìn)先出FIFO(First In First Out)的性質(zhì)。
入隊(duì)列：進(jìn)行插入操作的一端稱為隊(duì)尾。
出隊(duì)列：進(jìn)行刪除操作的一端稱為隊(duì)頭。
隊(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ì)比較低.
??隊(duì)列
??1.隊(duì)列的結(jié)構(gòu)框架
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
??友友們注意，這兩個(gè)結(jié)構(gòu)體不能合并到一起，因?yàn)樗鼈兯淼囊饬x不一樣，第一個(gè)結(jié)構(gòu)體是每一個(gè)結(jié)點(diǎn)的結(jié)構(gòu)，第二個(gè)結(jié)構(gòu)體代表的是這個(gè)隊(duì)列的結(jié)構(gòu)，它表示的是隊(duì)列整體.
??2.隊(duì)列的初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
??為什么初始化不使用二級(jí)指針
??這里有可能友友們會(huì)有疑問(wèn)，我們初始化不是要改變phead指針和ptail指針，它們兩個(gè)都是結(jié)構(gòu)體指針，我們要改變它們，為什么不用二級(jí)指針呢？這里友友們注意了，phead指針和ptail指針又在一個(gè)新的結(jié)構(gòu)體Queue里面放著，它們就屬于這個(gè)結(jié)構(gòu)體里面的成員，我們要改變它，只需要傳這個(gè)新結(jié)構(gòu)體的地址就可以訪問(wèn)并改變它們了.
這里阿博給友友們總結(jié)幾種不用二級(jí)指針的方法：
?1.我們?cè)诤瘮?shù)外部定義一個(gè)同類型的指針，通過(guò)返回值的方式接收，這本質(zhì)上是一個(gè)值拷貝（賦值）
?2.帶哨兵位的頭結(jié)點(diǎn)，它的本質(zhì)是改變結(jié)構(gòu)體里面的next指針，next指針屬于結(jié)構(gòu)體的成員，所以我們只需要傳結(jié)構(gòu)體的指針就可以訪問(wèn)到它了.
?3.把結(jié)構(gòu)體指針重新放在一個(gè)結(jié)構(gòu)體里面，這樣它就屬于這個(gè)結(jié)構(gòu)體的成員了，我們只需要傳這個(gè)結(jié)構(gòu)體的地址就可以改變結(jié)構(gòu)體指針了.
??3.隊(duì)列的釋放
1.保存下一結(jié)點(diǎn)的地址迭代釋放
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;
}
2.保存當(dāng)前結(jié)點(diǎn)的地址迭代釋放
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* del = cur;
cur = cur->next;
free(del);
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
????友友們，這里要注意兩個(gè)點(diǎn)：?1.如果保存當(dāng)前結(jié)點(diǎn)的地址的話，我們就需要先讓cur=cur->next往后迭代，然后在釋放保留的那個(gè)地址，如果先釋放的話，那么cur=cur->next這一步就會(huì)報(bào)錯(cuò)，此時(shí)cur已經(jīng)被釋放了，我們還在使用，它就是一個(gè)
野指針.?2.如果保留下一結(jié)點(diǎn)地址的話，我們就需要先釋放當(dāng)前結(jié)點(diǎn)，在讓cur=next往后進(jìn)行迭代，如果我們先往后迭代的話，此時(shí)cur=next已經(jīng)指向下一結(jié)點(diǎn)了，我們?cè)诎阉尫牛@樣就會(huì)導(dǎo)致上一個(gè)結(jié)點(diǎn)沒(méi)有釋放和下次再使用cur就是野指針.????
??4.隊(duì)列的插入數(shù)據(jù)
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = x;
newnode->next = NULL;
if (pq->phead == NULL)
{
assert(pq->ptail == NULL);
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
??友友們注意，就算這里是首次插入數(shù)據(jù)，我們也不需要
二級(jí)指針，因?yàn)閜head和ptail指針都在結(jié)構(gòu)體里面放著，所以我們傳這個(gè)結(jié)構(gòu)體的指針就可以改變它們.
??5.隊(duì)列的刪除數(shù)據(jù)
?錯(cuò)誤案例
void QueuePop(Queue* pq)
{
assert(pq);
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
pq->size--;
}
?代碼糾正
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
//1個(gè)結(jié)點(diǎn)
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead =pq->ptail= NULL; //不能對(duì)同一動(dòng)態(tài)開(kāi)辟出來(lái)的空間進(jìn)行多次free釋放，這里我們釋放完pq->phead之后，pq->ptail也已經(jīng)被釋放了，所以我們主要的目的就是把pq->phead和pq->ptail都置空
}
//多個(gè)結(jié)點(diǎn)
else
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
??友友們注意，pq->phead和pq->ptail指向相同的結(jié)點(diǎn)，free(pq->phead)之后就已經(jīng)把這塊內(nèi)存空間釋放了，此時(shí)我們就不能再free(pq->ptail)了，因?yàn)閯?dòng)態(tài)開(kāi)辟出來(lái)的空間不能進(jìn)行多次free釋放.
??6.隊(duì)列取隊(duì)頭數(shù)據(jù)
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->data;
}
這里我們需要斷言隊(duì)列不能為空，如果為空，pq->phead就是空指針，這時(shí)pq->phead->data就是對(duì)空指針的解引用，程序就會(huì)報(bào)錯(cuò).
??7.隊(duì)列取隊(duì)尾數(shù)據(jù)
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
??8.返回隊(duì)列數(shù)據(jù)的個(gè)數(shù)
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
??9.判斷隊(duì)列是否為空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL
&& pq->ptail == NULL;
}
??Queue.h代碼
#pragma once
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}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);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
??Queue.c代碼
#define _CRT_SECURE_NO_WARNINGS 1
#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;
/*QNode* del = cur;
cur = cur->next;
free(del);*/
}
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->data = x;
newnode->next = NULL;
if (pq->phead == NULL)
{
assert(pq->ptail == NULL);
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
//1個(gè)結(jié)點(diǎn)
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail=NULL; //不能對(duì)同一動(dòng)態(tài)開(kāi)辟出來(lái)的空間進(jìn)行多次free釋放，這里我們釋放完pq->phead之后，pq->ptail也已經(jīng)被釋放了，所以我們主要的目的就是把pq->phead和pq->ptail都置空
}
//多個(gè)結(jié)點(diǎn)
else
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL
&& pq->ptail == NULL;
}
??Test.c代碼
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
#include<stdio.h>
TestQueue()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
QueueDestroy(&q);
return 0;
}
int main()
{
TestQueue();
return 0;
}
??代碼效果展示
1.??題目描述
??邏輯分析
友友們，通過(guò)這里也可以看出我們的入棧順序是1,2,3,我們的出棧順序也是1,2,3.
??代碼實(shí)現(xiàn)
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; //top指向棧頂?shù)奈恢?/span>
int capacity;
}ST;
void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst,STDataType x);
STDataType STTop(ST* pst);
void STPop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST* pst);
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->top = 0; //如果我們初始化為0，top就指向棧頂元素的下一個(gè)位置，初始化為-1，top就是指向棧頂元素.
pst->capacity = 0;
}
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->capacity = pst->top = 0;
}
void STPush(ST* pst, STDataType x)
{
assert(pst);
if (pst->top == pst->capacity)
{
int newcapacity= pst->capacity==0 ? 4 : pst->capacity * 2 ;
STDataType* tmp = (STDataType*)realloc(pst->a,newcapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp;
pst->capacity = newcapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
STDataType STTop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
return pst->a[pst->top - 1];
}
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
void STPop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
pst->top--;
}
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
typedef struct {
ST pushst;
ST popst;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
if(obj==NULL)
{
perror("malloc fail");
return;
}
STInit(&obj->pushst);
STInit(&obj->popst);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
STPush(&obj->pushst,x);
}
int myQueuePop(MyQueue* obj) {
int front=myQueuePeek(obj);
STPop(&obj->popst);
return front;
}
int myQueuePeek(MyQueue* obj) {
if(STEmpty(&obj->popst))
{
while(!STEmpty(&obj->pushst))
{
STPush(&obj->popst,STTop(&obj->pushst));
STPop(&obj->pushst);
}
}
return STTop(&obj->popst);
}
bool myQueueEmpty(MyQueue* obj) {
return (STEmpty(&obj->pushst))
&&(STEmpty(&obj->popst));
}
void myQueueFree(MyQueue* obj) {
STDestroy(&obj->popst);
STDestroy(&obj->pushst);
free(obj);
}
2.??題目描述
??邏輯分析
??代碼實(shí)現(xiàn)
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}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);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
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;
/*QNode* del = cur;
cur = cur->next;
free(del);*/
}
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->data = x;
newnode->next = NULL;
if (pq->phead == NULL)
{
assert(pq->ptail == NULL);
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
//1個(gè)結(jié)點(diǎn)
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead =pq->ptail= NULL; //不能對(duì)同一動(dòng)態(tài)開(kāi)辟出來(lái)的空間進(jìn)行多次free釋放，這里我們釋放完pq->phead之后，pq->ptail也已經(jīng)被釋放了，所以我們主要的目的就是把pq->phead和pq->ptail都置空
}
//多個(gè)結(jié)點(diǎn)
else
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL
&& pq->ptail == NULL;
}
typedef struct {
Queue p;
Queue q;
} MyStack;
MyStack* myStackCreate() {
MyStack*obj=(MyStack*)malloc(sizeof(MyStack));
if(obj==NULL)
{
perror("malloc fail");
return;
}
QueueInit(&obj->p);
QueueInit(&obj->q);
return obj;
}
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(&obj->q))
{
QueuePush(&obj->q,x);
}
else
{
QueuePush(&obj->p,x);
}
}
int myStackPop(MyStack* obj) {
Queue* NoFull=&obj->p;
Queue* Full=&obj->q;
if(QueueEmpty(&obj->p))
{
Full=&obj->p;
NoFull=&obj->q;
}
while(QueueSize(NoFull)>1)
{
QueuePush(Full,QueueFront(NoFull));
QueuePop(NoFull);
}
int top=QueueBack(NoFull);
QueuePop(NoFull);
return top;
}
int myStackTop(MyStack* obj) {
if(!QueueEmpty(&obj->p))
{
return QueueBack(&obj->p);
}
else
{
return QueueBack(&obj->q);
}
}
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->p)
&&QueueEmpty(&obj->q);
}
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->p);
QueueDestroy(&obj->q);
free(obj);
}
3.??題目描述
??循環(huán)隊(duì)列
友友們，我們有時(shí)還會(huì)使用一種隊(duì)列叫循環(huán)隊(duì)列。如操作系統(tǒng)課程講解生產(chǎn)者消費(fèi)者模型時(shí)可以就會(huì)使用循環(huán)隊(duì)列。環(huán)形隊(duì)列可以使用
數(shù)組實(shí)現(xiàn)，也可以使用循環(huán)鏈表實(shí)現(xiàn)。
??邏輯分析
?解決方案
??友友們注意，這里我們刪除數(shù)據(jù)的時(shí)候不需要抹除數(shù)據(jù)，我們只需要把front指針往后移動(dòng)就行，因?yàn)槲覀兪钦J(rèn)為front和rear之間的數(shù)據(jù)為有效的數(shù)據(jù)，而且rear的位置是可以存放數(shù)據(jù)的，因?yàn)樗顷?duì)尾數(shù)據(jù)的下一個(gè)位置，所以即使它有數(shù)據(jù)，無(wú)論如何我們也訪問(wèn)不到.
??誤區(qū)1(插入刪除數(shù)據(jù)的取模處理）
友友們注意，這里我們?nèi)霐?shù)據(jù)之后，也不能只讓rear++.
同理，當(dāng)我們刪除數(shù)據(jù)的時(shí)候，也不能只讓front++，我們?cè)诩蛹又笠惨M(jìn)行取模處理.文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-469921.html
??誤區(qū)2(訪問(wèn)隊(duì)尾數(shù)據(jù)）
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-469921.html
??代碼實(shí)現(xiàn)
typedef struct {
int front;
int rear;
int k;
int*a;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a=(int*)malloc(sizeof(int)*(k+1));
obj->front=obj->rear=0;
obj->k=k;
return obj;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->rear+1)%(obj->k+1)==obj->front;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front==obj->rear;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
return false;
obj->a[obj->rear]=value;
obj->rear++;
obj->rear%=(obj->k+1);
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return false;
obj->front++;
obj->front%=(obj->k+1);
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->a[(obj->rear+obj->k)%(obj->k+1)];
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
obj->a=NULL;
free(obj);
}
到了這里，關(guān)于隊(duì)列的實(shí)現(xiàn)（附含三道經(jīng)典例題）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
