当前位置： 首页 > article >正文

数据结构--队列(C语言实现)

article 2025/3/4 7:57:03

文章目录

  • 一、简介
  • 二、顺序结构的队列
  • 三、顺序结构循环队列
  • 四、链式结构的队列
  • 五、总结

一、简介

队列（Queue）是一种常见的数据结构，遵循“先进先出”（FIFO, First In First Out）的原则。队列的应用非常广泛，例如任务调度、缓冲区管理、广度优先搜索等。

队列通常支持以下几种基本操作：

  • 入队（enqueue）：将元素添加到队列的末尾。
  • 出队（dequeue）：移除队列的第一个元素，并返回它。
  • 查看队首元素（getHead）：返回队列的第一个元素，但不移除它。
  • 判断队列是否为空（IsEmpty）：检查队列是否为空。
  • 判断队列是否满了（IsFull）：对于固定大小的队列。
  • 获取队列大小（getSize）：返回队列中元素的数量。

二、顺序结构的队列

顺序结构的队列，在C语言中可以借助数组 加队头、队尾指针 来实现。假设队列为 q = (a1, a2, …, an)，那么，a1 就是队头元素，an 就是队尾元素。队列中的元素是按照 a1, a2, …, an 的顺序进入的，退出队列也只能按照这个次序依次退出，也就是说，只有在 a1, a2, …, an-1 都离开队列之后，an 才能退出队列。
在这里插入图片描述
顺序结构队列的C语言结构：

typedef struct 
{
	ElemType *data;
	int front;  //队头指针（记录队头位置）
	int rear;   //队尾指针（记录队尾位置）
}Queue;
  • (1) 初始化队列（动态分配）
Queue* initQueue(void)
{
	Queue *q = (Queue*)malloc(sizeof(Queue));
    if(NULL == q)
    {
        perror("malloc Error: ");
        return NULL;
    }
	q->data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
    if(NULL == q->data)
    {
        free(q);
        q = NULL;
        perror("malloc Error: ");
        return NULL;
    }
    /* 队头、队尾指针初始值为0 */
	q->front = 0; 
	q->rear  = 0; 
	return q;
}
  • (2) 销毁队列
void destoryQueue(Queue *Q)
{
    if(Q)
    {
        if(Q->data)
        {
            free(Q->data);
            Q->data = NULL;
        }
        free(Q);
        Q = NULL;
    }
}
  • (3)判断是否空
bool isEmpty(Queue *Q)
{
    /* 队头指针和队尾指针相等，说明是空队列 */
	if(Q->front == Q->rear)
	{
		return 1;
	}
	else
	{
		return 0;	
	}
}
  • (4)判断是否满
bool isFull(Queue *Q)
{
    /* rear到了数组末尾元素位置，且front在数组首元素位置，则队列是真的满了 */
    if(Q->rear >= MAXSIZE)
    {
    	if(Q->front > 0)
    	{
            /* 移动队列到数组首元素位置 */
    		int step = Q->front;
    		for (int i = Q->front; i <= Q->rear; ++i)
    		{
    			Q->data[i - step] = Q->data[i];
    		}
    		Q->front = 0;
    		Q->rear = Q->rear - step;
    		return false;
    	}
    	else
    	{
    		return true;
    	}
    }
    else
    {
        return false;
    }
}
  • (5)入队
int equeue(Queue *Q, ElemType elem)
{

	if(isFull(Q))
	{
        printf("queue is full\n");
        return -1;
    }
    
    /* 先插入元素，再移动队尾指针 */
	Q->data[Q->rear] = elem;
	Q->rear++;
	return 0;
}
  • (6)出队
ElemType dequeue(Queue *Q, ElemType *elem)
{
	if(isEmpty(Q))
	{
        printf("queue is empty\n");
        return -1;
    }
    /* 先取出元素，再移动队头指针 */
	*elem = Q->data[Q->front];
	Q->front++;
	return 0;
}
  • (7)获取队头元素
