C语言详解链式队列与循环队列的实现-C/C++开发

队列（Queue）与栈一样，是一种线性存储结构，它具有如下特点：队列中的数据元素遵循“先进先出”（FirstInFirstOut）的原则，简称FIFO结构。在队尾添加元素，在队头删除元素，本篇来讲解链式队列与循环队列的实现

队列的实现

队列是一种先进先出（First in First Out）的线性表，简称FIFO。与栈不同，栈是一种后进先出（先进后出）的线性表。在队列中，允许插入的一端称为队尾，允许删除的一端称为队头。假设队列是q=（a1,a2,…,an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，列在最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然在队伍的最后。队列分为顺序队列和循环队列。顺序队列我们可以利用数组或者链表实现。这里，我们选择用链表实现顺序队列。

IiBzcmM9

今天主要介绍链表实现的队列和循环队列

链式队列

队列主要有哪些基本操作

// 初始化队列 
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;
    /

目录

队列的实现

链式队列

链式队列的定义

链式队列的实现