您的位置: 首页  >  文章  >  数据结构（C语言）队列

数据结构（C语言）队列

分类: 文章 • 2025-02-04 12:45:40

（郝斌老师视频课）

简介：

35 _ 队列1 _ 什么是队列
36 _ 队列2 _ 队列的分类和链式队列伪算法的讲解
37 _ 队列3 _ 学习循环队列必须要弄清楚的7个问题概述
38 _ 队列4 _ 静态队列为什么必须是循环队列
39 _ 队列5 _ 循环队列需要几个参数来确定及其含义的讲解
40 _ 队列6 _ 循环队列各个参数的含义
41 _ 队列7 _ 循环队列入队伪算法讲解
42 _ 队列8 _ 循环队列出队伪算法讲解
43 _ 队列9 _ 如何判断循环队列是否为空
44 _ 队列10 _ 如何判断循环队列是否已满
45 _ 复习 _ 求链表的长度【没写】
46 _ 复习上节课队列知识
47 _ 循环队列程序演示
48 _ 队列的具体应用

35 _ 队列1 _ 什么是队列

线性结构的两种常见应用之二队列
定义：
一种可以实现“先进先出”的存储结构

36 _ 队列2 _ 队列的分类和链式队列伪算法的讲解

数据结构（C语言）队列
出队：f加1，入队：r加1
队列最需要注意的是：如果有五个元素，0 1 2 3 4 位置上都有元素，f 指向的是0，r 指向的5，是有元素的下一个位置！！！
分类：
链式队列：用链表实现
静态队列：用数组实现

37 _ 队列3 _ 学习循环队列必须要弄清楚的7个问题概述

静态队列
静态队列通常都必须是循环队列
循环队列的讲解：
1）静态队列为什么必须是循环队列
2）循环队列需要几个参数来确定
3）循环队列各个参数的含义
4）循环队列入队伪算法讲解
5）循环队列出队伪算法讲解
6）如何判断循环队列是否为空
7）如何判断循环队列是否已满

38 _ 队列4 _ 静态队列为什么必须是循环队列

数据结构（C语言）队列
如果要删除元素（出队），f只能加；如果要增加元素（入队），r只能加。（按照一般数组的方法）。r指向当前队列的下一个位置。
数据结构（C语言）队列

39 _ 队列5 _ 循环队列需要几个参数来确定及其含义的讲解

需要2个参数来确定
front
rear
两个参数不同场合有不同的含义
建议初学者先记住，然后慢慢体会
1）队列初始化
front和rear的值都是零
2）队列非空
front代表的是队列的第一个元素，rear代表的是队列的最后一个有效元素的下一个元素
3）队列空
front和rear的值相等，但不一定是零

40 _ 队列6 _ 循环队列各个参数的含义

41 _ 队列7 _ 循环队列入队伪算法讲解

数据结构（C语言）队列
两步完成：
1.将值存入r所代表的位置
2.错误的写法：r=r+1;
正确写法是：r=（r+1）%数组的长度
R是5的时候就不能加1，r下一个应该是0

42 _ 队列8 _ 循环队列出队伪算法讲解

数据结构（C语言）队列
f=（f+1）%数组的长度

43 _ 队列9 _ 如何判断循环队列是否为空

如果front于rear的值相等，则该队列就一定为空。

44 _ 队列10 _ 如何判断循环队列是否已满

数据结构（C语言）队列
图1：m n f p q 图2：q r s m 都是4个元素
f 和 r 的大小没有关系。
若f、r相等，不知道队列到底是空还是满。
预备知识：
front的值可能比rear大，也可能比rear小，也可能两者相等。
如何判断循环队列是否已满
两种方式：
1.多增加一个标志参数
2.少用一个元素【通常使用第二种方式】
如何判断队列已满：如果f和r的值紧挨着，则队列已满
用C语言伪算法表示就是：
if（（r+1）%数组长度==f）
已满
else
不满
数据结构（C语言）队列

45 _ 复习 _ 求链表的长度

46 _ 复习上节课队列知识

队列
定义：一种可以实现先进先出的存储结构
分类：
静态队列
链式队列（其实就是对链表操作，砍去了一些功能）

47 _ 循环队列程序演示

队列算法：
入队
出队

静态队列是一个数组，是一个循环数组，需要队首、队尾、以及数组。

typedef struct Queue
{
	int *pBase;  //代表的是那个数组
	int front;
	int rear;
}QUEUE;

1、初始化队列
初始化队列，分配一个数组，队首和队尾都是下表为0的那个位置

