快捷導(dǎo)航

C語言詳解鏈式隊列與循環(huán)隊列的實現(xiàn)

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

隊列（Queue）與棧一樣，是一種線性存儲結(jié)構(gòu)，它具有如下特點：隊列中的數(shù)據(jù)元素遵循“先進先出”（First In First Out）的原則，簡稱FIFO結(jié)構(gòu)。在隊尾添加元素，在隊頭刪除元素，本篇來講解鏈式隊列與循環(huán)隊列的實現(xiàn)

隊列的實現(xiàn)

隊列是一種先進先出（First in First Out）的線性表，簡稱FIFO。與棧不同，棧是一種后進先出（先進后出）的線性表。在隊列中，允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。假設(shè)隊列是q=（a1,a2,…,an），那么a1就是隊頭元素，而an是隊尾元素。這樣我們就可以刪除時，總是從a1開始，而插入時，列在最后。這也比較符合我們通常生活中的習(xí)慣，排在第一個的優(yōu)先出列，最后來的當然在隊伍的最后。隊列分為順序隊列和循環(huán)隊列。順序隊列我們可以利用數(shù)組或者鏈表實現(xiàn)。這里，我們選擇用鏈表實現(xiàn)順序隊列。

今天主要介紹鏈表實現(xiàn)的隊列和循環(huán)隊列

鏈式隊列

隊列主要有哪些基本操作

// 初始化隊列 
void QueueInit(Queue* q);
?
// 隊尾入隊列 
void QueuePush(Queue* q, QDataType data);
// 隊頭出隊列 
void QueuePop(Queue* q);
// 獲取隊列頭部元素 
QDataType QueueFront(Queue* q);
// 獲取隊列隊尾元素 
QDataType QueueBack(Queue* q);
// 獲取隊列中有效元素個數(shù) 
int QueueSize(Queue* q);
// 檢測隊列是否為空，如果為空返回非零結(jié)果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 銷毀隊列 
void QueueDestroy(Queue* q);

鏈式隊列的定義

typedef int QDataType;
// 鏈式結(jié)構(gòu)：表示隊列 
typedef struct QListNode
{
    struct QListNode* _next;
    QDataType _data;
}QNode;
?
// 隊列的結(jié)構(gòu) 
typedef struct Queue
{
    QNode* _front;
    QNode* _rear;
}Queue;

鏈式隊列的實現(xiàn)

1、初始化隊列

void QueueInit(Queue* q)
{
    assert(q);
    q->_front = NULL;
    q->_rear = NULL;
}

2、銷毀隊列

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、隊列判空

bool QueueEmpty(Queue* q)
{
    assert(q);
    //if (q->_front == NULL)
    //{
    //  return 1;
    //}
    //else
    //{
    //  return 0;
    //}
    return q->_front == NULL;
}

4、入隊操作

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、出隊操作

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、取隊頭元素

QDataType QueueFront(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->_front->_data;
}

7、取隊尾操作

QDataType QueueBack(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->_rear->_data;
}

8、隊中有效元素個數(shù)

int QueueSize(Queue* q)
{
    assert(q);
    int size = 0;
    QNode* cur = q->_front;
    while (cur) 
    {
        size++;
        cur = cur->_next;
    }
    return size;
}

循環(huán)隊列

循環(huán)隊列的定義

循環(huán)隊列就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。在循環(huán)隊列結(jié)構(gòu)中，當存儲空間的最后一個位置已被使用而再要進入隊運算時，只需要存儲空間的第一個位置空閑，便可將元素加入到第一個位置，即將存儲空間的第一個位置作為隊尾。循環(huán)隊列可以更簡單防止偽溢出的發(fā)生，但隊列大小是固定的。在循環(huán)隊列中，當隊列為空時，有front=rear，而當所有隊列空間全占滿時，也有front=rear。為了區(qū)別這兩種情況，規(guī)定循環(huán)隊列最多只能有MaxSize-1個隊列元素，當循環(huán)隊列中只剩下一個空存儲單元時，隊列就已經(jīng)滿了。因此，隊列判空的條件是front=rear，而隊列判滿的條件是front=（rear+1)%MaxSize。

循環(huán)隊列的空間可以重復(fù)利用，解決了普通隊列的空間浪費問題

循環(huán)隊列的實現(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)隊列
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)隊列入隊
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)隊列出隊
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return false;
    }
    obj->front++;
    obj->front%=(obj->k+1);
    return true;
?
}
//循環(huán)隊列取隊頭
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return -1;
    }
    return obj->a[obj->front];
}
//循環(huán)隊列取隊尾
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return -1;
    }
    int i=(obj->tail+obj->k)%(obj->k+1);
    return obj->a[i];
}
//循環(huán)隊列判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->tail;
}
//循環(huán)隊列判滿
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1)%(obj->k+1)==obj->front;
}
//銷毀循環(huán)隊列
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

到此這篇關(guān)于C語言詳解鏈式隊列與循環(huán)隊列的實現(xiàn)的文章就介紹到這了,更多相關(guān)C語言隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: