C語言鏈式隊列與循環隊列怎么實現

這篇文章主要介紹了C語言鏈式隊列與循環隊列怎么實現的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇C語言鏈式隊列與循環隊列怎么實現文章都會有所收獲，下面我們一起來看看吧。

隊列的實現

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

今天主要介紹鏈表實現的隊列和循環隊列

鏈式隊列

隊列主要有哪些基本操作

// 初始化隊列 
void QueueInit(Queue* q);

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

鏈式隊列的定義

typedef int QDataType;
// 鏈式結構：表示隊列 
typedef struct QListNode
{
    struct QListNode* _next;
    QDataType _data;
}QNode;

// 隊列的結構 
typedef struct Queue
{
    QNode* _front;
    QNode* _rear;
}Queue;

鏈式隊列的實現

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、隊中有效元素個數

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

循環隊列

循環隊列的定義

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

循環隊列的空間可以重復利用，解決了普通隊列的空間浪費問題

循環隊列的實現

typedef struct {
    int *a;
    int front;
    int tail;
    int k;
} MyCircularQueue;

//提前聲明判空判滿
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
//創建循環隊列
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;
}
//循環隊列入隊
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;
}
//循環隊列出隊
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;
    }
    int i=(obj->tail+obj->k)%(obj->k+1);
    return obj->a[i];
}
//循環隊列判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->tail;
}
//循環隊列判滿
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1)%(obj->k+1)==obj->front;
}
//銷毀循環隊列
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

關于“C語言鏈式隊列與循環隊列怎么實現”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“C語言鏈式隊列與循環隊列怎么實現”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。