数据结构——队列练习题

news/2024/7/8 10:32:49 标签: 数据结构

在C语言中，.和->运算符用于访问结构体的成员变量。它们之间的区别在于：.运算符用于访问结构体变量的成员。->运算符用于访问结构体指针变量的成员

1a（rear指向队尾元素后一位，判空判满时牺牲一个存储单元）

首先我们考虑1a的情况下在牺牲一个存储单元rear指向队尾元素后一个位置该怎么实现队列的基本操作，当rear指向队尾元素的后一位时，队列的实现需要牺牲一个存储单元来区分队列是空还是满

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10 // 定义队列中元素的最大个数

typedef struct {
    int data[MaxSize]; // 用静态数组存放队列元素
    int front, rear; // 队头指针和队尾指针
} SqQueue;

// 初始化队列
void InitQueue(SqQueue* Q) {
    Q->front = Q->rear = 0; // 初始时队头、队尾指针指向0
}

// 判断队列是否为空
bool QueueEmpty(SqQueue* Q) {
    return Q->front == Q->rear; // 判空条件：队头指针等于队尾指针
}

// 判断队列是否已满
bool QueueFull(SqQueue* Q) {
    return (Q->rear + 1) % MaxSize == Q->front; // 判满条件：队尾指针后移一位后等于队头指针
}

// 入队
bool EnQueue(SqQueue* Q, int x) {
    if (QueueFull(Q)) { // 判断队满
        return false; // 队满报错
    } else {
        Q->data[Q->rear] = x; // 新元素插入队尾
        Q->rear = (Q->rear + 1) % MaxSize; // 队尾指针后移
        return true;
    }
}

// 出队（删除一个队头元素，并用x返回）
bool DeQueue(SqQueue* Q, int* x) {
    if (QueueEmpty(Q)) { // 判断队空
        return false; // 队空则报错
    } else {
        Q->front = (Q->front + 1) % MaxSize; // 队头指针后移
        *x = Q->data[Q->front]; // 获取队头元素
        return true;
    }
}

// 获得队头元素的值，用x返回
bool GetHead(SqQueue* Q, int* x) {
    if (QueueEmpty(Q)) { // 判断队空
        return false; // 队空则报错
    } else {
        *x = Q->data[Q->front]; // 获取队头元素
        return true;
    }
}

在这个实现中，队列满的条件是队尾指针后移一位后等于队头指针。这意味着队列的实际容量是MaxSize - 1，因为一个存储单元被用来区分队列是空还是满。 

