首页 > 其他分享 >队列及其C语言实现

队列及其C语言实现

时间：2024-07-25 11:57:27浏览次数：8  
标签：ElementType 队列 及其 PtrQ Queue int front C语言

2.3队列

2.3.1什么是队列

队尾入队，队头出队，一个受限制性的线性表。

队列(Queue)：具有一定操作约束的线性表

• 插入和删除操作：只能在一端插入，而在另一端删除。

• 数据插入：入队列（AddQ）

• 数据删除：出队列（DeleteQ）

• 先来先服务

• 先进先出：FIFO 

2.3.2队列的抽象数据类型描述 

类型名称：队列(Queue)

数据对象集：一个有0个或多个元素的有穷线性表。

操作集：长度为MaxSize的队列Q ∈ Queue，队列元素item ∈ ElementType

1、Queue CreatQueue( int MaxSize )：生成长度为MaxSize的空队列；

2、int IsFullQ( Queue Q, int MaxSize )：判断队列Q是否已满；

3、void AddQ( Queue Q, ElementType item )： 将数据元素item插入队列Q中；

4、int IsEmptyQ( Queue Q )： 判断队列Q是否为空；

5、ElementType DeleteQ( Queue Q )：将队头数据元素从队列中删除并返回。

2.3.3队列的顺序存储实现 

        队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成。 

#define MaxSize <储存数据元素的最大个数>
struct QNode {
ElementType Data[ MaxSize ];
int rear;
int front;
};
typedef struct QNode *Queue;

顺序队列工作流程 

初始只有一个元素时： 

 一个元素入队：

 

 再一个元素入队：

 一个元素出队：

 那要是队列放满之后，再删除队头几个元素，新加的元素放在哪呢？

 

        其实我们依旧可以将新加的元素放在对头的空位置就可以，但是这个时候会发现front 和 rear的顺序会反过来，这时我们可以将该队列做成循环队列。 

 

但是，当rear转一圈，队列满了之后front又会等于rear，那么这时队列是满是空呢？

 

其实解决方法很简单，我们六个位置只放五个就好，这样front就不会再次等于rear了。

所以我们判断队列是否满队时就对队尾+1再和队长取余操作就可以。

int IsFullQ(Queue PtrQ) {
    return ((PtrQ->rear + 1) % MaxSize == PtrQ->front); // 判断队列是否已满
}

有了“不放满”的设定之后，就可以通过front是否等于rear来判断是否空队列了。

int IsEmptyQ(Queue PtrQ) {
    return (PtrQ->front == PtrQ->rear); // 判断队列是否为空
}

综上，我们使用“加1取余法”完成了循环队列的设计。

“加1取余法”

其实这种方式很简单

#include <stdio.h>

int main(void){
	int i;
	for(i=0;i<100;i++){
		printf("%d\n",(i+1)%6);
	}	
	return 0;
};

 我们很简单的就实现了0~max-1的循环输出。

 

 完整代码实现

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

#define ERROR ((ElementType){.num = "ERROR", .name = "ERROR", .sex = "ERROR", .age = -1})  // 定义错误元素
#define MaxSize 100 // 定义储存数据元素的最大个数

/* 队列元素示例 */ 
typedef struct student {
    char num[20];   // 学号
    char name[20];  // 姓名
    char sex[5];    // 性别
    int age;        // 年龄
} ElementType;

struct QNode {
    ElementType Data[MaxSize]; // 队列数据
    int rear;                  // 队尾指针
    int front;                 // 队头指针
};
typedef struct QNode *Queue;

/* 操作集声明 */ 
Queue CreateQueue(); // 生成空队列

int IsFullQ(Queue PtrQ); // 判断队列是否已满

void AddQ(Queue PtrQ, ElementType item); // 将数据元素插入队列

int IsEmptyQ(Queue PtrQ); // 判断队列是否为空

ElementType DeleteQ(Queue PtrQ); // 将队头数据元素从队列中删除并返回

Queue CreateQueue() {
    Queue PtrQ = (Queue)malloc(sizeof(struct QNode)); // 分配队列空间
    PtrQ->front = PtrQ->rear = 0; // 初始化队头和队尾指针
    return PtrQ;
}

int IsFullQ(Queue PtrQ) {
    return ((PtrQ->rear + 1) % MaxSize == PtrQ->front); // 判断队列是否已满
}

int IsEmptyQ(Queue PtrQ) {
    return (PtrQ->front == PtrQ->rear); // 判断队列是否为空
}

void AddQ(Queue PtrQ, ElementType item) {
    if (IsFullQ(PtrQ)) {
        printf("队列满\n"); // 队列满时打印信息
        return;
    }
    PtrQ->rear = (PtrQ->rear + 1) % MaxSize; // 更新队尾指针
    PtrQ->Data[PtrQ->rear] = item; // 插入新元素
}

ElementType DeleteQ(Queue PtrQ) {
    if (IsEmptyQ(PtrQ)) {
        printf("队列空\n"); // 队列空时打印信息
        return ERROR; // 返回错误元素
    } else {
        PtrQ->front = (PtrQ->front + 1) % MaxSize; // 更新队头指针
        return PtrQ->Data[PtrQ->front]; // 返回队头元素
    }
}

int main() {
    Queue q = CreateQueue(); // 创建队列
    ElementType student1 = {"2021001", "Alice", "F", 20}; // 创建学生1
    ElementType student2 = {"2021002", "Bob", "M", 21}; // 创建学生2
    
    AddQ(q, student1); // 插入学生1
    AddQ(q, student2); // 插入学生2
    
    while (!IsEmptyQ(q)) { // 队列不为空时
        ElementType student = DeleteQ(q); // 删除队头元素
        printf("删除的学生: %s, %s, %s, %d\n", student.num, student.name, student.sex, student.age); // 打印删除的学生信息
    }
    
    return 0;
}

 

 

2.3.4队列的链式存储实现 

        队列的链式存储结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行；队列指针front和rear应该分别指向链表的头结点和尾结点。 

 

        front需要做删除操作的时候必须知晓下一个结点是是谁，所以必须指向队头。

结构定义 

struct Node{
 ElementType Data;
 struct Node *Next;
};
struct QNode{ /* 链队列结构 */
 struct Node *rear; /* 指向队尾结点 */
 struct Node *front; /* 指向队头结点 */
};
typedef struct QNode *Queue;
Queue PtrQ;

图示

 

完整实现 

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

#define ERROR ((ElementType){.num = "ERROR", .name = "ERROR", .sex = "ERROR", .age = -1})  // 定义错误元素

/* 队列元素示例 */ 
typedef struct student {
    char num[20];   // 学号
    char name[20];  // 姓名
    char sex[5];    // 性别
    int age;        // 年龄
} ElementType;

/* 结构定义 */
struct Node {
    ElementType Data;
    struct Node *Next;
};
typedef struct Node *NodePtr;

struct QNode { /* 链队列结构 */
    NodePtr rear; /* 指向队尾结点 */
    NodePtr front; /* 指向队头结点 */
};
typedef struct QNode *Queue;

/* 操作集声明 */ 
Queue CreatQueue(); // 生成空队列

int IsFullQ(Queue PtrQ, int MaxSize); // 判断队列是否已满

void AddQ(Queue PtrQ, ElementType item); // 将数据元素插入队列

int IsEmptyQ(Queue PtrQ); // 判断队列是否为空

ElementType DeleteQ(Queue PtrQ); // 将队头数据元素从队列中删除并返回

Queue CreatQueue() {
    Queue PtrQ = (Queue)malloc(sizeof(struct QNode)); // 分配队列空间
    PtrQ->front = PtrQ->rear = NULL; // 初始化队头和队尾
    return PtrQ;
}

int IsFullQ(Queue PtrQ, int MaxSize) {
    // 由于是链队列，通常不会满，除非内存分配失败。
    // 如果有特定约束，可以实现这个函数，但通常链队列不被认为会满。
    return 0;
}

int IsEmptyQ(Queue PtrQ) {
    return (PtrQ->front == NULL); // 判断队列是否为空
}

ElementType DeleteQ(Queue PtrQ) {
    NodePtr FrontCell;
    ElementType FrontElem;
    if (PtrQ->front == NULL) {
        printf("队列为空!\n");
        return ERROR; // 返回错误元素
    }
    FrontCell = PtrQ->front; // 获取队头结点
    if (PtrQ->front == PtrQ->rear) /* 如果队列只有一个元素 */
        PtrQ->front = PtrQ->rear = NULL; /* 删除后队列置为空 */
    else
        PtrQ->front = PtrQ->front->Next; // 队头指针指向下一个结点
    FrontElem = FrontCell->Data; // 保存队头数据
    free(FrontCell); /* 释放被删除结点空间 */
    return FrontElem; // 返回队头数据
}

void AddQ(Queue PtrQ, ElementType item) {
    NodePtr TempCell;
    TempCell = (NodePtr)malloc(sizeof(struct Node)); // 分配新结点空间
    TempCell->Data = item; // 设置新结点数据
    TempCell->Next = NULL; // 新结点指向空

    if (PtrQ->front == NULL) { // 如果队列为空
        PtrQ->front = PtrQ->rear = TempCell; // 新结点为队头和队尾
    } else {
        PtrQ->rear->Next = TempCell; // 将新结点连接到队尾
        PtrQ->rear = TempCell; // 更新队尾指针
    }
    printf("%s 已成功插入!\n", item.num); // 打印插入成功信息
}