int getHead(Queue *Q, ElemType *elem)
{
	if(isEmpty(Q))
	{
        printf("queue is empty\n");
        return -1;
    }
	*elem = Q->data[Q->front];
	return 0;
}
  • (8)获取大小
int getSize(Queue *Q)
{
	return (Q->rear - Q->front);
}
  • (9)完整代码
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//顺序结构队列
#define MAXSIZE 3
typedef int ElemType;

typedef struct 
{
	ElemType *data;
	int front;  //队头指针（记录队头位置）
	int rear;   //队尾指针（记录队尾位置）
	
}Queue;

/*****************************************************************
* 函数功能      : 初始化队列
* 参数        : void
* 返回值       : 成功：Queue* 指针，失败：NULL
******************************************************************/
Queue* initQueue(void)
{
	Queue *q = (Queue*)malloc(sizeof(Queue));
    if(NULL == q)
    {
        perror("malloc Error: ");
        return NULL;
    }
	q->data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
    if(NULL == q->data)
    {
        free(q);
        q = NULL;
        perror("malloc Error: ");
        return NULL;
    }
    /* 队头、队尾指针初始值为0 */
	q->front = 0; 
	q->rear  = 0; 
	return q;
}
/*****************************************************************
* 函数功能      : 销毁
* 参数        : Q(in):队列
* 返回值       : void
******************************************************************/
void destoryQueue(Queue *Q)
{
    if(Q)
    {
        if(Q->data)
        {
            free(Q->data);
            Q->data = NULL;
        }
        free(Q);
        Q = NULL;
    }
}

/*****************************************************************
* 函数功能      : 判断队列是否为空
* 参数        : Q(in):队列
* 返回值       : 空：true, 非空：false
******************************************************************/
bool isEmpty(Queue *Q)
{
    /* 队头指针和队尾指针相等，说明是空队列 */
	if(Q->front == Q->rear)
	{
		return 1;
	}
	else
	{
		return 0;	
	}
}
/*****************************************************************
* 函数功能      : 判断队列是否满
* 参数        : Q(in):队列
* 返回值       : 满：true, 没满：false
******************************************************************/
bool isFull(Queue *Q)
{
    /* rear到了数组末尾元素位置，且front在数组首元素位置，则队列是真的满了 */
    if(Q->rear >= MAXSIZE)
    {
    	if(Q->front > 0)
    	{
            /* 移动队列到数组首元素位置 */
    		int step = Q->front;
    		for (int i = Q->front; i <= Q->rear; ++i)
    		{
    			Q->data[i - step] = Q->data[i];
    		}
    		Q->front = 0;
    		Q->rear = Q->rear - step;
    		return false;
    	}
    	else
    	{
    		return true;
    	}
    }
    else
    {
        return false;
    }
}
/*****************************************************************
* 函数功能      : 入队
* 参数        : Q(in):队列
* 返回值       : 成功：0，失败：-1
******************************************************************/
int equeue(Queue *Q, ElemType elem)
{

	if(isFull(Q))
	{
        printf("queue is full\n");
        return -1;
    }
    
    /* 先插入元素，再移动队尾指针 */
	Q->data[Q->rear] = elem;
	Q->rear++;
	return 0;
}

/*****************************************************************
* 函数功能      : 出队
* 参数        : Q(in):队列
* 参数        : elem(out):出队元素值
* 返回值       : 成功：0，失败：-1
******************************************************************/
ElemType dequeue(Queue *Q, ElemType *elem)
{
	if(isEmpty(Q))
	{
        printf("queue is empty\n");
        return -1;
    }
    /* 先取出元素，再移动队头指针 */
	*elem = Q->data[Q->front];
	Q->front++;
	return 0;
}

