裝飾公司網(wǎng)站seo公司排名教程
目錄
前言
1. 隊列
1.1?隊列的概念
1.2 隊列的結(jié)構(gòu)
2.?隊列的實現(xiàn)
2.1?隊列的定義
2.2 隊列的初始化
2.3?入隊
2.4 出隊
2.5?獲取隊頭元素
2.6?獲取隊尾元素
2.7?判斷空隊列
2.8?隊列的銷毀
3. 隊列完整源碼
Queue.h
Queue.c
- 🎈個人主頁:庫庫的里昂
- ?🎐C/C++領(lǐng)域新星創(chuàng)作者
- ?🎉歡迎 👍點贊?評論?收藏
- ?收錄專欄:數(shù)據(jù)結(jié)構(gòu)與算法
- 🤝希望作者的文章能對你有所幫助,有不足的地方請在評論區(qū)留言指正,大家一起學習交流!🤗
前言
在前幾期的學習中,我們認識了順序表、鏈表和棧這三種線性表,而在本期學習中,我們將會認識別的線性表。跟隨我們的腳本,看看隊列有怎樣的特點。
1. 隊列
1.1?隊列的概念
隊列:只允許在一端進行插入數(shù)據(jù)操作,在另一端進行刪除數(shù)據(jù)操作的特殊線性表,隊列具有先進先出?FIFO(First In First Out)。
- 入隊列:進行插入操作的一端稱為隊尾
- 出隊列:進行刪除操作的一端稱為隊頭
1.2 隊列的結(jié)構(gòu)
2.?隊列的實現(xiàn)
2.1?隊列的定義
在入隊時相當于尾插,我們可以定義一個尾指針來記錄尾的位置。這就使我們傳指針時,要傳遞兩個指針,我們可以把指針放到結(jié)構(gòu)體中,這樣在插入第一個時也可以解決要傳遞二級指針的問題。
定義尾指針可以避免每次尾插時要遍歷一遍鏈表。
typedef int QDateType;typedef struct QueueNode
{QDateType val;struct QueueType* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;
2.2 隊列的初始化
這里的 size 用來記錄隊列中數(shù)據(jù)的個數(shù)。
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}
2.3?入隊
入隊相當于尾插,在入隊時我們要考慮鏈表是否為空。
void QueuePush(Queue* pq, QDateType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->val = x;if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}
2.4 出隊
出隊相當于頭刪,與之前不同的是,當我們刪除最后一個節(jié)點,還要記得處理尾指針。
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--;
}
2.5?獲取隊頭元素
隊頭元素就是頭指針指向的節(jié)點的數(shù)據(jù)域。
QDateType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}
2.6?獲取隊尾元素
我們通過尾指針可以直接找到隊尾,不用遍歷鏈表。
QDateType QueueBack(Queue* pq)
{assert(pq);assert(pq->phead);return pq->ptail->val;
}
2.7?判斷空隊列
利用bool的函數(shù)判斷隊列是否為空,當尾指針為空時,返回true;當尾指針不為空時,返回false。
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}
2.8?隊列的銷毀
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
3. 隊列完整源碼
Queue.h
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int QDateType;typedef struct QueueNode
{QDateType val;struct QueueType* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;void QueueInit(Queue* pq);void QueueDstroy(Queue* pq);void QueuePush(Queue* pq, QDateType x);void QueuePop(Queue* pq);QDateType QueueFront(Queue* pq);QDateType 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 QueueDstroy(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, QDateType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->val = x;if (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(pq->phead);QNode* del = pq->phead;pq->phead = pq->phead->next;free(del);del = NULL;if (pq->phead == NULL){pq->ptail = NULL;}pq->size--;
}QDateType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}QDateType QueueBack(Queue* pq)
{assert(pq);assert(pq->phead);return pq->ptail->val;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
本次的內(nèi)容到這里就結(jié)束啦。希望大家閱讀完可以有所收獲,同時也感謝各位讀者三連支持。文章有問題可以在評論區(qū)留言,博主一定認真認真修改,以后寫出更好的文章。你們的支持就是博主最大的動力。