【数据结构】（C语言）：队列

news/2024/7/7 5:53:39 标签: 数据结构, c语言

队列：

  • 线性的集合。
  • 先进先出（FIFO，first in first out）。
  • 两个指针：头指针（指向第一个进入且第一个出去的元素），尾指针（指向最后一个进入且最后一个出去的元素）。
  • 两个操作：入队（往队尾添加元素），出队（从队头删除元素）。
  • 队列有优先队列，双端队列，循环队列等。
  • 可以使用链表实现，也可以使用数组实现。本文使用数组实现循环队列。

添加元素：

往队尾添加。若尾指针已指向队尾，则循环重新指向队头。

删除元素：

从队头删除。若头指针已指向队尾，则循环重新指向队头。

扩容、缩容：

若内存区域已全部使用完，则增加内存区域。若内存区域使用小，则减少内存区域。

方法：新开辟内存区域，将原数据复制到新内存区域。

若头指针在尾指针的前面，则从头指针到尾指针的数据依次复制到新内存区域。

若尾指针在头指针的前面，则从头指针到内存区域最后的这m个数据，依次复制到新区域0到m-1，再从0到尾指针的数据，依次复制到n到n-1（n为实际存储数据个数）。

 ​​​​​​

C语言实现：（使用数组实现循环队列）

创建结构体数据类型：

  • 指针p：记录数组的内存地址（即数组第一个元素的地址）。
  • 整型length：记录数组最大物理容量（即创建数组时指定的内存大小）。
  • 整型n：记录数组实际逻辑大小（即数组实际已经存储的数据个数）。
  • 指针front：头指针，始终指向数组数据中第一个进入且将第一个出去的元素。
  • 指针rear：尾指针，始终指向数组数据中最后一个进入且将最后一个出去的元素。
typedef struct Queue
{
	int *p;		    // 数组内存地址
	int length;	    // 物理最大容量
	int n;		    // 实际存储数据
	int *front;	    // 始终指向第一个进入且第一个出去的元素
	int *rear;	    // 始终指向最后一个进入且最后一个出去的元素
} Queue;	        // 别名

创建队列变量：

Queue queue;

初始化队列：

void init(Queue *queue, int len)
{
	queue->p = (int *)malloc(len * sizeof(int));     // 分配数组内存空间
	if(queue->p == NULL)
	{
		perror("Memory allocation failled");
		exit(-1);
	}
	queue->length = len;            // 指定物理大小
	queue->n = 0;                   // 实际存储数据个数,初始化为0
	queue->front = queue->p;        // 头指针,初始化指向数组第一个元素地址
	queue->rear = queue->p;         // 尾指针,初始化指向数组第一个元素地址
}

扩容、缩容：

void resize(Queue *queue, int len)
{
    // 开辟新内存空间，将原数据复制到新地址
	int *t = (int *)malloc(len * sizeof(int));
	int *tmp = queue->front;

    // 若头指针在前，依次复制从头指针到尾指针的数据
	if(queue->front < queue->rear)
	{
		for(int k = 0; k < queue->n; k++)
		{
			t[k] = *tmp;
			tmp++;
		} 
	}
    // 若尾指针在前，复制头指针到数组最后的数据，再复制数组开头到尾指针的数据
	else if(queue->front > queue->rear)
	{
		int i;
		int m = queue->p + queue->n - queue->front;
		for(i = 0; i < m; i++)
		{
			t[i] = *tmp;
			tmp++;
		}
		for(; i < queue->n; i++)
		{
			t[i] = queue->p[i - m];
		}
	}
	queue->p = t;
	queue->length = len;
	queue->front = queue->p;
	queue->rear = queue->p + queue->n - 1;
}

 添加元素：

往队尾添加。尾指针rear指向下一个元素。若尾指针已指向区域最后，则尾指针循环重新指向区域开头。

void add(Queue *queue, int data)
{
	if(queue->length == queue->n)	// 若数组满，扩容
	{
		int newlength = queue->length * 2;
		resize(queue, newlength);
	}
	
	// 若尾指针指向数组最后，尾指针循环开始指向数组开头
	if(queue->rear == queue->p + queue->n) queue->rear = queue->p;
	else queue->rear++;

	*queue->rear = data;
	queue->n++;
}

删除元素：

从队头删除。头指针front指向下一个元素。若头指针已指向区域最后，则头指针循环重新指向区域开头。

int deltop(Queue *queue)
{
	int value = *queue->rear;
	queue->n--;

	// 若头指针已指向数组尾部，头指针循环开始指向数组开头
	if(queue->front == queue->p + queue->n)	queue->front = queue->p;
	else queue->front++;

	if(queue->n < ceil(queue->length / 2) && queue->length > 4)	// 满足条件，缩容
	{
		int newlength = ceil(queue->length / 2);
		resize(queue, newlength);
	}
	return value;
}