/*****************************************************************
* 函数功能      : 获取队头元素
* 参数        : Q(in):队列
* 参数        : elem(out):队头元素值
* 返回值       : 成功：0，失败：-1
******************************************************************/
int getHead(Queue *Q, ElemType *elem)
{
	if(isEmpty(Q))
	{
        printf("queue is empty\n");
        return -1;
    }
	*elem = Q->data[Q->front];
	return 0;
}
/*****************************************************************
* 函数功能      : 获取队列大小
* 参数        : Q(in):队列
* 返回值       : 队列大小
******************************************************************/
int getSize(Queue *Q)
{
	return (Q->rear - Q->front);
}


//测试
int main(int argc, char const *argv[])
{
	//初始化队列
	Queue *queue = initQueue();
    printf("queue size:%d\n",getSize(queue)); 

    //入队
	equeue(queue, 10);
	equeue(queue, 20);
	equeue(queue, 30);
    equeue(queue, 40);   //已经满了
    printf("queue size:%d\n",getSize(queue)); 

    //出队
	ElemType elem;
    dequeue(queue, &elem);
	printf("dequeue: %d\n",elem);
    dequeue(queue, &elem);
	printf("dequeue: %d\n",elem);
    dequeue(queue, &elem);
	printf("dequeue: %d\n",elem);
    
    dequeue(queue, &elem); //已经空了
    printf("queue size:%d\n",getSize(queue)); 

    equeue(queue, 10);
    //获取队头
	getHead(queue, &elem);
    printf("queue head:%d\n", elem); 
    
	//销毁
    destoryQueue(queue);
	return 0;
}

三、顺序结构循环队列

顺序结构循环队列的相比于非循环队列的好处在于，判断队列是否满时，不用移动队列。
在这里插入图片描述

  • (1) 初始化队列（动态分配）
Queue* initQueue()
{
	Queue *q = (Queue*)malloc(sizeof(Queue));
    if(NULL == q)
    {
        perror("malloc Error: ");
        return NULL;
    }
	q->data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
    if(NULL == q->data)
    {
        perror("malloc Error: ");
        free(q);
        q = NULL;
        return NULL;
    }
	q->front = 0;
	q->rear  = 0;
	return q;
}
  • (2) 销毁队列
void destoryQueue(Queue *Q)
{
    if(Q)
    {
        if(Q->data)
        {
            free(Q->data);
            Q->data = NULL;
        }
        free(Q);
        Q = NULL;
    }
}
  • (3)判断是否空
bool isEmpty(Queue *Q)
{
	if (Q->front == Q->rear)
	{
		return true;
	}
	else
	{
		return false;	
	}
}
  • (4)判断是否满
bool isFull(Queue *Q)
{
    /* 按照队尾指针指向队尾元素的下一个元素方式，这个判满公式会有一个空闲 */
	if ((Q->rear + 1) % MAXSIZE == Q->front)
	{
		return true;
	}
	return false;
}
  • (5)入队
int equeue(Queue *Q, ElemType elem)
{
	if(isFull(Q))
	{
        printf("queue is full\n");
		return -1;
	}
	Q->data[Q->rear] = elem;
	Q->rear = (Q->rear + 1) % MAXSIZE;
	return 0;
}
  • (6)出队
int dequeue(Queue *Q, ElemType *elem)
{
	if(isEmpty(Q))
	{
		printf("queue is empty\n");
		return -1;
	}
	*elem = Q->data[Q->front];
	Q->front = (Q->front + 1) % MAXSIZE;
	return 0;
}
  • (7)获取队头元素
int getHead(Queue *Q, ElemType *elem)
{
	if(isEmpty(Q))
	{
		printf("queue is empty\n");
		return -1;
	}
	*elem = Q->data[Q->front];
	return 0;
}
  • (8)获取大小
int getSize(Queue *Q)
{
    if(Q->rear < Q->front)
    {
	    return (Q->rear + MAXSIZE - Q->front);
    }
    else
    {
	    return (Q->rear - Q->front);
    }
}
  • (9)完整代码
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//顺序结构循环队列
#define MAXSIZE 4
typedef int ElemType;

typedef struct 
{
	ElemType *data;
	int front;
	int rear;
	
}Queue;