2a(rear指向队尾元素,判空判满时牺牲一个存储单元）

当rear指向队尾元素时，队列的实现不需要牺牲额外的存储单元来区分队列是空还是满。在这种情况下，队列的实际容量就是MaxSize，因为所有的存储单元都可以用来存储元素。

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10 // 定义队列中元素的最大个数

typedef struct {
    int data[MaxSize]; // 用静态数组存放队列元素
    int front, rear; // 队头指针和队尾指针
} SqQueue;

// 初始化队列
void InitQueue(SqQueue* Q) {
    // 初始时队头指针指向0
    // 队尾指针指向数组尾元素
    Q->front = 0;
    Q->rear = MaxSize - 1;
}

// 判断队列是否为空
bool QueueEmpty(SqQueue* Q) {
    if (Q->rear == Q->front) { // 判空条件
        return true;
    } else {
        return false;
    }
}

// 判断队列是否已满
bool QueueFull(SqQueue* Q) {
    if ((Q->rear + 1) % MaxSize == Q->front) { // 判满条件
        return true;
    } else {
        return false;
    }
}

// 入队
bool EnQueue(SqQueue* Q, int x) {
    if (QueueFull(Q)) { // 判断队满
        return false; // 队满报错
    } else {
        Q->rear = (Q->rear + 1) % MaxSize; // 队尾指针后移
        Q->data[Q->rear] = x; // 新元素插入队尾
        return true;
    }
}

// 出队（删除一个队头元素，并用x返回）
bool DeQueue(SqQueue* Q, int* x) {
    if (QueueEmpty(Q)) { // 判断队空
        return false; // 队空则报错
    } else {
        Q->front = (Q->front + 1) % MaxSize; // 队头指针后移
        *x = Q->data[Q->front]; // 获取队头元素
        return true;
    }
}

// 获得队头元素的值，用x返回
bool GetHead(SqQueue* Q, int* x) {
    if (QueueEmpty(Q)) { // 判断队空
        return false; // 队空则报错
    } else {
        *x = Q->data[(Q->front + 1) % MaxSize]; // 获取队头元素
        return true;
    }
}

在这个实现中，队列满的条件是队尾指针后移一位后等于队头指针。这意味着队列的实际容量是MaxSize，因为所有的存储单元都可以用来存储元素 ，与1a的相比主要改变了入队和初始化的操作，入队的时候，rear需要先往后一位，再接受新的数据。

1b（rear指向队尾元素后一位，增加size变量记录长度）

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10 // 定义队列中元素的最大个数

typedef struct {
    int data[MaxSize]; // 用静态数组存放队列元素
    int front, rear; // 队头指针和队尾指针
    int size;//增加一个size记录队列的长度
} SqQueue;

// 初始化队列
void InitQueue(SqQueue* Q) {
    // 初始时队头、队尾指针指向0
    Q->rear = Q->front = 0;
    Q->size = 0;
}

// 判断队列是否为空
bool QueueEmpty(SqQueue Q) {
    if (Q->size == 0) { // 判空条件
        return true;
    }
    else {
        return false;
    }

bool QueueFull(SqQueue Q) {
    if (Q->size==MaxSize) { // 判满条件
        return true;
    }
    else {
        return false;
    }
}

// 入队
bool EnQueue(SqQueue* Q, int x) {
    if (QueueFull(*Q)) { // 判断队满
        return false; // 队满报错
    }
    else {
        Q->data[Q->rear] = x; // 新元素插入队尾
        Q->rear = (Q->rear + 1) % MaxSize; // 队尾指针加1取模，队尾指针后移
        Q->size = Q->size + 1; // 队列长度加1
        return true;
    }
}

// 出队（删除一个队头元素，并用x返回）
bool DeQueue(SqQueue* Q, int* x) {
    if (QueueEmpty(*Q)) { // 判断队空
        return false; // 队空则报错
    }
    else {
        *x = Q->data[Q->front];
        Q->front = (Q->front + 1) % MaxSize; // 队头指针后移
        Q->size = Q->size - 1; // 队列长度减1
        return true;
    }
}
// 获得队头元素的值，用x返回
bool GetHead(SqQueue Q, int* x) {
    if (QueueEmpty(*Q)) { // 判断队空
        return false; // 队空则报错
    }
    else {
        *x = Q.data[Q.front];
        return true;
    }
}

2b(rear指向队尾元素，增加size变量记录长度)

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10 // 定义队列中元素的最大个数

typedef struct {
    int data[MaxSize]; // 用静态数组存放队列元素
    int front, rear; // 队头指针和队尾指针
    int size;//增加一个size记录队列的长度
} SqQueue;

// 初始化队列
void InitQueue(SqQueue* Q) {
    // 初始时队头、队尾指针指向
    Q->front = 0;
    Q->rear = MaxSize - 1;
    Q->size = 0;
}

// 判断队列是否为空
bool QueueEmpty(SqQueue Q) {
    if (Q->size == 0) { // 判空条件
        return true;
    }
    else {
        return false;
    }

bool QueueFull(SqQueue Q) {
    if (Q->size==MaxSize) { // 判满条件
        return true;
    }
    else {
        return false;
    }
}

// 入队
bool EnQueue(SqQueue* Q, int x) {
    if (QueueFull(*Q)) { // 判断队满
        return false; // 队满报错
    }
    else {
        Q->rear = (Q->rear + 1) % MaxSize; // 队尾指针加1取模，队尾指针后移
        Q->data[Q->rear] = x; // 新元素插入队尾
        Q->size = Q->size + 1; // 队列长度加1
        return true;
    }
}

// 出队（删除一个队头元素，并用x返回）
bool DeQueue(SqQueue* Q, int* x) {
    if (QueueEmpty(*Q)) { // 判断队空
        return false; // 队空则报错
    }
    else {
        *x = Q->data[Q->front];
        Q->front = (Q->front + 1) % MaxSize; // 队头指针后移
        Q->size = Q->size - 1; // 队列长度减1
        return true;
    }
}
// 获得队头元素的值，用x返回
bool GetHead(SqQueue Q, int* x) {
    if (QueueEmpty(*Q)) { // 判断队空
        return false; // 队空则报错
    }
    else {
        *x = Q.data[Q.front];
        return true;
    }
}

3a（rear指向队尾元素后一位，判空判满时添加一个tag标签标记）

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10 // 定义队列中元素的最大个数

typedef struct {
    int data[MaxSize]; // 用静态数组存放队列元素
    int front, rear; // 队头指针和队尾指针
    int tag;//tag标签用于标记,0=出队，1=入队
} SqQueue;

// 初始化队列
void InitQueue(SqQueue* Q) {
    Q->front = Q->rear = 0; // 初始时队头、队尾指针指向0
    Q->tag = 0;
}

// 判断队列是否为空
bool QueueEmpty(SqQueue* Q) {
    return (Q->front == Q->rear&&Q->tag==0); // 判空条件：队头指针等于队尾指针
}

// 判断队列是否已满
bool QueueFull(SqQueue* Q) {
    return ((Q->rear + 1) % MaxSize == Q->front&&Q->tag==1); // 判满条件：队尾指针后移一位后等于队头指针
}

// 入队
bool EnQueue(SqQueue* Q, int x) {
    if (QueueFull(Q)) { // 判断队满
        return false; // 队满报错
    }
    else {
        Q->data[Q->rear] = x; // 新元素插入队尾
        Q->rear = (Q->rear + 1) % MaxSize; // 队尾指针后移
        Q->tag = 1;//入队后tag变为1;
        return true;
    }
}

// 出队（删除一个队头元素，并用x返回）
bool DeQueue(SqQueue* Q, int* x) {
    if (QueueEmpty(Q)) { // 判断队空
        return false; // 队空则报错
    }
    else {
        Q->front = (Q->front + 1) % MaxSize; // 队头指针后移
        *x = Q->data[Q->front]; // 获取队头元素
        Q->tag = 1;//出队后tag变为1;
        return true;
    }
}

// 获得队头元素的值，用x返回
bool GetHead(SqQueue* Q, int* x) {
    if (QueueEmpty(Q)) { // 判断队空
        return false; // 队空则报错
    }
    else {
        *x = Q->data[Q->front]; // 获取队头元素
        return true;
    }
}

3b（rear指向队尾元素，判空判满时添加一个tag标签标记）

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10 // 定义队列中元素的最大个数

typedef struct {
    int data[MaxSize]; // 用静态数组存放队列元素
    int front, rear; // 队头指针和队尾指针
    int tag;//tag标签用于标记,0=出队，1=入队
} SqQueue;

// 初始化队列
void InitQueue(SqQueue* Q) {
    Q->front = 0//初始时队头指针指向队头元素
    Q->rear = MaxSize-1;//初始时队尾指针指向队尾元素
    Q->tag = 0;
}

// 判断队列是否为空
bool QueueEmpty(SqQueue* Q) {
    return (Q->front == Q->rear && Q->tag == 0); // 判空条件：队头指针等于队尾指针
}

// 判断队列是否已满
bool QueueFull(SqQueue* Q) {
    return ((Q->rear + 1) % MaxSize == Q->front && Q->tag == 1); // 判满条件：队尾指针后移一位后等于队头指针
}

// 入队
bool EnQueue(SqQueue* Q, int x) {
    if (QueueFull(Q)) { // 判断队满
        return false; // 队满报错
    }
    else {
        Q->rear = (Q->rear + 1) % MaxSize; // 队尾指针后移
        Q->data[Q->rear] = x; // 新元素插入队尾
        Q->tag = 1;//入队后tag变为1;
        return true;
    }
}

// 出队（删除一个队头元素，并用x返回）
bool DeQueue(SqQueue* Q, int* x) {
    if (QueueEmpty(Q)) { // 判断队空
        return false; // 队空则报错
    }
    else {
        Q->front = (Q->front + 1) % MaxSize; // 队头指针后移
        *x = Q->data[Q->front]; // 获取队头元素
        Q->tag = 1;//出队后tag变为1;
        return true;
    }
}

// 获得队头元素的值，用x返回
bool GetHead(SqQueue* Q, int* x) {
    if (QueueEmpty(Q)) { // 判断队空
        return false; // 队空则报错
    }
    else {
        *x = Q->data[Q->front]; // 获取队头元素
        return true;
    }
}


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

相关文章

班组长在预防突发事件方面应该采取哪些措施？

班组长在预防突发事件方面应该采取哪些措施？

在预防突发事件方面&#xff0c;班组长作为基层管理的关键人物&#xff0c;肩负着维护团队稳定、保障员工安全的重要职责。为了确保工作的顺利进行和团队的和谐稳定&#xff0c;班组长必须采取一系列切实有效的措施来预防潜在的风险和突发事件。以下是深圳天行健精益管理咨询公…
阅读更多...
苹果公司的Wifi定位服务(WPS)存在被滥用的风险

苹果公司的Wifi定位服务(WPS)存在被滥用的风险

安全博客 Krebs on Security 2024年5月21日发布博文&#xff0c;表示苹果公司的定位服务存在被滥用风险&#xff0c;通过 "窃取"WPS 数据库&#xff0c;可以定位部队行踪。 相关背景知识 手机定位固然主要依赖卫星定位&#xff0c;不过在城市地区&#xff0c;密集的…
阅读更多...
查看视频时间基 time_base

查看视频时间基 time_base

时间基、codec, 分辨率&#xff0c;音频和视频的都一样&#xff0c;才可以直接使用ffmpeg -f concat -i file.txt 方式合并。 On Thu, Dec 03, 2015 at 21:54:53 0200, redneb8888 wrote: I am looking for a way to find the time base of a stream (video or audio), $ ffpr…
阅读更多...
GraalVM

GraalVM

文章目录 1、什么是GraalVM2、GraalVM的两种模式1_JIT模式2_AOT模式3_总结 3、应用场景1_SpringBoot搭建GraalVM应用2_函数计算3_Serverless应用 4、参数优化和故障诊断1_内存快照文件的获取2_运行时数据的获取 1、什么是GraalVM GraalVM是Oracle官方推出的一款高性能JDK&…
阅读更多...
精确计算应用的冷启动耗时

精确计算应用的冷启动耗时

在iOS项目中&#xff0c;冷启动时间是指从用户点击应用图标开始&#xff0c;到应用完全加载并呈现出第一个界面&#xff08;可能需要网络请求必要的数据&#xff09;所花费的时间。这里以 main 函数为界&#xff0c;分为两个时间段&#xff1a; 从用户点击应用图标 ~ invoke m…
阅读更多...
k8s离线安装单节点elasticsearch7.x

k8s离线安装单节点elasticsearch7.x

目录 概述资源实践脚本 概述 k8s离线安装单节点elasticsearch7.x 资源 镜像可以自己准备&#xff0c;懒人速递 elasticsearch离线安装镜像-版本7.17.22 实践 脚本 # pvc apiVersion: v1 kind: PersistentVolumeClaim metadata:name: es-nfsnamespace: defaultlabels:pvc: …
阅读更多...
fastadmin 如何给页面添加水印

fastadmin 如何给页面添加水印

偶然发现fastadmin框架有个水印插件&#xff0c;看起来漂亮&#xff0c;就想也实现这样的功能&#xff0c;看到需要费用。但是现成的插件需要费用&#xff0c;自己动手丰衣足食。说干就干。 1. 找到watermark.js &#xff0c;放到assets/js/ 下面 2.具体页面引入 <script…
阅读更多...
Vuetify3：文章显示html标签

Vuetify3：文章显示html标签

在Vuetify 3中&#xff0c;如果你想要显示一个包含HTML标签的文章&#xff0c;你可以使用v-html指令来渲染这些标签。这个指令会将绑定的HTML内容渲染到模板中&#xff0c;但要注意&#xff0c;由于直接渲染HTML可能会有XSS攻击的风险&#xff0c;因此只在可靠内容上使用v-html…
阅读更多...
最新文章

Copyright @ 2022~2023