数据结构--循环队列、链队

news/2025/1/15 22:34:02/

基础知识

//循环队列数据结构
typedef struct
{
QElemType data[MaxQSize];//数据域
int front,rear; //队头队尾指针
}SqQueue;

//链队结点数据结构
typedef struct QNode
{
int data;//数据域
struct QNode* next;//指针域

}QNode, * QueuePtr;
typedef struct
{
struct QNode* front, * rear;//rear指针指向队尾 用于入队 front指针指向队头 用于出队
}LinkQueue;

队列是一种常见的数据结构，它遵循==先进先出（FIFO）==的原则。以下是队列的基本操作：
1、入队（Enqueue）：将元素添加到队列的末尾。
2、出队（Dequeue）：从队列的头部移除一个元素，并返回其值。
3、队列长度（Size）：获取队列中元素的个数。
4、队列是否为空（IsEmpty）：检查队列是否为空。
5、获取队首元素（Front）：获取队列头部的元素值，但不移除该元素。

C++ 实现队列的基本操作的示例代码：

#include <iostream>
#include <queue>int main() {std::queue<int> myQueue;// 入队myQueue.push(10);myQueue.push(20);myQueue.push(30);// 队列长度std::cout << "队列长度：" << myQueue.size() << std::endl;// 出队int frontElement = myQueue.front();myQueue.pop();std::cout << "出队元素：" << frontElement << std::endl;// 获取队首元素std::cout << "队首元素：" << myQueue.front() << std::endl;// 队列是否为空std::cout << "队列是否为空：" << (myQueue.empty() ? "是" : "否") << std::endl;return 0;
}

在C语言中，队列的基本操作可以通过结构体和指针来实现。

#include <stdio.h>
#include <stdlib.h>// 定义队列结构体
typedef struct {int *array;  // 存储队列元素的数组int front;   // 队首索引int rear;    // 队尾索引int size;    // 队列的容量
} Queue;// 初始化队列
void initQueue(Queue *queue, int capacity) {queue->array = (int*)malloc(capacity * sizeof(int));queue->front = 0;queue->rear = -1;queue->size = 0;
}// 销毁队列
void destroyQueue(Queue *queue) {free(queue->array);
}// 入队
void enqueue(Queue *queue, int element) {queue->rear = (queue->rear + 1) % queue->size;queue->array[queue->rear] = element;queue->size++;
}// 出队
int dequeue(Queue *queue) {int dequeuedElement = queue->array[queue->front];queue->front = (queue->front + 1) % queue->size;queue->size--;return dequeuedElement;
}// 获取队列长度
int getSize(Queue *queue) {return queue->size;
}// 检查队列是否为空
int isEmpty(Queue *queue) {return queue->size == 0;
}// 获取队首元素
int getFront(Queue *queue) {return queue->array[queue->front];
}int main() {Queue myQueue;initQueue(&myQueue, 5);// 入队enqueue(&myQueue, 10);enqueue(&myQueue, 20);enqueue(&myQueue, 30);// 队列长度printf("队列长度：%d\n", getSize(&myQueue));// 出队int frontElement = dequeue(&myQueue);printf("出队元素：%d\n", frontElement);// 获取队首元素printf("队首元素：%d\n", getFront(&myQueue));// 队列是否为空printf("队列是否为空：%s\n", isEmpty(&myQueue) ? "是" : "否");destroyQueue(&myQueue);return 0;
}

循环队列

