一、队列的原理
队列和栈相似，相同点是都属于线性结构，不同点是栈的原理是“后进先出”，队列的原理是“先进先出”，队列也被称为”FIFO”。
数据结构中的队列是两端都允许操作，只不过要求数据只能从一端入队(enqueue)，从另一端出队(dequeue)，一般把入队的一端称为队尾(tail/rear)，把出队的一端称为队头/队首(head/front)。
队列也属于线性结构，所以根据数据元素之间的物理关系来划分，同样可以数组或链表为基础来实现队列的操作
1.以数组实现循环队列
如果以数组为基础，一般会把队列设置成循环队列，循环队列也被称为“环形缓冲区”，因为如果队列中的元素出队，则需要把该元素的后继元素整体向前移动，这时时间复杂度为O(n)。
如果数据出队之后不去移动后继元素又会导致数组的空间被浪费，为了解决该问题，可以把队列设置为循环队列，在移动数据的时候只需要移动一次即可，所以时间复杂度就是O(1)
sequencequeue.h
/**
* @file : sequencequeue
* @brief : 使用数组实现循环队列
* @author : TingFengLuo@126.com
* @date : 2026-1-3
* @version : V1.0
* @note :使用循环链表时，要少一个空间，便于分清队首和堆尾
*/
#ifndef __SEQUENCEQUEUE_H_
#define __SEQUENCEQUEUE_H_
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
//将int重命名为DataType_t,便于用户后续对类型进行修改
typedef int DataType_t;
//使用数组创建循环队列类型
typedef struct Circular_Sequence_Queue{
//数组容量
int size;
//数组首地址
DataType_t *addr;
//队首下标
int front;
//队尾下标
int rear;
}CirSeqQueue_t;
//创建循环队列并对其元素初始化
CirSeqQueue_t *CirSeqQueue_Create(DataType_t capacity);
//判断循环队列是否满队
bool CirSeqQueue_IsFull(CirSeqQueue_t *queue);
//入队
bool CirSeqQueue_EnQueue(CirSeqQueue_t *queue,DataType_t data);
//判空
bool CirSeqQueue_IsEmpty(CirSeqQueue_t *queue);
//出队
bool CirSeqQueue_DeQueue(CirSeqQueue_t *queue,DataType_t *data);
#endif
sequencequeue.c
#include "sequencequeue.h"
/**
* @name : CirSeqQueue_Create
* @brief : 创建循环队列，并对循环队列初始化
* @param
@size :创建循环队列的元素个数
* @return : 返回循环队列的地址
* @version : V1.0
* @note : NULL
*/
CirSeqQueue_t *CirSeqQueue_Create(DataType_t capacity)
{
//创建变量为循环队列类型申请内存
CirSeqQueue_t *queue = (CirSeqQueue_t *)calloc(1,sizeof(CirSeqQueue_t));
//判断队列内存是否申请成功
if(NULL == queue){
perror("Circular Sequenue Queue create memory failed for queue");
exit(1);
}
//创建变量存储数组容量,addr指向数组首地址
queue->addr = (DataType_t *)calloc(capacity+1,sizeof(DataType_t));
//判断数组是否创建成功
if(NULL == queue->addr){
perror("Circualr Sequence Queue create memory failed for arr");
free(queue);
exit(1);
}
queue->size = capacity+1;
queue->front = 0;
queue->rear = 0;
return queue;
}
/**
* @name : CirSeqQueue_IsFull
* @brief : 判断循环队列是否为满
* @param
@queue : 表示需要操作的循环队列
* @return : 如果循环队列满则返回true，否则返回false
* @version : V1.0
* @note : NULL
*/
bool CirSeqQueue_IsFull(CirSeqQueue_t *queue)
{
return ((queue->rear + 1 ) % queue->size == queue->front) ? true : false;
}
/**
* @name : CirSeqQueue_EnQueue
* @brief : 入队
* @param
@queue : 表示需要操作的循环队列
@data : 表示入队的数据
* @return : 入队成功返回true，否则返回false
* @version : V1.0
* @note : 在入队时，并不是无限插入，所以需要用队尾下标+1，然后和数组元素个数求余
*/
bool CirSeqQueue_EnQueue(CirSeqQueue_t *queue,DataType_t data)
{
//判断循环队列是否存在
if(NULL == queue){
printf("Circular Sequence queue create queue failed\n");
return false;
}
//判断循环队列是否满队
if(CirSeqQueue_IsFull(queue)){
printf("Circular Sequence queue is full\n");
return false;
}
//给数组赋值
queue->addr[queue->rear] = data;
//防止越界
queue->rear = (queue->rear + 1)%queue->size;
return true;
}
/**
* @name : CirSeqQueue_EnQueue
* @brief : 判断循环队列是否为空
* @param
@queue : 表示需要操作的循环队列
* @return : 如果为空返回true，否则返回false
* @version : V1.0
* @note : 判断循环队列是否为空时，只需要判断队首和堆尾下标是否相同就可
*/
bool CirSeqQueue_IsEmpty(CirSeqQueue_t *queue)
{
return queue->rear == queue->front ? true : false;
}
/**
* @name : CirSeqQueue_DeQueue
* @brief : 出队
* @param
@queue : 表示需要操作的循环队列
@data : 表示需要出队的数据
* @return : 如果出队成功返回true,否则返回false
* @version : V1.0
* @note : 出队时要防止出多了，所以要使用队头+1然后对素组元素求余
*/
bool CirSeqQueue_DeQueue(CirSeqQueue_t *queue,DataType_t *data)
{
//判断循环队列是否存在
if(NULL == queue){
printf("Circular Sequence queue create queue failed\n");
return false;
}
//判断循环队列是否为空
if(CirSeqQueue_IsEmpty(queue)){
printf("Circular Sequence queue is Empty\n");
return false;
}
//返回队头的值
*data = queue->addr[queue->front];
//数组中下一个元素的值
queue->front = (queue->front+1) % queue->size;
return true;
}
main.c
#include "sequencequeue.h"
int main(int argc,const char *argv[]){
//创建变量存储循环变量地址
CirSeqQueue_t *queue = CirSeqQueue_Create(20);
CirSeqQueue_EnQueue(queue,10);
CirSeqQueue_EnQueue(queue,20);
CirSeqQueue_EnQueue(queue,30);
CirSeqQueue_EnQueue(queue,40);
CirSeqQueue_EnQueue(queue,50);
CirSeqQueue_EnQueue(queue,60);
CirSeqQueue_EnQueue(queue,70);
int data;
printf("current queue value: ");
while(!CirSeqQueue_IsEmpty(queue)){
CirSeqQueue_DeQueue(queue,&data);
printf("%d ",data);
}
printf("\n");
return 0;
}
代码测试：
二、以链表尾基础实现链式队列
如果打算以链表作为基础实现队列的操作，可以避免内存浪费以及避免内存成片移动，只需要确定队头和队尾即可，一般把链表头部作为队头，可以实现头删，把链表尾部作为队尾，可以实现尾插。
linkedlistqueue.h
/**
* @file : linkedlistqueue
* @brief : 使用链表创建队列，实现链式队列的入队和出队
* @author : TingFengLuo@126.com
* @date : 2026-1-5
* @version : V1.0
* @note : 该链式队列有一个哨兵用来管理，一个节点包含数据域和指针域，有一个头指针和尾指针，便于出队和入队
**/
#ifndef __LINKEDLISTQUEUE_H_
#define __LINKEDLISTQUEUE_H_
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
//将int重命名为Datatype_t,后续便于用于对数据类型进行修改
typedef int DataType_t;
//定义队列的节点结构体
typedef struct node{
//数据域
DataType_t data;
//指针域
struct node *next;
}node_t;
//定义队列管理结构体
typedef struct linkedlistqueue{
//队头指针
node_t *front;
//队尾指针
node_t *rear;
}LLQueue_t;
//创建队列并初始化
LLQueue_t *LLQueue_Create(void);
//判断队列是否为空
bool LLQueue_IsEmpty(LLQueue_t *llqueue);
//创建新节点
node_t *LLQueue_NewNode(DataType_t data);
//入队
bool LLQueue_EnQueue(LLQueue_t *queue,DataType_t data);
//出队
bool LLQueue_DeQueue(LLQueue_t *queue,DataType_t *data);
#endif
linkedlistqueue.c
#include "linkedlistqueue.h"
/**
* @name : LLQueue_Create
* @brief : 创建链式队列，该链式队列包含头节点并对链表初始化
* @param : NULL
* @return : 返回链式队列的地址
* @version : V1.0
* @note : 要对头节点申请内存，也要对队列本身分配内存，让队列的头元素和尾元素指向头节点
*/
LLQueue_t *LLQueue_Create(void)
{
//为队列结构体本身分配内存
LLQueue_t *llqueue = (LLQueue_t *)calloc(1,sizeof(LLQueue_t));
//判断队列是否创建成功
if(NULL == llqueue){
perror("Linked list queue create memory failed for llqueue");
exit(1);
}
//创建变量用于存储哨兵节点
node_t *head = (node_t *)calloc(1,sizeof(node_t));
//判断哨兵节点是否创建成功
if(NULL == head){
perror("Linked list queue create memory failed for head");
free(llqueue);
exit(1);
}
// 初始化哨兵节点
head->next = NULL;
//初始化队列的 front 和 rear 指针，都指向哨兵节点
llqueue->front = head;
llqueue->rear = head;
return llqueue;
}
/**
* @name : LLQueue_IsEmpty
* @brief : 判断队列是否为空
* @param
@llqueue :要操作的队列
* @return : 如果为空返回true，否则返回false
* @version : V1.0
* @note : 判断是否为空只需要判断头节点和尾节点是否相同
*/
bool LLQueue_IsEmpty(LLQueue_t *llqueue)
{
return (llqueue->front->next == NULL) ? true : false;
}
/**
* @name : LLQueue_NewNode
* @brief : 创建新节点，为后续入队左操作
* @param
@data :要入队的数据
* @return : 返回新节点地址
* @version : V1.0
* @note : NULL
*/
node_t *LLQueue_NewNode(DataType_t data)
{
//创建变量存储新节点地址
node_t *new_node = (node_t *)calloc(1,sizeof(node_t));
//判断新节点是否创建成功
if(NULL == new_node){
printf("create new node failed\n");
return NULL;
}
new_node->data = data;
new_node->next = NULL;
return new_node;
}
/**
* @name : LLQueue_EnQueue
* @brief : 入队
* @param
@queue :要操作的队列
@data :要入队的数据
* @return : 入队成功返回true否则返回false
* @version : V1.0
* @note : NULL
*/
bool LLQueue_EnQueue(LLQueue_t *queue,DataType_t data)
{
//判断队列是否存在
if(NULL == queue){
printf("create memory failed for queue\n");
return false;
}
//创建变量存储新节点地址
node_t *new_node = LLQueue_NewNode(data);
if(NULL == new_node){
printf("create new_node failed\n");
return false;
}
//判断队列是否为空,如果为空，直接插入新节点
if(queue->front->next == NULL){
queue->rear->next = new_node;
queue->rear = queue->rear->next;
return true;
}
queue->rear->next = new_node;
queue->rear = queue->rear->next;
return true;
}
/**
* @name : LLQueue_DeQueue
* @brief : 出队
* @param
@queue :要操作的队列
@data :返回出队的数据
* @return : 出队成功返回true否则返回false
* @version : V1.0
* @note : NULL
*/
bool LLQueue_DeQueue(LLQueue_t *queue,DataType_t *data)
{
//判断链式队列是否存在
if(NULL == queue){
printf("create queue failed\n");
return false;
}
//判断队列是否为空
if(queue->front->next == NULL){
printf("queue is empty\n");
return false;
}
//创建变量用于存储要出队的节点
node_t *pnode = queue->front->next;
//将头节点的下一个指针指向出队的下一个节点
queue->front->next = pnode->next;
//如果是最后一个节点
if(pnode == queue->rear){
queue->front->next = NULL;
queue->rear = queue->front;
}
*data = pnode->data;
free(pnode);
pnode = NULL;
return true;
}
main.c
#include "linkedlistqueue.h"
int main(int argc,const char *argv[]){
LLQueue_t * queue = LLQueue_Create();
if(NULL == queue){
printf("create queue failed!!!\n");
return -1;
}
//创建变量用于存储返回的数据
DataType_t data;
LLQueue_EnQueue(queue,10);
LLQueue_EnQueue(queue,20);
LLQueue_EnQueue(queue,30);
LLQueue_EnQueue(queue,40);
LLQueue_EnQueue(queue,50);
LLQueue_EnQueue(queue,60);
LLQueue_EnQueue(queue,70);
printf("Dequeue value : ");
while(!LLQueue_IsEmpty(queue)){
LLQueue_DeQueue(queue,&data);
printf("%d ",data);
}
printf("\n");
free(queue);
queue = NULL;
return 0;
}
代码测试：
发表回复