[数据结构与算法]数据结构-队列

数据结构-队列

生活中会有这样的场景，当我们去一个地方排队买东西的时候，总是先排队的先买，后排队的后买；去银行中办理业务的时候，先到达银行的人现办理业务，后到达银行的人后办理业务。

其实这和数据结构中的队列类似。

初识队列

队列也是一种操作受限制的线性表。

特点

1. 队列中的数据先进后出，或者说是后进先出。
2. 数据进队列的时候是从队列尾(队尾)进，数据出队列的时候是从队列头(队头)出。

同样的：队列也可以用数组和链表来实现。

可以看到的是，如果队列中没有节点，要不对头是指向NULL，要不就是一直指向头节点，在只进行尾插的情况下，头节点的指向是不变的；变的一直是尾节点的指向。

实现队列

这里使用链表来模拟实现队列。

设计节点和队列

• 节点中应该包含的东西：

1. 需要储存的数据。
2. 指向下一个节点的结构体指针next。

typedef int QueueDataType;

typedef struct QueueNode
{
    QueueDataType data;
    struct QueueNode* next;
}QNode;

• 队列中应该包含的东西

1. 指向队头的指针。
2. 指向队尾的指针。
3. 队列中数据的个数。

typedef struct Queue
{
    QNode* head;
    QNode* tail;
    int size;
}Queue;

队列的基本功能

队列的基本功能无非就是插入数据和删除数据，这里用尾插和头删来表示。

当然，还有队列的初始化以及销毁。

队列的初始化和销毁

队列的初始化

创建一个队列，因为head tail指针无具体指向，如果直接拿来用的话，势必会出现野指针问题。

void QueueInit(Queue* pq)
{
    assert(pq);
    
    pq->head = pq->tail = NULL;
    pq->size = 0;
}

队列的销毁

每个节点都是在堆区用动态函数开辟的，如果在程序结束的时候不进行内存空间的释放，将会引发内存泄漏。

这里的销毁方法就是从队尾往队头依次释放节点。

void QueueDestroy(Queue* pq)
{
    assert(pq);
    
    Queue* cur = pq->head;
    while (cur)
    {
        Queue* del = cur;
        cur = cur->next;
        free(del);
    }
    
    pq->head = pq->tail = NULL;
}

尾插和头删

• 尾插

在队尾插入一个节点，节点中保存着对应的数据，如果队列中没有节点的话，则该尾插节点的next节点指向空；要是队列中有节点的话，则尾插节点的next指向原本队列中的最后一个节点。同时，调整好tail指针的指向。

void EnQueue(Queue* pq, QueueDataType x)
{
    assert(pq);
    
    // 创建一个节点
    QNode* newNode = (QNode*)malloc(sizeof(QNode));
    if (newNode == NULL)
    {
        perror("Malloc Fail");
        return;
    }
    
    newNode->data = x;
    // 默认节点指向NULL
    newNode->next = NULL;
    
    
    // 队列中没有节点
    if (pq->size == 0)
    {
        pq->head = pq->tail = newNode;
    }
    // 队列中有节点
    else
    {
        // 1.将新节点和队列中的最后一个节点链接起来
        pq->tail->next = newNode;
        
        // 2. 更新tail指针
        pq->tail = newNode;
    }
    
    
    pq->size++;
}

头删

头删的话，分为3种情况：

1. 队列种没有节点：直接提示一下队列种没有节点。
2. 队列中只有一个节点，删除之后，head 和 tail指针最终都要置为空。
3. 队列中有多个节点，删除头节点之后，只有head的指向需要改变。

需要知道的是，删除本质上还是将节点释放掉。

void DeQueue(Queue* pq)
{
    assert(pq);
    
    if (pq->size == 0)
    {
        printf("Queue empty, delete fail.\n");
        return;
    }
    else if (pq->size == 1)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else 
    {
        QNode* del = pq->head;
        pq->head = del->next;
        
        free(del);
        del = NULL;
    }
    
    pq->size--;
}

返回队头和队尾的数据

返回数据就比较简单了，队头的数据就是head指向的节点中的数据，队尾的数据就是tail指向的节点中的数据。

当然，不要忘了判断一下队列中是否有节点。

返回队头数据

QueueDataType QueueFront(Queue* pq)
{
    assert(pq);
    
    if (pq->size == 0)
    {
        printf("Queue empty, there is no data in it.");
        exit(-1);
    }
    else
    {
        return pq->head->data;
    }
}

返回队尾数据

QueueDataType QueueBack(Queue* pq)
{
    assert(pq);
    
    if (pq->size == 0)
    {
        printf("Queue empty, there is no data in it.");
        exit(-1);
    }
    else
    {
        return pq->tail->data;
    }
}