#define MaxSize 100
typedef struct { int data[MaxSize]; int front, rear; }SqQueue;//***********************************   基本操作函数  *******************************************int InitQueue(SqQueue &Q)
{Q.front = Q.rear = 0;return 1;}
bool QueueEmpty(SqQueue& Q) {if (Q.front != Q.rear)	return true;else   return false;
}//入队：尾部加1；	出队：头部加1
bool EnQueue(SqQueue& Q, int& e) {if (Q.front ==Q.rear)	return false;e = Q.data[Q.rear];Q.rear = (Q.rear + 1) % MaxSize; //指针加1 取模return true;
}bool DeQueue(SqQueue& Q, int &e) {if (Q.front == Q.rear)	return false;e = Q.data[Q.front];Q.front = (Q.front + 1) % MaxSize; //指针加1 取模return true;
}bool GetHead(SqQueue& Q, int &e)
{if (Q.front == Q.rear)	return false;//队空 					e = Q.data[Q.front];return true;
}//********************************功能实现函数**************************************//void EnterToQueue(SqQueue& Q)
{int n; int e; int flag;printf("请输入入队元素个数(>=1)：\n");scanf("%d", &n);for (int i = 0; i < n; i++){printf("请输入第%d个元素的值:", i + 1);scanf("%d", &e);flag = EnQueue(Q, e);if (flag)printf("%d已入队\n", e);else { printf("队已满！！！\n"); break; }}
}void DeleteFromQueue(SqQueue& Q)
{int n; int e; int flag;printf("请输入出队元素个数(>=1)：\n");scanf("%d", &n);for (int i = 0; i < n; i++){flag = DeQueue(Q, e);if (flag)printf("%d已出队\n", e);else { printf("队已空！！！\n"); break; }}
}void GetHeadOfQueue(SqQueue Q)
{int e; bool flag;flag = GetHead(Q, e);if (flag)printf("队头元素为:%d\n", e);else printf("队已空！！！\n");
}void menu() {printf("********1.入队          2.出队*********\n");printf("********3.取队头元素    4.退出*********\n");
}int main() {SqQueue Q;int choice = 0;;InitQueue(Q);while (1){menu();printf("请输入菜单序号：\n");scanf("%d", &choice);if (choice == 4) break;switch (choice){case 1:EnterToQueue(Q); break;case 2:DeleteFromQueue(Q); break;case 3:GetHeadOfQueue(Q); break;default:printf("输入错误！！！\n");}system("pause");system("cls");}return 0;
}

链队