/*****************************************************************
* 函数功能      : 初始化队列
* 参数        : void
* 返回值       : 成功：Queue* 指针，失败：NULL
******************************************************************/
Queue* initQueue()
{
	Queue *q = (Queue*)malloc(sizeof(Queue));
    if(NULL == q)
    {
        perror("malloc Error: ");
        return NULL;
    }
	q->data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
    if(NULL == q->data)
    {
        perror("malloc Error: ");
        free(q);
        q = NULL;
        return NULL;
    }
	q->front = 0;
	q->rear  = 0;
	return q;
}
/*****************************************************************
* 函数功能      : 销毁
* 参数        : Q(in):队列
* 返回值       : void
******************************************************************/
void destoryQueue(Queue *Q)
{
    if(Q)
    {
        if(Q->data)
        {
            free(Q->data);
            Q->data = NULL;
        }
        free(Q);
        Q = NULL;
    }
}

/*****************************************************************
* 函数功能      : 判断队列是否为空
* 参数        : Q(in):队列
* 返回值       : 空：true, 非空：false
******************************************************************/
bool isEmpty(Queue *Q)
{
	if (Q->front == Q->rear)
	{
		return true;
	}
	else
	{
		return false;	
	}
}
/*****************************************************************
* 函数功能      : 判断队列是否满了
* 参数        : Q(in):队列
* 返回值       : 满：true, 没满：false
******************************************************************/
bool isFull(Queue *Q)
{
    /* 按照队尾指针指向队尾元素的下一个元素方式，这个判满公式会有一个空闲 */
	if ((Q->rear + 1) % MAXSIZE == Q->front)
	{
		return true;
	}
	return false;
}
/*****************************************************************
* 函数功能      : 入队
* 参数        : Q(in):队列
* 参数        : elem(in):入队元素
* 返回值       : 成功：0，失败：-1
******************************************************************/
int equeue(Queue *Q, ElemType elem)
{
	if(isFull(Q))
	{
        printf("queue is full\n");
		return -1;
	}
	Q->data[Q->rear] = elem;
	Q->rear = (Q->rear + 1) % MAXSIZE;
	return 0;
}
/*****************************************************************
* 函数功能      : 出队
* 参数        : Q(in):队列
* 参数        : elem(out):出队元素
* 返回值       : 成功：0，失败：-1
******************************************************************/
int dequeue(Queue *Q, ElemType *elem)
{
	if(isEmpty(Q))
	{
		printf("queue is empty\n");
		return -1;
	}
	*elem = Q->data[Q->front];
	Q->front = (Q->front + 1) % MAXSIZE;
	return 0;
}
/*****************************************************************
* 函数功能      : 获取队头元素
* 参数        : Q(in):队列
* 参数        : elem(out):队列头元素
* 返回值       : 成功：0，失败：-1
******************************************************************/
int getHead(Queue *Q, ElemType *elem)
{
	if(isEmpty(Q))
	{
		printf("queue is empty\n");
		return -1;
	}
	*elem = Q->data[Q->front];
	return 0;
}
/*****************************************************************
* 函数功能      : 获取队列大小
* 参数        : Q(in):队列
* 返回值       : 队列大小
******************************************************************/
int getSize(Queue *Q)
{
    if(Q->rear < Q->front)
    {
	    return (Q->rear + MAXSIZE - Q->front);
    }
    else
    {
	    return (Q->rear - Q->front);
    }
}

//测试
int main(int argc, char const *argv[])
{
	//初始化队列
	Queue *queue = initQueue();
    printf("queue size:%d\n",getSize(queue)); 

    //入队
	equeue(queue, 10);
	equeue(queue, 20);
	equeue(queue, 30);
    equeue(queue, 40);   //已经满了
    printf("queue size:%d\n",getSize(queue)); 

    //出队
	ElemType elem;
    dequeue(queue, &elem);
	printf("dequeue: %d\n",elem);
    dequeue(queue, &elem);
	printf("dequeue: %d\n",elem);
    dequeue(queue, &elem);
	printf("dequeue: %d\n",elem);
    
    dequeue(queue, &elem); //已经空了
    printf("queue size:%d\n",getSize(queue)); 

    equeue(queue, 10);
    //获取队头
	getHead(queue, &elem);
    printf("queue head:%d\n", elem); 

    //销毁
    destoryQueue(queue);
	return 0;
}