遍历队列元素：

void travel(Queue *queue)
{
	if(queue->n == 0) return ;

	printf("elements: ");
	int *tmp = queue->front;
    
    // 若头指针在前，依次从头指针遍历到尾指针
	if(queue->front < queue->rear)
	{
		for(int k = 0; k < queue->n; k++)
		{
			printf("%d  ", *tmp);
			tmp++;
		} 
	}
    // 若尾指针在前，遍历头指针到数组最后，再遍历数组开头到尾指针
	else if(queue->front > queue->rear)
	{
		int i;
		int m = queue->p + queue->n - queue->front;
		for(i = 0; i < m; i++)
		{
			printf("%d  ", *tmp);
			tmp++;
		}
		for(; i < queue->n; i++)
		{
			printf("%d  ", queue->p[i - m]);
		}
	}
	printf("\n");
}

完整代码：（queue.c）

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

/* structure */
typedef struct Queue
{
	int *p;		// memory address of the queue
	int length;	// maximum number of the queue
	int n;		// actual number of the queue
	int *front;	// point to the first element
	int *rear;	// point to the end element
} Queue;

/* function prototype */
void init(Queue *, int);	// queue initialization
void resize(Queue *, int);	// increase or reduce the size of the queue
void add(Queue *, int);         // add element to the end of the queue
int deltop(Queue *);		// delete element from the start of the queue
void travel(Queue *);		// show element one by one

/* main function */
int main(void)
{
	Queue queue;
	init(&queue, 4);
	printf("length is %d, actual is %d\n", queue.length, queue.n);
	
	add(&queue, 8);
	add(&queue, 16);
	add(&queue, 23);
	printf("length is %d, actual is %d\n", queue.length, queue.n);
	travel(&queue);
	add(&queue, 65);
	printf("length is %d, actual is %d\n", queue.length, queue.n);
	travel(&queue);
	add(&queue, 27);     // 已满，扩容
	printf("length is %d, actual is %d\n", queue.length, queue.n);
	travel(&queue);

	deltop(&queue);
	printf("length is %d, actual is %d\n", queue.length, queue.n);
	travel(&queue);
	deltop(&queue);      // 使用少于一半，缩容
	printf("length is %d, actual is %d\n", queue.length, queue.n);
	travel(&queue);
	deltop(&queue);
	deltop(&queue);
	deltop(&queue);
	printf("length is %d, actual is %d\n", queue.length, queue.n);
	return 0;
}

/* subfunction */
void init(Queue *queue, int len)		// queue initialization
{
	queue->p = (int *)malloc(len * sizeof(int));
	if(queue->p == NULL)
	{
		perror("Memory allocation failled");
		exit(-1);
	}
	queue->length = len;
	queue->n = 0;
	queue->front = queue->p;
	queue->rear = queue->p;
}

void resize(Queue *queue, int len)	// increase or reduce the size of the queue
{
	int *t = (int *)malloc(len * sizeof(int));	// new memory space
	int *tmp = queue->front;			// copy datas to new memroy space
	if(queue->front < queue->rear)
	{ // copy elements from front pointer to rear pointer
		for(int k = 0; k < queue->n; k++)
		{
			t[k] = *tmp;
			tmp++;
		} 
	}
	else if(queue->front > queue->rear)
	{
		int i;
		int m = queue->p + queue->n - queue->front;
		for(i = 0; i < m; i++)
		{ // copy elements from front pointer to the end of the queue
			t[i] = *tmp;
			tmp++;
		}
		for(; i < queue->n; i++)
		{ // copy elements from start of the queue to the rear pointer
			t[i] = queue->p[i - m];
		}
	}
	queue->p = t;
	queue->length = len;
	queue->front = queue->p;
	queue->rear = queue->p + queue->n - 1;
}

void add(Queue *queue, int data)        // add element to the end of the queue
{
	if(queue->length == queue->n)	// increase the size of the queue
	{
		int newlength = queue->length * 2;
		resize(queue, newlength);
	}
	
	// if rear point to the end space, rear point to index 0
	if(queue->rear == queue->p + queue->n) queue->rear = queue->p;
	else queue->rear++;

	*queue->rear = data;
	queue->n++;
}

int deltop(Queue *queue)		// delete element from the start of the queue
{
	int value = *queue->rear;
	queue->n--;

	// if front point to the end space,front point to index 0
	if(queue->front == queue->p + queue->n)	queue->front = queue->p;
	else queue->front++;

	if(queue->n < ceil(queue->length / 2) && queue->length > 4)	// reduce the size of the queue
	{
		int newlength = ceil(queue->length / 2);
		resize(queue, newlength);
	}
	return value;
}


