C語言數(shù)據(jù)結(jié)構(gòu)與算法之隊列的實現(xiàn)詳解
隊列的概念及結(jié)構(gòu)
隊列：只允許在一端進行插入數(shù)據(jù)操作，在另一端進行刪除數(shù)據(jù)操作的特殊線性表，隊列具有先進先出FIFO(First In First Out)的原則
入隊列：進行插入操作的一端稱為隊尾
出隊列：進行刪除操作的一端稱為隊頭
隊列的結(jié)構(gòu)在生活中非常地常見，比如排隊時的抽號機就是一個典型的隊列結(jié)構(gòu)。那隊列如何實現(xiàn)呢？我們一起來看一下。
隊列的實現(xiàn)
隊列也可以數(shù)組和鏈表的結(jié)構(gòu)實現(xiàn)，使用鏈表的結(jié)構(gòu)實現(xiàn)更優(yōu)一些。因為如果使用數(shù)組的結(jié)構(gòu)，出隊列在數(shù)組頭上出數(shù)據(jù)，需要挪動數(shù)據(jù)，時間復(fù)雜度為O(N)，效率會比較低。
Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* head; // 頭指針
QNode* tail; // 尾指針
int size; // 節(jié)點的個數(shù)
}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);
隊列要實現(xiàn)的函數(shù)接口有：初始化隊列、銷毀隊列、數(shù)據(jù)入隊、數(shù)據(jù)出隊、返回隊頭的數(shù)據(jù)、返回隊尾的數(shù)據(jù)、判斷隊列是否為空以及隊列中數(shù)據(jù)的個數(shù)。這些接口實現(xiàn)起來也不是很難，我們一起來看一下。
Queue.c
#include "Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* del = cur;
cur = cur->next;
free(del);
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
// 隊列中沒有節(jié)點
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
// 隊列中只有一個節(jié)點
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* del = pq->head;
pq->head = pq->head->next;
free(del);
//del = NULL;
}
pq->size--;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
//return pq->head == NULL && pq->tail == NULL;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
初始化隊列
頭指針和尾指針都指向空，隊列元素個數(shù)初始化為0
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
銷毀隊列
利用while循環(huán)將申請的節(jié)點一一釋放掉，然后頭指針pq->head和尾指針pq->tail指向空，棧的數(shù)據(jù)個數(shù)置為 0pq->size = 0
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* del = cur;
cur = cur->next;
free(del);
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
數(shù)據(jù)入隊
1.申請新的節(jié)點newnode newnode->data = x,newnode->next = NULL
2.數(shù)據(jù)入隊：當pq->tail == NULL時，隊列中沒有節(jié)點，那么頭指針和尾指針都賦值為newnode pq->head = pq->tail = newnode；當pq->tail != NULL時，隊列中有節(jié)點，那么尾部鏈接上新節(jié)點newnode，然后newnode成為新的尾結(jié)點。
3.隊列數(shù)據(jù)個數(shù)加一pq->size++
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
// 隊列中沒有節(jié)點
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
數(shù)據(jù)出隊
1.判斷隊列是否為空
2.數(shù)據(jù)出隊：當pq->head->next == NULL時，隊列中只有一個節(jié)點，釋放該節(jié)點，頭指針和尾指針都指向空；當pq->head->next != NULL時，釋放讓頭指針指向當前節(jié)點的下一個節(jié)點，釋放原來的頭節(jié)點
3.隊列數(shù)據(jù)個數(shù)減一pq->size--
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
// 隊列中只有一個節(jié)點
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* del = pq->head;
pq->head = pq->head->next;
free(del);
//del = NULL;
}
pq->size--;
}
返回隊頭數(shù)據(jù)
先判斷隊列是否為空，不為空時，返回隊頭數(shù)據(jù)。
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
返回隊尾數(shù)據(jù)
先判斷隊列是否為空，不為空時，返回隊尾數(shù)據(jù)。
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
判斷隊列是否為空
判斷隊列是否為空有兩種方式：1.判斷pq->size等不等于 0；2.判斷頭指針pq->head和尾指針pq->tail是否等于空指針NULL
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
//return pq->head == NULL && pq->tail == NULL;
}
隊列中數(shù)據(jù)的個數(shù)
直接返回隊列數(shù)據(jù)的個數(shù)pq->size
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
Test.c
以下為測試函數(shù)接口的代碼，大家可以參考一下。需要注意的是，打印隊列中的數(shù)據(jù)是通過打印隊頭數(shù)據(jù)、Pop掉隊頭數(shù)據(jù)的方式來實現(xiàn)的。
#include "Queue.h"
void QueueTest()
{
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);
QueuePush(&q, 6);
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
printf("\n");
QueueDestroy(&q);
}
int main()
{
QueueTest();
return 0;
}
以上就是C語言數(shù)據(jù)結(jié)構(gòu)與算法之隊列的實現(xiàn)詳解的詳細內(nèi)容，更多關(guān)于C語言數(shù)據(jù)結(jié)構(gòu) 隊列的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C++實現(xiàn)拷貝構(gòu)造函數(shù)的方法詳解
拷貝構(gòu)造函數(shù)是構(gòu)造函數(shù)的一個重載，因此顯式的定義了拷貝構(gòu)造，那么編譯器也不再默認生成構(gòu)造函數(shù)。本文主要介紹了C++實現(xiàn)拷貝構(gòu)造函數(shù)的方法，需要的可以參考一下2022-09-09
OpenCV實現(xiàn)彩色照片轉(zhuǎn)換成素描卡通片
這篇文章主要為大家詳細介紹了OpenCV實現(xiàn)彩色照片轉(zhuǎn)換成素描卡通片，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-01-01
這篇文章主要介紹了詳解C++中的數(shù)據(jù)抽象,數(shù)據(jù)抽象是指，只向外界提供關(guān)鍵信息，并隱藏其后臺的實現(xiàn)細節(jié)，即只表現(xiàn)必要的信息而不呈現(xiàn)細節(jié),需要的朋友可以參考下2023-05-05
這篇文章主要為大家詳細介紹了 C/C++中的static關(guān)鍵字，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
單元測試（unit testing），是指對軟件中的最小可測試單元進行檢查和驗證。這篇文章主要為大家介紹了C語言實現(xiàn)單元測試的方法，需要的可以參考一下2022-09-09
利用C語言實現(xiàn)http服務(wù)器(Linux)
本文將利用C語言實現(xiàn)一個輕量級的http服務(wù)器，使用Reactor模式，即主線程只負責監(jiān)聽文件描述符上是否有事件發(fā)生，有的話立即將該事件通知工作線程，感興趣的可以了解一下2022-07-07
這篇文章主要介紹了C++中模板(Template)實現(xiàn)元素的反序，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-06-06
這篇文章主要介紹了C經(jīng)典算法之二分查找法的相關(guān)資料,這里提供兩種方法幫助大家實現(xiàn)這樣的功能，需要的朋友可以參考下2017-10-10
大家好，本篇文章主要講的是C語言數(shù)學公式來實現(xiàn)土味表白，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2021-12-12
C++實現(xiàn)學生信息管理系統(tǒng)(完整版)
這篇文章主要為大家詳細介紹了C++實現(xiàn)學生信息管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06