四、链式结构的队列

链式结构的队列，和链表相似，不同的是：队列是先进先出。所以，用链表头端作为队头，链表尾端作为队尾，入队就是链表的尾插法，出队就是删除头节点指向的节点。

C语言栈结构实现：

typedef struct QueueNode
{
	ElemType data;
	struct QueueNode *next;
}QueueNode;

typedef struct 
{
	QueueNode *front;  //队头
	QueueNode *rear;   //队尾
}Queue;
  • (1) 初始化队列
Queue* initQueue()
{
	Queue *q = (Queue*)malloc(sizeof(Queue));
    if(NULL == q)
    {
        perror("malloc Error: ");
        return NULL;
    }
    /* 头节点 */
	QueueNode *node = (QueueNode*)malloc(sizeof(QueueNode));
    if(NULL == node)
    {
        perror("malloc Error: ");
        free(q);
        q = NULL;
        return NULL;
    }
	node->data = 0;
	node->next = NULL;
    /* 队头、队尾都等于头节点 */
	q->front   = node; 
	q->rear    = node; 
	return q;
}
  • (2)判断是否空
bool isEmpty(Queue *Q)
{
     /* 队头等于队尾，说明是空队列 */
	if (Q->front == Q->rear)
	{
		return true;
	}
	else
	{
		return false;
	}
}
  • (3)入队
int equeue(Queue *Q, ElemType elem)
{
	QueueNode *node = (QueueNode*)malloc(sizeof(QueueNode));
    if(NULL == node)
    {
        perror("malloc Error: ");
        return -1;
    }
    //尾插法
	node->data = elem;
	node->next = NULL;
	Q->rear->next = node; 
	Q->rear = node; //移动队尾指针
}
  • (4)出队
int dequeue(Queue *Q, ElemType *elem)
{
	if(isEmpty(Q))
	{
		printf("queue is empty\n");
		return -1;
	}

    /* 删除头节点指向的节点 */
	QueueNode *node = Q->front->next;
	*elem = node->data;
	Q->front->next = node->next;
	if (Q->rear == node) //如果是队尾，删完就就是空队列
	{
		Q->rear = Q->front;
	}
	free(node);
	return 0;
}
  • (5)获取队头元素
int getHead(Queue *Q, ElemType *elem)
{
	if(isEmpty(Q))
	{
		printf("queue is empty\n");
		return -1;
	}
	*elem = Q->front->next->data;
    return 0;
}
  • (6)完整代码
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>


//链表结构队列
typedef int ElemType;

typedef struct QueueNode
{
	ElemType data;
	struct QueueNode *next;
}QueueNode;

typedef struct 
{
	QueueNode *front;  //队头
	QueueNode *rear;   //队尾
}Queue;

/*****************************************************************
* 函数功能      : 初始化队列
* 参数        : void
* 返回值       : 成功：Queue* 指针，失败：NULL
******************************************************************/
Queue* initQueue()
{
	Queue *q = (Queue*)malloc(sizeof(Queue));
    if(NULL == q)
    {
        perror("malloc Error: ");
        return NULL;
    }
    /* 头节点 */
	QueueNode *node = (QueueNode*)malloc(sizeof(QueueNode));
    if(NULL == node)
    {
        perror("malloc Error: ");
        free(q);
        q = NULL;
        return NULL;
    }
	node->data = 0;
	node->next = NULL;
    /* 队头、队尾都等于头节点 */
	q->front   = node; 
	q->rear    = node; 
	return q;
}