#define MaxSize 100//链队结点数据结构
typedef struct QNode
{int data;//数据域struct QNode* next;//指针域}QNode, * QueuePtr;
typedef struct
{struct QNode* front, * rear;//rear指针指向队尾 用于入队 front指针指向队头 用于出队
}LinkQueue;//***********************************   基本操作函数  *******************************************int InitQueue(LinkQueue &Q)
{Q.front = Q.rear = new QNode;Q.front->next = NULL;return 1;}int EnQueue(LinkQueue& Q, int& e) {QNode* p;p = new QNode;//生成新节点p->data = e;    //赋值p->next = NULL;Q.rear->next = p;//加入队尾Q.rear = p;      //尾指针后移return 1;
}bool DeQueue(LinkQueue &Q, int &e) {QueuePtr p;if (Q.front == Q.rear)return false;//队空e = Q.front->next->data;           //e返回值 之前写的Q.front->data 炸了，头结点没数据的，一定要注意头结点p = Q.front->next;                //保留，一会儿释放空间Q.front->next = p->next;          //出队,注意Q.front->next 不是Q.front 还有头结点if (Q.rear == p)Q.rear = Q.front;    //最后一个元素出队，rear指向头结点free(p);return true;
}//取队顶函数 用e返回
bool GetHead(LinkQueue &Q, int &e)
{if (Q.front == Q.rear)	return false;//队空 					e = Q.front->next->data;return true;
}//********************************功能实现函数**************************************//void EnterToQueue(LinkQueue& Q)
{int n; int e; int flag;printf("请输入入队元素个数(>=1)：\n");scanf("%d", &n);for (int i = 0; i < n; i++){printf("请输入第%d个元素的值:", i + 1);scanf("%d", &e);flag = EnQueue(Q, e);if (flag)printf("%d已入队\n", e);}
}void DeleteFromQueue(LinkQueue& Q)
{int n; int e; int flag;printf("请输入出队元素个数(>=1)：\n");scanf("%d", &n);for (int i = 0; i < n; i++){flag = DeQueue(Q, e);if (flag)printf("%d已出队\n", e);else { printf("队已空！！！\n"); break; }}
}void GetHeadOfQueue(LinkQueue Q)
{int e; bool flag;flag = GetHead(Q, e);if (flag)printf("队头元素为:%d\n", e);else printf("队已空！！！\n");
}void menu() {printf("********1.入队          2.出队*********\n");printf("********3.取队头元素    4.退出*********\n");
}int main() {LinkQueue Q;int choice = 0;;InitQueue(Q);while (1){menu();printf("请输入菜单序号：\n");scanf("%d", &choice);if (choice == 4) break;switch (choice){case 1:EnterToQueue(Q); break;case 2:DeleteFromQueue(Q); break;case 3:GetHeadOfQueue(Q); break;default:printf("输入错误！！！\n");}system("pause");system("cls");}return 0;
}

http://www.ppmy.cn/news/987159.html

相关文章

力扣 738. 单调递增的数字

力扣 738. 单调递增的数字

题目来源&#xff1a;https://leetcode.cn/problems/monotone-increasing-digits/description/ C题解&#xff1a;像1234就可以直接返回1234&#xff0c;像120需要从个位往高位遍历&#xff0c;2比0大&#xff0c;那么2减一成为1&#xff0c;0变成9&#xff0c;变成119。 clas…
阅读更多...
行为型-状态模式（State Pattern）

行为型-状态模式（State Pattern）

概述 状态模式是一种行为设计模式&#xff0c;它可以让对象在内部状态改变时改变它的行为。简而言之&#xff0c;状态模式允许对象在不同状态下更改其行为&#xff0c;而不需要通过使用大量的条件语句进行手动更改。 优点&#xff1a; 状态模式将与特定状态相关的行为分散到…
阅读更多...
Flutter：flutter_local_notifications——消息推送的学习

Flutter：flutter_local_notifications——消息推送的学习

前言 注&#xff1a; 刚开始学习&#xff0c;如果某些案例使用时遇到问题&#xff0c;可以自行百度、查看官方案例、官方github。 简介 Flutter Local Notifications是一个用于在Flutter应用程序中显示本地通知的插件。它提供了一个简单而强大的方法来在设备上发送通知&#…
阅读更多...
MySQL 8.0详细安装配置教程

MySQL 8.0详细安装配置教程

一. 前言 MySQL是目前最为流行的开源数据库产品&#xff0c;是完全网络化跨平台的关系型数据库系统。它起初是由瑞典MySQLAB公司开发&#xff0c;后来被Oracle公司收购&#xff0c;目前属于Oracle公司。因为开源&#xff0c;所以任何人都能从官网免费下载MySQL软件&#xff0c…
阅读更多...
机器学习分布式框架ray tune笔记

机器学习分布式框架ray tune笔记

Ray Tune作为Ray项目的一部分&#xff0c;它的设计目标是简化和自动化机器学习模型的超参数调优和分布式训练过程。Ray Tune简化了实验过程&#xff0c;使研究人员和数据科学家能够高效地搜索最佳超参数&#xff0c;以优化模型性能。 Ray Tune的主要特点包括&#xff1a; 超参…
阅读更多...
P3059 [USACO12NOV] Concurrently Balanced Strings G 题解

P3059 [USACO12NOV] Concurrently Balanced Strings G 题解

前言 现在是 2023 2023 2023 年 7 7 7 月 29 29 29 日凌晨 1 1 1 点 47 47 47 分&#xff0c;我听着我歌单的歌&#xff0c;进入了精神极其不正常的状态&#xff08;正经人谁在凌晨边听摇滚边写题啊&#xff09;。 所以我会胡言几句&#xff0c;大家请选择性忽视。 这道…
阅读更多...
C++数据结构笔记（11）二叉树的#号创建法及计算叶子节点数

C++数据结构笔记（11）二叉树的#号创建法及计算叶子节点数

首先分享一段计算叶子节点数目的代码&#xff0c;如下图&#xff1a; 不难发现&#xff0c;上面的二叉树叶子节点数目为4。我们可以采用递归的方式&#xff0c;每当一个结点既没有左结点又没有右节点时&#xff0c;即可算为一个叶子结点。 int num0; //全局变量&#xff0c;代…
阅读更多...
2.7. Java 泛型了解么？什么是类型擦除？介绍一下常用的通配符？

2.7. Java 泛型了解么？什么是类型擦除？介绍一下常用的通配符？

Java 泛型&#xff08;generics&#xff09;是 JDK 5 中引入的一个新特性, 泛型提供了编译时类型安全检测机制&#xff0c;该机制允许程序员在编译时检测到非法的类型。泛型的本质是参数化类型&#xff0c;也就是说所操作的数据类型被指定为一个参数。 Java 的泛型是伪泛型&am…
阅读更多...
最新文章

Copyright @ 2022~2023