【数据结构】顺序队列与链式队列

1.队列的基本概念

队列是一种逻辑结构，是一种特殊的线性表

• 只能在固定的两端操作线性表

只要满足上述条件，那么这种特殊的线性表就会呈现一种“先进先出”的逻辑，这种逻辑就被称为队列。

由于约定了只能在线性表固定的两端进行操作，于是给队列这种特殊的线性表的插入删除，起个特殊的名称：

• 队头：可以删除节点的一端
• 队尾：可以插入节点的一端
• 入队：将节点插入到队尾之后，函数名通常为enQueue()
• 出队：将队头节点从队列中剔除，函数名通常为outQueue()
• 取队头：取得队头元素，但不出队，函数名通常为front()

1.顺序存储的队列：循环队列

#include <stdio.h>
#include <stdlib.h>

#define QUEUE_SIZE 10

typedef struct sq_queue
{
    int data[QUEUE_SIZE];
    int tail;
}sq_queue_t;

// 
sq_queue_t *sq_queue_init(void)
{
    sq_queue_t *my_sq_queue = malloc(sizeof(sq_queue_t));
    
    (my_sq_queue->tail) = -1;
    return my_sq_queue;
}

// 入队
int en_queue(int new_data, sq_queue_t *sq_queue)
{
    // 判断队列是否满了
    if (sq_queue->tail > QUEUE_SIZE - 1)
    {
        printf("队列已满!\n");
        return -1;
    }
    
    (sq_queue->tail)++;
    sq_queue->data[sq_queue->tail] = new_data;
    return 0;
}

// 出队
int out_queue(sq_queue_t *sq_queue)
{
    int i;
    if (sq_queue->tail < 0)
    {
        printf("队列已空!\n");
        return -1;
    }
    int temp = sq_queue->data[0];
    for (i = 0; i < sq_queue->tail; i++)
    { 
        sq_queue->data[i] = sq_queue->data[i+1];
    }
    (sq_queue->tail)--;
    return temp;
}

int main(int argc, char const *argv[])
{
    int i;
    sq_queue_t *my_sq_queue = sq_queue_init();
    if (!my_sq_queue)
    {
        printf("[main] init fail\n");
        return -1;
    }

    for (i = 0; i < 12; i++)
    {
        en_queue(i, my_sq_queue);
    }

    for (i = 0; i < 12; i++)
    {
        printf("出队数据：%d\n", out_queue(my_sq_queue));
    }
    
    return 0;
}

3.链式存储的队列：链式队列

#include <stdio.h>
#include <stdlib.h>

typedef struct list_queue
{
    int data;
    struct list_queue *tail;
    struct list_queue *next;
}list_queue_t;

// 初始化链式队列， 定义结构体变量
list_queue_t *list_queue_init(void)
{
    list_queue_t *queue_head = malloc(sizeof(list_queue_t));
    queue_head->next = NULL;
    queue_head->tail = queue_head; // 对尾指针指向头节点,每次插入新的节点需要更新队尾指针

    return queue_head;
}

// 入队--尾插
int in_queue(int new_data, list_queue_t *queue)
{
    list_queue_t *new_node = malloc(sizeof(list_queue_t));
    // 初始化数据域
    new_node->data = new_data;
    new_node->next = NULL;
    new_node->tail = NULL;
    // 把新的节点插入到队尾后面
    queue->tail->next = new_node; 
    // 更新队尾---指向新的节点
    queue->tail = new_node;

    return 0;
}

// 出队--把头节点的下一个节点删除，返回该节点的数据
int out_queue(list_queue_t *queue)
{
    // 判断队列是否为空
    if (!queue->next)
    {
        printf("队列已空!\n");
        return -1;
    }
    
    // 定义指针p指向待删除的节点--也就是头节点的下一个节点
    list_queue_t *p = queue->next;
    // 备份待删除节点的数据
    int temp = p->data;
    // 将头节点的next指针指向待删除节点的下一个节点--删除队首
    queue->next = p->next;

    p->next = NULL;
    free(p);

    return temp;
}

#define IN_QUEUE_NUM 5
int main(int argc, char const *argv[])
{
    unsigned char i;
    list_queue_t *head_queue = list_queue_init();
    for (i = 0; i < IN_QUEUE_NUM; i++)
    {
        in_queue(i, head_queue);
    }
    
    for (i = 0; i < IN_QUEUE_NUM + 1; i++)
    {
        printf("出队的数据：%d\n", out_queue(head_queue));
    }
    

    return 0;
}

/*
执行结果：
    出队的数据：0
    出队的数据：1
    出队的数据：2
    出队的数据：3
    出队的数据：4
    队列已空!
    出队的数据：-1

*/