@[TOC]

前言

数组队列，链式队列都可以，只是因为效率，链表队列更好

队列结构体定义

//队列队尾入，队头出
//队列这里使用链表形式。
//方便操作

typedef int QDateType;

typedef struct node
{
    QDateType x;
    struct node* next;
}Queuenode;//定义队列结点

typedef struct 
{
    Queuenode* head;
    Queuenode* tail;
}Queue;//队列需要从队头出，队尾入，而链表一般只需要头指针，因此将队头，队尾指针存在结构体中。
       //方便且不需要考虑二级指针问题

队列的初始化

void QueueInit(Queue* q)//初始化
{
    assert(q);
    q->head = NULL;
    q->tail = NULL;
}

创建结点

Queuenode* newnode(QDateType x)//创建结点。因为某些需要开辟结点，因此将这步独立出来
{

    Queuenode* q = (Queuenode*)malloc(sizeof(Queuenode));
    if(q==NULL)
    {
    perror("q");
    exit(-1);
    }
    q->x = x;
    q->next = NULL;
    return q;
}

队列判空

bool  QueueEmpty(Queue* q)//因为返回值问题，在判断队列是否为空，只需要与NULL比较.
{
    assert(q);
    
    return q->head == NULL;
}

入队列

void QueuePush(Queue* q, QDateType x)//入队列
{
    assert(q);
    if (QueueEmpty(q))
    {
        Queuenode* node = newnode(x);
        q->head = node;
        q->tail = node;
    }
    else
    {
        Queuenode* node = newnode(x);
        q->tail->next = node;
        q->tail = node;
    }
    
}

出队列

void QueuePop(Queue* q)//出队列
{
    assert(q);
    assert (!QueueEmpty(q));//空队列。
    Queuenode* next = q->head->next;
    free(q->head);
    q->head = next;
    if (q->head == NULL)
    {
        q->tail = NULL;
    }
}

取队头元素

QDateType  QueueTop(Queue* q)
{

    assert(q);
    assert(!QueueEmpty(q));
    return q->head->x;
}

队列大小

size_t  QueueSize(Queue* q)//获取队列中的元素个数
{
    assert(q);
    size_t cnt = 0;
    Queuenode *cur = q->head;
    while (cur!=NULL)
    {
        ++cnt;
        cur = cur->next;

    }
    return cnt;
}

队列打印

void QueuePrint(Queue* q)//打印
{
    assert(q);
    Queuenode* tur= q->head;
    while (tur!=NULL)
    {
        printf("%d->", tur->x);
        tur = tur->next;
    }
    printf("NULL\n");
}

队列销毁

void QueueDestroy(Queue* q)//销毁
{
    assert(q);
    Queuenode* cur = q->head;
    while (cur!=NULL)
    {
        Queuenode* tmp = cur->next;
        free(cur);
        cur = tmp;
    }
    q->head = NULL;
    q->tail = NULL;
}