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

1.队列的基本概念

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

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

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

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

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

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

#include <stdio.h>
#include <stdlib.h>#define QUEUE_SIZE 10typedef 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*/