int main() {
    Queue q = CreatQueue(); // 创建队列
    ElementType student1 = {"2021001", "Alice", "F", 20}; // 创建学生1
    ElementType student2 = {"2021002", "Bob", "M", 21}; // 创建学生2
    
    AddQ(q, student1); // 插入学生1
    AddQ(q, student2); // 插入学生2
    
    while (!IsEmptyQ(q)) { // 队列不为空时
        ElementType student = DeleteQ(q); // 删除队头元素
        printf("删除的学生: %s, %s, %s, %d\n", student.num, student.name, student.sex, student.age); // 打印删除的学生信息
    }
    
    return 0;
}

 

 

 

 

标签：ElementType,队列,及其,PtrQ,Queue,int,front,C语言
From： https://blog.csdn.net/weixin_65866298/article/details/140652443

相关文章

  • C语言面向对象风格编程解惑-全局变量性能分析
    C语言面向对象风格编程解惑-全局变量性能分析如果你是CPP老手，但在软件开发过程中要求采用C语言作为主要语言，首先遇到的是各种设计模式不方便应用了，感到非常困扰，然后就是认命之后走向另外一个极端，常常会有过度使用全局变量和goto语句的问题。CPP既然是CWithClass，自然不会排斥面......
  • Tower Of Hanoi - 汉诺塔问题（C语言）
    ☆WelcometoHouse'sblog!☆本人主页：神王豪斯（重拾基础期）-CSDN博客所属专栏：重拾C语言——神王降世的第一步！_神王豪斯（重拾基础期）的博客-CSDN博客1.游戏规则-有三根柱子（通常分别命名为A、B、C）和若干大小不同的圆盘。-最初，所有圆盘按照从大到小的顺序堆叠在一根柱子（比如......
  • 【 C语言 】 C语言设计模式
    一、C语言和设计模式（继承、封装、多态）C++有三个最重要的特点，即继承、封装、多态。我发现其实C语言也是可以面向对象的，也是可以应用设计模式的，关键就在于如何实现面向对象语言的三个重要属性。（1）继承性[cpp]viewplaincopytypedefstruct_parent{intdata_parent;......
  • C语言程序设计练习（三）
    1.整型数据类型存储空间大小#include<stdio.h>intmain(){printf("Sizeofint:%zubytes\n",sizeof(int));printf("Sizeofshort:%zubytes\n",sizeof(short));printf("Sizeoflong:%zubytes\n",sizeof(l......
  • C语言：数组
    hello,大家好今天我们来讲解c语言中数组的知识。一、数组的概念数组是⼀组相同类型元素的集合；数组中存放的是1个或者多个数据，但是数组元素个数不能为0。数组中存放的多个数据，类型是相同的。数组分为一维数组和多维数组，多维数组一般比较多见的是二维数组。二、一维数组 1......
  • c语言--数组详解
    数组的概念数组是一组相同类型元素的集合；从这个概念我们就可以发现2个有价值的信息：数组中存放的是1个或多个数据，但是数组的元素不能为0。数组中存放的多个数据，类型是相同的。数组分为一维数组和多维数组，多维数组一般比较多见的是二维数组。一维数组1.一维数组的创建和初......
  • 深入理解淘客返利系统中的消息队列系统设计与优化
    深入理解淘客返利系统中的消息队列系统设计与优化大家好，我是微赚淘客系统3.0的小编，是个冬天不穿秋裤，天冷也要风度的程序猿！今天我们来深入探讨淘客返利系统中的消息队列系统设计与优化。消息队列在分布式系统中的应用已经非常广泛，对于淘客返利系统来说，消息队列能帮助我们更......
  • C语言学习day03
    变量概念表面：程序运行过程中取值可以改变的数据实质：变量其实代表了一块内存区域/单元/空间。变量名可视为该区域的标识。整个变量分为三部分：  变量名：这个只是变量的一个标识，我们借助变量名来存取数据。  变量空间/内存单元：这个就是内存中分配的一块用来存储数据的......
  • C语言——数据类型
    C语言——数据类型C语言中的数据类型种类整型整型的常量形式整型的变量形式整型类型的分类整型数据在内存中的存储浮点型浮点型的大小浮点型数据的存储浮点数的比较问题字符型C语言中的数据类型种类数据类型可分为基本数据类型（整型，浮点型，字符型，枚举类型），构造数据类......
  • c语言-数组（1）
    5.数组（1）数组的意义：保存多个具有相同数据类型的数据特点：（1）具有相同的数据类型。（2）数据的地址是连续的 数组的表现形式类型标识符[长度];数组的空间大小 数组的空间大小=单个数据的空间大小*长度tip：已知数组table，求该数组的长度？intl=sizeof(table)/sizeof(......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99