【数据结构】【线性表】之队列(C语言)

队列的概念

队列只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的FIFO(First in First Out)。

入队列：进行插入操作的一端称为队尾。

出队列：进行删除操作的一端称为队头。

同样可以使用链表或者数组

数组：不是适合，队头出数据需要挪动数据。

链表：适合单链表，单链表头删效率很高。

结构定义

typedef int QueueDataType;
typedef struct QueueNode
{
    struct QueueNode* next;
    QueueDataType data;
}QueueNode;
//单链表除了尾插还要尾删，所以不会加这个
typedef struct Queue
{
    QueueNode* tail;
    QueueNode* head;
}Queue;

初始化

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

销毁

void QueueDestory(Queue* pq)
{
    assert(pq);
    //定义一个新结点
    QueueNode* cur = pq->head;
    while (cur)
    {
        //依次保存下一个结点，然后删除这个结点
        QueueNode* curNext = cur->next;
        free(cur);
        cur = curNext;
    }
    pq->head = pq->tail = NULL;
}

队尾入

void QueuePush(Queue* pq, QueueDataType x)
{
    assert(pq);
    //创建新结点
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    //创建失败
    if (newnode == NULL)
    {
        printf("malloc is fail\n");
        exit(-1);
    }
    //链接
    newnode->data = x;
    newnode->next = NULL;
    //如果插入前是空的
    if (pq->tail == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
          //插到后面
        pq->tail->next = newnode;
          //称为新的尾巴
        pq->tail = newnode;
    }
}

队头出

void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->head);//队列是不等于空的
    if (pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
        //先保存下一个结点
        QueueNode* nextNode = pq->head->next;
        free(pq->head);
        pq->head = nextNode;
    }
}

队头出

QueueDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(pq->head);
    return pq->head->data;
}

队头数据

QueueDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(pq->head);
    return pq->head->data;
}

队尾数据

QueueDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(pq->head);
    return pq->tail->data;
}

是否为空

bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->head == NULL;
}

返回数据个数

int QueueSize(Queue* pq)
{
    assert(pq);
    int size = 0;
    QueueNode* cur = pq->head;
    while (cur)
    {
        size++;
        cur = cur->next;
    }
    return size;
}

全部代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
//结构定义
typedef int QueueDataType;
typedef struct QueueNode
{
    struct QueueNode* next;
    QueueDataType data;
}QueueNode;
//单链表除了尾插还要尾删，所以不会加这个
typedef struct Queue
{
    QueueNode* tail;
    QueueNode* head;
}Queue;
//初始化
void QueueInit(Queue* pq)
{
    assert(pq);
    pq->tail = pq->head = NULL;
}
//销毁
void QueueDestory(Queue* pq)
{
    assert(pq);
    QueueNode* cur = pq->head;
    while (cur)
    {
        QueueNode* curNext = cur->next;
        free(cur);
        cur = curNext;
    }
    pq->head = pq->tail = NULL;
}
//队尾入
void QueuePush(Queue* pq, QueueDataType x)
{
    assert(pq);
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newnode == NULL)
    {
        printf("malloc is fail\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;

    if (pq->tail == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
}
//队头出
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->head);//队列是不等于空的
    if (pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
        //先保存一下下一个结点
        QueueNode* nextNode = pq->head->next;
        free(pq->head);
        pq->head = nextNode;
    }
}
//队头数据
QueueDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(pq->head);
    return pq->head->data;
}
//队尾数据
QueueDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(pq->head);
    return pq->tail->data;
}
//是否为空
bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->head == NULL;
}
//返回数据个数
int QueueSize(Queue* pq)
{
    assert(pq);
    int size = 0;
    QueueNode* cur = pq->head;
    while (cur)
    {
        size++;
        cur = cur->next;
    }
    return size;
}
void Test1()
{
    Queue pq;
    QueueInit(&pq);
    QueuePush(&pq, 1);
    QueuePush(&pq, 2);
    QueuePush(&pq, 3);
    QueuePush(&pq, 4);
    //为空是假的才成立，进入循环(不为空，进入循环)
    while (!QueueEmpty(&pq))
    {
        //取队头的数据然后删除
        printf("%d ", QueueFront(&pq));
        QueuePop(&pq);
    }
    QueueDestory(&pq);
}
int main(void)
{
    Test1();
    return 0;
}