快捷導(dǎo)航

C語(yǔ)言詳解鏈?zhǔn)疥?duì)列與循環(huán)隊(duì)列的實(shí)現(xiàn)

更新時(shí)間：2022年04月15日 15:53:21 作者：m0_52012656

隊(duì)列（Queue）與棧一樣，是一種線性存儲(chǔ)結(jié)構(gòu)，它具有如下特點(diǎn)：隊(duì)列中的數(shù)據(jù)元素遵循“先進(jìn)先出”（First In First Out）的原則，簡(jiǎn)稱FIFO結(jié)構(gòu)。在隊(duì)尾添加元素，在隊(duì)頭刪除元素，本篇來(lái)講解鏈?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開(kāi)始，而插入時(shí)，列在最后。這也比較符合我們通常生活中的習(xí)慣，排在第一個(gè)的優(yōu)先出列，最后來(lái)的當(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)問(wèn)題

循環(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)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: