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

数据结构-队列-顺序队列

article 2024/11/25 18:36:45

完整代码：

/*
ADT 队列（Queue）
Data
		同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
		InitQueue(*Q)：初始化操作。建立一个空队列Q。
		DestroyQueue(*Q)：若队列Q存在，销毁它。
		ClearQueue(*Q)：将队列Q清空。
		QueueEmpty(Q)：若队列Q为空，返回1，否则返回0。
		GetHead(Q, *e)：若队列Q存在且非空，用e返回队列Q的队头元素。
		EnQueue(*Q, e)：若队列存在，插入新元素e到队列Q中并成为队尾元素。
		DeQueue(*Q, *e) : 删除队列Q中队头元素，并用e返回其值。
		QueueLength(Q)：返回队列Q的元素个数。
endADT
*/
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:6013)

#include<stdio.h>
#include<stdlib.h>
//#include<time.h>
#define MAXSIZE 10

typedef int QElemType;
typedef int Status;
typedef struct {
	QElemType data[MAXSIZE];
	int front, rear;
}SqQueue;
// 队列为满的条件为数组中只有一个元素为空，其他元素都存储数据。

void InitQueue(SqQueue* Q);
void DestroyQueue(SqQueue* Q);
void ClearQueue(SqQueue* Q);
Status QueueEmpty(SqQueue Q);
Status GetHead(SqQueue Q, QElemType* e);
Status EnQueue(SqQueue* Q, QElemType e);
Status DeQueue(SqQueue* Q, QElemType* e);
int QueueLength(SqQueue Q);
void _print(SqQueue Q);
void randInsert(SqQueue* Q, int n);

void test(SqQueue* Q) {
	for (int i = 0; i < MAXSIZE; i++) {
		if (i == Q->front) {
			printf("front --> ");
		}
		if (i == Q->rear) {
			printf("rear --> ");
		}
		printf("[%d]\t%d\n", i, Q->data[i]);
	}
}

// 打印菜单函数
void printQueueMenu() {
	printf("=========================菜单-顺序队列===================================\n");
	printf("(1)初始化\t\t\t(2)销毁\t\t\t\t\t|\n");
	printf("(3)清空\t\t\t\t(4)判断队列是否为空\t\t\t|\n");
	printf("(5)获取队头元素\t\t\t(6)入队操作\t\t\t\t|\n");
	printf("(7)出队操作\t\t\t(8)获取队列中元素个数\t\t\t|\n");
	printf("(9)随机生成元素入队\t\t(10)菜单\t\t\t\t|\n");
	printf("(11)输出队列元素\t\t\t\t\t\t\t|\n");
	printf("(0)退出\t\t\t\t\t\t\t\t\t|\n");
	printf("=========================================================================\n");
}

// 菜单函数
void queueMenu() {
	SqQueue Q;
	InitQueue(&Q);
	printf("初始化成功。\n");
	int choice;
	QElemType element;
	int num;
	printQueueMenu();

	while (1) {
		printf("请输入你的选择: ");
		scanf("%d", &choice);

		switch (choice) {
		case 999:
			test(&Q);
			break;
		case 11:
			_print(Q);
			break;
		case 10:
			printQueueMenu();
			break;
		case 1:
			InitQueue(&Q);
			printf("队列已重新初始化成功\n");
			break;
		case 2:
			DestroyQueue(&Q);
			printf("队列已销毁\n");
			break;
		case 3:
			ClearQueue(&Q);
			printf("队列已清空\n");
			break;
		case 4:
			if (QueueEmpty(Q)) {
				printf("队列为空\n");
			}
			else {
				printf("队列不为空\n");
			}
			break;
		case 5:
			if (GetHead(Q, &element)) {
				printf("队头元素为: %d\n", element);
			}
			else {
				printf("队列为空，无法获取队头元素\n");
			}
			break;
		case 6:
			printf("请输入要入队的元素: ");
			scanf("%d", &element);
			if (EnQueue(&Q, element)) {
				printf("元素入队成功\n");
			}
			else {
				printf("入队失败，队列可能已满或已被销毁\n");
			}
			break;
		case 7:
			if (DeQueue(&Q, &element)) {
				printf("出队元素为: %d\n", element);
			}
			else {
				printf("队列为空，无法出队\n");
			}
			break;
		case 8:
			num = QueueLength(Q);
			printf("队列中元素个数为: %d\n", num);
			break;
		case 9:
			printf("请输入要随机生成入队的元素个数: ");
			scanf("%d", &num);
			randInsert(&Q, num);
			printf("已随机生成元素入队\n");
			break;
		case 0:
			printf("程序已退出\n");
			exit(0);
		default:
			printf("输入的选择无效，请重新输入\n");
			break;
		}
	}
}

int main() {
	queueMenu();
	return 0;
}

/// <summary>
/// 初始化操作。建立一个空队列Q。
/// </summary>
void InitQueue(SqQueue* Q) {
	for (int i = 0; i < MAXSIZE; i++) {
		Q->data[i] = 0;
	}
	Q->front = 0;
	Q->rear = 0;
}

/// <summary>
/// 若队列Q存在，销毁它。
/// </summary>
void DestroyQueue(SqQueue* Q) {
	Q->front = -1;
	Q->rear = -1;
}

/// <summary>
/// 将队列Q清空。
/// </summary>
void ClearQueue(SqQueue* Q) {
	Q->front = 0;
	Q->rear = 0;
}

/// <summary>
/// 若队列Q为空，返回1，否则返回0。
/// </summary>
Status QueueEmpty(SqQueue Q) {
	return (Q.front == Q.rear) ? 1 : 0;
}

/// <summary>
/// 若队列Q存在且非空，用e返回队列Q的队头元素。
/// </summary>
Status GetHead(SqQueue Q, QElemType* e) {
	if (Q.front == Q.rear || Q.front < 0)return 0;	//为空，或则被销毁；
	*e = Q.data[Q.front];
	return 1;
}

/// <summary>
/// 若队列存在，插入新元素e到队列Q中并成为队尾元素。
/// </summary>
Status EnQueue(SqQueue* Q, QElemType e) {
	if ((Q->rear + 1 + MAXSIZE) % MAXSIZE == Q->front || Q->front < 0)return 0;
	Q->data[Q->rear] = e;
	Q->rear = (Q->rear + 1) % MAXSIZE;
	return 1;
}

/// <summary>
/// 删除队列Q中队头元素，并用e返回其值。
/// </summary>
Status DeQueue(SqQueue* Q, QElemType* e) {
	if (Q->front == Q->rear || Q->front < 0)return 0;
	*e = Q->data[Q->front];
	Q->front = (Q->front + 1) % MAXSIZE;
	return 1;
}