void travel(Queue *queue)		// show element one by one
{
	if(queue->n == 0) return ;

	printf("elements: ");
	int *tmp = queue->front;
	if(queue->front < queue->rear)
	{ // copy elements from front pointer to rear pointer
		for(int k = 0; k < queue->n; k++)
		{
			printf("%d  ", *tmp);
			tmp++;
		} 
	}
	else if(queue->front > queue->rear)
	{
		int i;
		int m = queue->p + queue->n - queue->front;
		for(i = 0; i < m; i++)
		{ // copy elements from front pointer to the end of the queue
			printf("%d  ", *tmp);
			tmp++;
		}
		for(; i < queue->n; i++)
		{ // copy elements from start of the queue to the rear pointer
			printf("%d  ", queue->p[i - m]);
		}
	}
	printf("\n");
}

编译链接： gcc -o queue queue.c

执行可执行文件： ./queue


http://www.niftyadmin.cn/n/5534952.html

相关文章

基于深度学习的动画渲染

基于深度学习的动画渲染

基于深度学习的动画渲染是一项利用深度学习技术来提高动画制作效率和质量的前沿研究领域。该技术旨在通过深度学习模型加速动画渲染过程&#xff0c;优化图像质量&#xff0c;并实现复杂效果的自动化生成。以下是关于这一领域的系统介绍&#xff1a; 1. 任务和目标 动画渲染的…
阅读更多...
webpack 之 splitChunks分包策略

webpack 之 splitChunks分包策略

webpack 之 splitChunks分包策略 一、为什么需要拆包二、拆包方式三、splitChunks介绍四、splitChunks 拆包策略五、总结 一、为什么需要拆包 随着应用程序规模的增长&#xff0c;JavaScript 文件的大小也越来越大。一个大的 JavaScript 文件会导致页面加载时间过长&#xff0…
阅读更多...
Java 开发环境配置

Java 开发环境配置

配置Java开发环境涉及几个关键步骤&#xff0c;包括安装Java Development Kit (JDK)、配置环境变量和选择集成开发环境&#xff08;IDE&#xff09;。以下是详细的步骤和示例说明&#xff1a; ### 1. 安装 Java Development Kit (JDK) Java JDK 是开发Java应用程序的基本工具…
阅读更多...
Vue 循环内部获取图片高度

Vue 循环内部获取图片高度

在vue循环里面获取图片宽度或者高度,有时候会用到,则可以 <div classconmon v-for"(item, index) in items"><router-link :to"{path: /art/details,query:{artid:item.app_id,item_id:item.image_id}}"><img :src"item.src" al…
阅读更多...
prometheus 安装node_exporter， node_exporter 安装最新版 普罗米修思安装监控服务器client

prometheus 安装node_exporter， node_exporter 安装最新版 普罗米修思安装监控服务器client

1. 本文介绍两种安装方式&#xff0c;一种安装为service,使用systemctl start node_exporter管理&#xff0c;第二种为安装docker内 容器内使用。 1.1 安装到系统内&#xff1a; 1.1.1 github地址&#xff1a; Releases prometheus/node_exporter GitHub ​ 1.1.2 下载命…
阅读更多...
深度学习中，模型的构建和训练过程中会用到多种函数

深度学习中，模型的构建和训练过程中会用到多种函数

在深度学习中&#xff0c;模型的构建和训练过程中会用到多种函数&#xff0c;这些函数在数据处理、模型定义、损失计算、激活以及优化等方面发挥着重要作用。以下是一些常见的深度学习模型中用到的函数&#xff1a; 1. 激活函数 Sigmoid函数&#xff1a;Sigmoid函数是一种非线…
阅读更多...
嵌入式面试需要注意的问题！

嵌入式面试需要注意的问题！

1.在嵌入式和IT行业&#xff0c;技术更新换代非常快。因此&#xff0c;求职者必须时刻关注行业的最新动向和发展趋势。了解当前市场上哪些技术和岗位需求量大&#xff0c;哪些新兴技术值得学习和掌握&#xff0c;都是至关重要的。 &#x1f538;嵌入式行业&#xff1a;嵌入式系…
阅读更多...
【SQL】已解决：SQL分组去重并合并相同数据

【SQL】已解决：SQL分组去重并合并相同数据

文章目录 一、分析问题背景二、可能出错的原因三、错误代码示例四、正确代码示例五、注意事项 已解决&#xff1a;SQL分组去重并合并相同数据 在数据库操作中&#xff0c;数据的分组、去重以及合并是常见需求。然而&#xff0c;初学者在编写SQL语句时&#xff0c;可能会遇到一…
阅读更多...
最新文章

Copyright @ 2022~2023