/*****************************************************************
* 函数功能      : 判断队列是否为空
* 参数        : Q(in):队列
* 返回值       : 空：true, 非空：false
******************************************************************/
bool isEmpty(Queue *Q)
{
     /* 队头等于队尾，说明是空队列 */
	if (Q->front == Q->rear)
	{
		return true;
	}
	else
	{
		return false;
	}
}

/*****************************************************************
* 函数功能      : 入队
* 参数        : Q(in):队列
* 参数        : elem(in):入队元素
* 返回值       : 成功：0，失败：-1
******************************************************************/
int equeue(Queue *Q, ElemType elem)
{
	QueueNode *node = (QueueNode*)malloc(sizeof(QueueNode));
    if(NULL == node)
    {
        perror("malloc Error: ");
        return -1;
    }
    //尾插法
	node->data = elem;
	node->next = NULL;
	Q->rear->next = node; 
	Q->rear = node; //移动队尾指针
}

/*****************************************************************
* 函数功能      : 出队
* 参数        : Q(in):队列
* 参数        : elem(out):出队元素
* 返回值       : 成功：0，失败：-1
******************************************************************/
int dequeue(Queue *Q, ElemType *elem)
{
	if(isEmpty(Q))
	{
		printf("queue is empty\n");
		return -1;
	}

    /* 删除头节点指向的节点 */
	QueueNode *node = Q->front->next;
	*elem = node->data;
	Q->front->next = node->next;
	if (Q->rear == node) //如果是队尾，删完就就是空队列
	{
		Q->rear = Q->front;
	}
	free(node);
	return 0;
}

/*****************************************************************
* 函数功能      : 获取队头元素
* 参数        : Q(in):队列
* 参数        : elem(out):队列头元素
* 返回值       : 成功：0，失败：-1
******************************************************************/
int getHead(Queue *Q, ElemType *elem)
{
	if(isEmpty(Q))
	{
		printf("queue is empty\n");
		return -1;
	}
	*elem = Q->front->next->data;
    return 0;
}


int main(int argc, char const *argv[])
{
	//初始化队列
	Queue *queue = initQueue();

    //入队
	equeue(queue, 10);
	equeue(queue, 20);
	equeue(queue, 30);

    //出队
	ElemType elem;
    dequeue(queue, &elem);
	printf("dequeue: %d\n",elem);
    dequeue(queue, &elem);
	printf("dequeue: %d\n",elem);
    dequeue(queue, &elem);
	printf("dequeue: %d\n",elem);
    dequeue(queue, &elem); //已经空了
    

    equeue(queue, 10);
    //获取队头
	getHead(queue, &elem);
    printf("queue head:%d\n", elem); 
	return 0;
}

五、总结

队列是一种非常有用的数据结构，它在许多算法和程序设计中都有广泛的应用。


http://www.kler.cn/a/569861.html

相关文章：

  • 一个非常好用便捷的web自动化爬虫工具Playwright
  • 大数据分析中的机器学习基础：从原理到实践
  • Dwall 动态壁纸自动匹配
  • 蓝桥杯深秋的苹果
  • 数据图表ScottPlot.WPF用法示例
  • HTTP 协议的发展历程：从 HTTP/1.0 到 HTTP/2.0
  • 【Linux】TCP协议
  • VScode C语言学习开发环境；运行提示“#Include错误，无法打开源文件stdio.h”
  • 计算机毕设-基于springboot的社团管理系统的设计与实现（附源码+lw+ppt+开题报告）
  • 小红的回文子串
  • 企业微信获取用户信息
  • MySQL增删改查(进阶)
  • 时序论文41 | Medformer：基于多粒度patch的时序分类模型
  • [含文档+PPT+源码等]精品基于Python实现的微信小程序的在线医疗咨询系统
  • 汽车智能钥匙低频PKE天线
  • 基于C#的CANoe CLR Adapter开发指南
  • 达梦数据库如何收集表和索引的统计信息
  • C# 使用 Newtonsoft.Json 序列化和反序列化对象实例
  • 线上JVM OOM问题，如何排查和解决？
  • Linux运维——软件管理