void init(QUEUE *pQ)
{
	pQ->pBase = (int *)malloc(sizeof(int) * 6);//6个元素
	//malloc动态分配6个元素的空间24个字节，malloc(sizeof(int) * 6)表示第一个字节的地址；
	//(int *)表示4个字节为一个元素的空间;
	//pQ->pBase 第一个元素的首地址（第一个元素占四个字节），pQ->pBase+1表示第二个元素首地址
	pQ->front = 0;
	pQ->rear = 0;
}

2、入队
入队时将这个元素放在r的位置，然后让r指向下一个（但是注意这里的下一个都是要用循环的）

bool full_queue(QUEUE * pQ)
{
	if ((pQ->rear + 1) % 6 == pQ->front)
		return true;
	else
		return false;
}

//如果不满，要放在r的位置，不是r的下一个位置
bool en_queue(QUEUE * pQ, int val)
{
	if (full_queue(pQ))
	{
		return false;
	}
	else
	{
		pQ->pBase[pQ->rear] = val;
		pQ->rear = (pQ->rear + 1) % 6;
		return true;
	}
}

3、遍历
循环遍历输出所有数组的元素

void traverse_queue(QUEUE * pQ)
{
	int i = pQ->front;
	while (i != pQ->rear)
	{
		printf("%d ", pQ->pBase[i]);
		i = (i + 1) % 6;
	}
	printf("\n");
}

4、出队
f 往后移动就可以，这个是循环数组，不需要释放内存什么的，后来还有可能循环回来的。

bool empty_queue(QUEUE * pQ)
{
	if (pQ->front == pQ->rear)
		return true;
	else
		return false;
}

bool out_queue(QUEUE * pQ, int * pVal)  // int * pVal)目的将值传递给主函数
{
	if (empty_queue(pQ))
	{
		return false;
	}
	else
	{
		*pVal = pQ->pBase[pQ->front];
		pQ->front = (pQ->front + 1) % 6;
		return true;
	}
}

5、实例

#include<stdio.h>
#include<malloc.h>

typedef struct Queue
{
	int *pBase;  //代表的是那个数组
	int front;
	int rear;
}QUEUE;


void init(QUEUE *);
bool en_queue(QUEUE *, int);//入队
void traverse_queue(QUEUE *);
bool full_queue(QUEUE *);
bool out_queue(QUEUE *, int *);
bool empty_queue(QUEUE *);

int main(void)
{
	QUEUE Q;
	int val;
	init(&Q);
	en_queue(&Q, 1);
	en_queue(&Q, 2);
	en_queue(&Q, 3);
	en_queue(&Q, 4);
	en_queue(&Q, 5);
	en_queue(&Q, 6);
	en_queue(&Q, 7); //入队失败
	traverse_queue(&Q);
	if (out_queue(&Q, &val))
	{
		printf("出队成功，队列出队的元素是%d\n", val);
	}
	else
	{
		printf("出队失败！\n");
	}
	traverse_queue(&Q);
	out_queue(&Q, &val);
	out_queue(&Q, &val);
	out_queue(&Q, &val);
	out_queue(&Q, &val);
	out_queue(&Q, &val);
	
	if (out_queue(&Q, &val))
	{
		printf("出队成功，队列出队的元素是%d\n", val);
	}
	else
	{
		printf("出队失败！\n");
	}


	return 0;
}

void init(QUEUE *pQ)
{
	pQ->pBase = (int *)malloc(sizeof(int) * 6);//6个元素
	pQ->front = 0;
	pQ->rear = 0;
}

bool full_queue(QUEUE * pQ)
{
	if ((pQ->rear + 1) % 6 == pQ->front)
		return true;
	else
		return false;
}


//如果不满，要放在r的位置，不是r的下一个位置
bool en_queue(QUEUE * pQ, int val)
{
	if (full_queue(pQ))
	{
		return false;
	}
	else
	{
		pQ->pBase[pQ->rear] = val;
		pQ->rear = (pQ->rear + 1) % 6;
		return true;
	}
}

void traverse_queue(QUEUE * pQ)
{
	int i = pQ->front;
	while (i != pQ->rear)
	{
		printf("%d ", pQ->pBase[i]);
		i = (i + 1) % 6;
	}
	printf("\n");
}

bool empty_queue(QUEUE * pQ)
{
	if (pQ->front == pQ->rear)
		return true;
	else
		return false;
}

bool out_queue(QUEUE * pQ, int * pVal)  // int * pVal)目的将值传递给主函数
{
	if (empty_queue(pQ))
	{
		return false;
	}
	else
	{
		*pVal = pQ->pBase[pQ->front];
		pQ->front = (pQ->front + 1) % 6;
		return true;
	}
}

数据结构（C语言）队列

48 _ 队列的具体应用

所有和时间有关的操作都有队列的影子

相关推荐