/// <summary>
/// 返回队列Q的元素个数。
/// </summary>
int QueueLength(SqQueue Q) {
	return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

/// <summary>
/// 输出队列
/// </summary>
/// <param name="Q"></param>
void _print(SqQueue Q) {
	if (Q.front < 0 || Q.front == Q.rear) {
		return;
	}
	for (int i = Q.front; i != Q.rear; i = (i + 1) % MAXSIZE) {
		printf("%d\t", Q.data[i]);
	}
	printf("\n");
}

/// <summary>
/// 在队列中生成n个随机数据。
/// </summary>
/// <param name="Q"></param>
/// <param name="n"></param>
void randInsert(SqQueue* Q, int n) {
	// 初始化随机数种子
	int min = 0;
	int max = 1000;
	int range = max - min + 1;

	for (int j = 0; j < n; j++) {
		QElemType e = min + rand() % range;
		if (EnQueue(Q, e)) { //这里之所以不用&Q是因为Q已经是一个地址了。
			printf("插入 %d 成功。\n", e);
		}
		else {
			printf("插入 %d 失败，队列满或已被销毁。\n", e);
			break;
		}
	}
	printf("\n");
}

一、顺序队列是什么？

顺序队列是一种线性数据结构，它遵循先进先出（FIFO）的原则。在顺序队列中，元素被存储在一个连续的数组空间里，并且有两个指针，一个指向队头（front），一个指向队尾（rear）。当有元素入队时，队尾指针向后移动；当有元素出队时，队头指针向后移动。它就像是一个排队的队伍，先到的人先接受服务并离开队伍。

二、功能函数详解

（一）初始化函数 - InitQueue(SqQueue* Q)

void InitQueue(SqQueue* Q) {
    for (int i = 0; i < MAXSIZE; i++) {
        Q->data[i] = 0;
    }
    Q->front = 0;
    Q->rear = 0;
}

作用：建立一个空队列 Q。将队列中的数据数组元素全部初始化为 0，并将队头和队尾指针都设置为 0，表示队列为空。

实现细节：通过循环遍历数据数组 data，把每个元素赋值为 0。然后明确队列初始状态下，队头和队尾的位置都在数组的起始位置，即索引为 0 的地方。

（二）销毁函数 - DestroyQueue(SqQueue* Q)

void DestroyQueue(SqQueue* Q) {
    Q->front = -1;
    Q->rear = -1;
}

作用：若队列 Q 存在，将其“销毁”。这里的销毁并非真正释放内存空间，而是通过将队头和队尾指针设置为 -1，来表示队列已被销毁，后续对该队列的操作可以根据这个标识进行判断。

实现细节：简单地把队头和队尾指针修改为 -1，以此来标记队列的“销毁”状态。

（三）清空函数 - ClearQueue(SqQueue* Q)

void ClearQueue(SqQueue* Q) {
    Q->front = 0;
    Q->rear = 0;
}

作用：将队列 Q 清空。使队列回到初始的空队列状态，即队头和队尾指针都指向数组的起始位置。

实现细节：把队头和队尾指针重新设置为 0，就像初始化时一样，这样就表示队列中没有元素了，完成了清空操作。

（四）判空函数 - QueueEmpty(SqQueue Q)

Status QueueEmpty(SqQueue Q) {
    return (Q.front == Q.rear)? 1 : 0;
}

作用：判断队列 Q 是否为空。如果队头和队尾指针相等，说明队列中没有元素，返回 1；否则返回 0。

实现细节：通过比较队头和队尾指针的值来确定队列是否为空。这是因为在空队列时，队头和队尾都指向同一个位置（初始位置或在清空后恢复的初始位置）。

（五）获取队头元素函数 - GetHead(SqQueue Q, QElemType* e)

Status GetHead(SqQueue Q, QElemType* e) {
    if (Q.front == Q.rear || Q.front < 0)return 0;    //为空，或者被销毁；
    *e = Q.data[Q.front];
    return 1;
}

作用：若队列 Q 存在且非空，用 e 返回队列 Q 的队头元素。

实现细节：首先判断队列是否为空（队头和队尾指针相等）或者是否被销毁（队头指针小于 0），如果是则无法获取队头元素，返回 0。如果队列正常且非空，就将队头指针所指向的数组元素赋值给 e，并返回 1 表示获取成功。

（六）入队函数 - EnQueue(SqQueue* Q, QElemType e)

Status EnQueue(SqQueue* Q, QElemType e) {
    if ((Q->rear + 1 + MAXSIZE) % MAXSIZE == Q->front || Q->front < 0)return 0;
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAXSIZE;
    return 1;
}

作用：若队列存在，插入新元素 e 到队列 Q 中并成为队尾元素。

实现细节：先判断队列是否已满。判断条件 (Q->rear + 1 + MAXSIZE) % MAXSIZE == Q->front 是因为在循环队列中，当队尾指针的下一个位置（Q->rear + 1）与队头指针相等时，表示队列已满。这里加上 MAXSIZE 再取余是为了处理循环的情况，例如当队尾指针在数组末尾时，下一个位置应该回到数组开头。如果队列未满，就将元素 e 放入队尾指针所指向的数组位置，然后将队尾指针向后移动一位，这里通过取余运算 Q->rear = (Q->rear + 1) % MAXSIZE 实现循环移动队尾指针，最后返回 1 表示入队成功。

（七）出队函数 - DeQueue(SqQueue* Q, QElemType* e)

Status DeQueue(SqQueue* Q, QElemType* e) {
    if (Q->front == Q->rear || Q->front < 0)return 0;
    *e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;
    return 1;
}

作用：删除队列 Q 中队头元素，并用 e 返回其值。

实现细节：首先判断队列是否为空（队头和队尾指针相等）或者是否被销毁（队头指针小于 0），如果是则无法出队，返回 0。如果队列正常且非空，就将队头指针所指向的数组元素赋值给 e，然后将队头指针向后移动一位，同样通过取余运算 Q->front = (Q->front + 1) % MAXSIZE 实现循环移动队头指针，最后返回 1 表示出队成功。

（八）获取队列长度函数 - QueueLength(SqQueue Q)

int QueueLength(SqQueue Q) {
    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

作用：返回队列 Q 的元素个数。

实现细节：由于是循环队列，计算长度不能简单地用队尾指针减去队头指针。这里通过 (Q.rear - Q.front + MAXSIZE) % MAXSIZE 来计算。加上 MAXSIZE 是为了防止队尾指针小于队头指针时出现负数结果，取余运算则是处理循环队列的情况，确保得到正确的元素个数。

（九）随机插入函数 - randInsert(SqQueue* Q, int n)

void randInsert(SqQueue* Q, int n) {
    // 初始化随机数种子
    int min = 0;
    int max = 1000;
    int range = max - min + 1;

    for (int j = 0; j < n; j++) {
        QElemType e = min + rand() % range;
        if (EnQueue(Q, e)) { //这里之所以不用&Q是因为Q已经是一个地址了。
            printf("插入 %d 成功。\n", e);
        }
        else {
            printf("插入 %d 失败，队列满或已被销毁。\n", e);
            break;
        }
    }
    printf("\n");
}

作用：在队列中生成 n 个随机数据并插入队列。

实现细节：首先确定随机数的范围，通过 min 和 max 设定，然后计算范围值 range。在循环中，生成一个在指定范围内的随机数 e，并尝试将其入队。如果入队成功（调用 EnQueue 函数成功），则打印插入成功信息；如果入队失败（队列已满或已被销毁），则打印插入失败信息并跳出循环。


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

相关文章：

  • 七天掌握SQL---＞第五天：数据库安全与权限管理
  • 曲谱转换成音频
  • vue实现滚动下拉加载更多
  • 部署自动清理任务解决ORA-00257: archiver error. Connect internal only, until freed
  • Exploring Prompt Engineering: A Systematic Review with SWOT Analysis
  • Java爬虫：获取商品详情的实践之旅
  • tauri2.0版本开发苹果ios和安卓android应用，环境搭建和最后编译为apk
  • C++结构型设计模式之使用抽象工厂来创建和配置桥接模式的例子
  • XviD4PSP视频无损转换器
  • oracle的静态注册和动态注册
  • 数据可视化复习2-绘制折线图+条形图（叠加条形图，并列条形图，水平条形图）+ 饼状图 + 直方图
  • 【技术支持】vscode不使用插件，两种方式重命名html标签对
  • 基于物联网设计的人工淡水湖养殖系统(华为云IOT)_253
  • 关于mqtt协议与qt联合开发的实现记录
  • 用Tauri框架构建跨平台桌面应用：1、Tauri快速开始
  • 【桂林理工大学主办 | 往届均已EI检索】第五届能源工程、新能源材料与器件国际学术会议（NEMD 2025）
  • ctfshow -web 89-115-wp
  • 数据结构之二：表
  • RoPE——Transformer 的旋转位置编码
  • Centos使用docker搭建Graylog日志平台
  • python中的base64使用小笑话
  • vue从入门到精通(七)：事件处理
  • 全新三网话费余额查询API系统源码 Thinkphp全开源 附教程
  • 力扣力扣力：860柠檬水找零
  • 【机器学习监督学习】：从原理到实践，探索算法奥秘，揭示数据标注、模型训练与预测的全过程，助力人工智能技术应用与发展
  • Unity 内置枚举（Option Stencil）