【头歌】数据结构-队列的应用

这篇具有很好参考价值的文章主要介绍了【头歌】数据结构-队列的应用。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 第1关:循环队列

任务描述

本关任务:编写一个循环队列,实现入队、出队操作,判断队空、队满等特殊情况。

相关知识

为了完成本关任务,你需要掌握:1.循环队列定义,2.入队、出队的定义,3.队空、队满的情况。

循环队列定义

循环队列将数组存储区看成是一个首尾相接的环形区域(下图)。当数据存放到尾地址后,下一个地址就跳转到首地址。循环队列定义如下:

 
  1. struct Queue{
  2. int maxSize; // 队列最大长度
  3. int *data; // 数据指针
  4. int front; // 头指针索引
  5. int rear; // 尾指针索引
  6. };

头歌数据结构,数据结构,算法,c语言

入队出队定义

入队操作:队列未满,在队尾插入一个元素item,使得data[rear+1]=item,若超过存储空间则尾指针索引取模(rear+1)%maxSize

出队操作:队列不空,返回队首元素值data[front],并移除队首元素front+1,若超过存储空间则头指针索引取模(front+1)%maxSize

队空队满情况

初始化创建空队时,令front=rear=0, 其中front指向队首元素,rear指向队尾元素的下一个元素:

  • 当队空时:front==rear
  • 当队满时:front==rear 亦成立

因此只凭等式front==rear无法判断队空还是队满。 一个方法是少用一个元素空间,约定:队列头指针front在队尾指针rear的下一个位置上作为队列“满”状态的标志(如上图),即:

  • 队空时: front==rear
  • 队满时: (rear+1)%maxSize==front

编程要求

本关的编程任务是补全右侧代码片段isFullisEmptyenQueuedeQueueBeginEnd中间的代码,具体要求如下:

  • isFull中,判断队列是否为满,若满返回true并在一行打印The queue is Full,否则返回false
  • isEmpty中,判断队列是否为空,若空返回true并在一行打印The queue is Empty,否则返回false
  • enQueue中,实现入队操作:将元素item加入队列尾部;
  • deQueue中,实现出队操作:移除队列首部元素,并返回元素值。

测试说明

平台将自动编译补全后的代码,并生成若干组测试数据,接着根据程序的输出判断程序是否正确。

以下是平台的测试样例:

测试输入: 10 7 enqueue 30 enqueue 98 dequeue enqueue 96 dequeue dequeue enqueue 0 预期输出: 0 The queue is Empty

输入说明: 第一行n m分别表示循环队列大小、入队出队操作记录数量。 接下来m行,enqueue表示入队操作,后面接待入队元素;dequeue表示出队操作。

输出说明: 输出m个操作之后的所有队列元素。


开始你的任务吧,祝你成功!文章来源地址https://www.toymoban.com/news/detail-715482.html

 

//
//  queue_.cpp
//  Queue
//
//  Created by ljpc on 2018/5/29.
//  Copyright © 2018年 ljpc. All rights reserved.
//

#include "queue_.h"


void creatQueue(Queue* que, int maxSize)
//  创建一个循环队列指针que,队列最大长度为maxSize
{
    que->maxSize = maxSize;
    que->data = (int*)malloc(maxSize * sizeof(int));
    que->front = que->rear = 0;
}

void destroyQueue(Queue* que)
//  释放队列内存空间
{
    free(que->data);
}

bool isFull(Queue* que)
//  判断队列que是否为满
//  若满返回 true 并在一行打印  The queue is Full 末尾换行!!!
//  否则返回 false

{
    // 请在这里补充代码,完成本关任务
    /********** Begin *********/
    if((que->rear+1)%que->maxSize==que->front)
    {
        printf("The queue is Full\n");
        return true;
    }
    else return false;
    /********** End **********/
}

bool isEmpty(Queue* que)
//  判断队列que是否为空
//  若空返回 true 并在一行打印 The queue is Empty 末尾换行!!!
//  否则返回 false
{
    // 请在这里补充代码,完成本关任务
    /********** Begin *********/
    if(que->rear==que->front)
    {
        printf("The queue is Empty\n");
        return true;
    }   
    else 
    return false;

    /********** End **********/
}

int enQueue(Queue* que, int item)
//  实现入队操作:将元素item加入队列que尾部
//  若队列没满,编写加入操作,返回 1
//  若队列满了,不做任何操作,返回 -1
{
    // 请在这里补充代码,完成本关任务
    /********** Begin *********/
    
    if(isFull(que))
    {
        return -1;
    }
    else 
    {
        que->data[que->rear]=item;
        que->rear=(que->rear+1)%que->maxSize;
        return 1;
    }
    /********** End **********/
}

int deQueue(Queue* que)
//  实现出队操作:移除队列que首部元素,并返回元素值
{
    // 请在这里补充代码,完成本关任务
    /********** Begin *********/
    int x;
    if(que->front==que->rear)
    {
        return false;
    }
    else 
    {
        x=que->data[que->front];
        que->front=(que->front+1)%que->maxSize;        
    }
    return x;

    /********** End **********/
}

void printQueue(Queue* que)
//  打印队列
{
    while (isEmpty(que)==false) {
        int item = deQueue(que);
        printf("%d ", item);
    }
}

 第二关-链队列

任务描述

本关任务:编写一个链队列,实现入队、出队操作,判断队空等特殊情况。

相关知识

为了完成本关任务,你需要掌握:1.链队列定义,2.入队、出队的定义,3.队空的情况。

链队列定义

链队列的定义是在单链表的基础上,增加一个尾指针。队列的特点是“先进先出”,因此只需要一头一尾两个指针,就可以快速地在队头取出数据,在队尾插入数据。

链队列动态创建节点,不需要预设大小,内存空间不需要连续,入队、出队更容易实现。但是存取速度慢,操作也比数组的方式更加复杂。

 
  1. struct Node // 数据节点
  2. {
  3. int data; // 数据类型
  4. Node *next; // 指向下一个节点的指针
  5. };
  6. struct LinkQueue // 链表队列
  7. {
  8. Node *front; // 头指针
  9. Node *rear; // 尾指针
  10. };

头歌数据结构,数据结构,算法,c语言

入队出队定义

入队操作:

  • 第一步:为待入队元素创建数据节点Node* node
  • 第二步:将队尾节点next指向新节点rear->next = node;
  • 第三步:修改队尾指针rear指向新节点rear = node

出队操作:队列不空,返回队首元素值。

  • 第一步:获取队首节点Node *node = front->next,注意front->next才是指向队列头节点,front本身不具备任何意义。
  • 第二步:移除队首节点,修改front->next = node->next
  • 特殊情况:当队列最后一个元素被删除后,队列尾指针也丢失了,因此需对队尾指针重新赋值,即指向头结点 rear = front

队空情况

初始化创建空队时,令rear = front,即队空的情况是rear == front

编程要求

本关的编程任务是补全右侧代码片段isEmptyenQueuedeQueueBeginEnd中间的代码,具体要求如下:

  • isEmpty中,判断队列是否为空,若空返回true并在一行打印The queue is Empty,否则返回false
  • enQueue中,实现入队操作:将元素item加入队列尾部;
  • deQueue中,实现出队操作:移除队列首部元素,并返回元素值。

测试说明

平台将自动编译补全后的代码,并生成若干组测试数据,接着根据程序的输出判断程序是否正确。

以下是平台的测试样例:

测试输入: 7 enqueue 30 enqueue 98 dequeue enqueue 96 dequeue dequeue enqueue 0 预期输出: 0 The queue is Empty

输入说明: 第一行m分别表示链队列入队出队操作记录数量。 接下来m行,enqueue表示入队操作,后面接待入队元素;dequeue表示出队操作。

输出说明: 输出m个操作之后的所有队列元素。


开始你的任务吧,祝你成功!

//
//  queue_.cpp
//  LinkQueue
//
//  Created by ljpc on 2018/5/30.
//  Copyright © 2018年 ljpc. All rights reserved.
//

#include "queue_.h"

void creatLinkQueue(LinkQueue* que)
//  创建一个循环队列指针que
{
    que->front = (Node*)malloc(sizeof(Node));
    que->rear = que->front;
    que->rear->next = NULL;
}

bool isEmpty(LinkQueue* que)
//  判断队列que是否为空
//  若空返回 true 并在一行打印 The queue is Empty 末尾换行!!!
//  否则返回 false
{
    // 请在这里补充代码,完成本关任务
    /********** Begin *********/
    if(que->front==que->rear)
    {
        printf("The queue is Empty\n");
        return true;
    }
    else 
    return false;

    /********** End **********/
}

void enQueue(LinkQueue* que, int item)
//  实现入队操作:将元素item加入队列que尾部
{
    // 请在这里补充代码,完成本关任务
    /********** Begin *********/
    Node *newque=(Node*)malloc(sizeof(Node));
    if(newque!=NULL)
    {
        newque->data=item;
        newque->next=NULL;
        que->rear->next=newque;
        que->rear=newque;
    }
    /********** End **********/
}

int deQueue(LinkQueue* que)
//  实现出队操作:移除队列que首部元素,并返回元素值
{
    // 请在这里补充代码,完成本关任务
    /********** Begin *********/
    Node *p;
    int item;
    if(que->front==que->rear)
       return false;

    p=que->front->next;
    que->front->next=p->next;
    item=p->data;

    if(que->rear==p)
    {
        que->rear=que->front;
    }
    free(p);
    return item;
    /********** End **********/
}

void printQueue(LinkQueue* que)
//  打印队列
{
    while (isEmpty(que)==false) {
        int item = deQueue(que);
        printf("%d ", item);
    }
}

第3关:单链表循环队列

任务描述

本关任务:编写一个单链表循环队列,实现入队、出队操作,判断队空等特殊情况。

相关知识

为了完成本关任务,你需要掌握:1.单链表循环队列定义,2.入队、出队的定义,3.队空的情况。

单链表循环队列

单链表循环队列设一个尾指针rear,不设头指针。队尾添加数据的时候,只需要在rearrear->next之间插入该数据节点,然后将rear指向这个节点。因为没有头指针,所以添加一个整形变量size_来判定队列空的情况。

头歌数据结构,数据结构,算法,c语言

 
  1. struct Node // 数据节点
  2. {
  3. int data; // 数据类型
  4. Node *next; // 指向下一个节点的指针
  5. };
  6. struct CycleQueue // 循环链表队列
  7. {
  8. int size_; // 目前队列元素个数
  9. Node *rear; // 尾指针
  10. };

入队出队定义

注意初始队列时,尾指针rear = NULL以及rear->next = NULL

入队操作:

头歌数据结构,数据结构,算法,c语言

  • 为待入队元素创建数据节点Node* node
  • 如果队列为空,则尾节点指向新节点rear = noderear->next指向队首节点rear->next = node
  • 如果队列非空,则在rearrear->next之间插入新节点:
     
      
    1. Node *temp = rear->next;
    2. rear->next = node;
    3. node->next = temp;
    4. rear = node;
    5. rear->next = temp;

出队操作:队列不空,返回队首元素值。

头歌数据结构,数据结构,算法,c语言

  • 第一步:获取队首节点Node *node = rear->next;
  • 第二步:移除队首节点,修改rear->next = node->next

队空情况

队列中不含数据节点,通过变量size_来判定队列空的情况。

编程要求

本关的编程任务是补全右侧代码片段isEmptyenQueuedeQueueBeginEnd中间的代码,具体要求如下:

  • isEmpty中,判断队列是否为空,若空返回true并在一行打印The queue is Empty,否则返回false
  • enQueue中,实现入队操作:将元素item加入队列尾部;
  • deQueue中,实现出队操作:移除队列首部元素,并返回元素值。

测试说明

平台将自动编译补全后的代码,并生成若干组测试数据,接着根据程序的输出判断程序是否正确。

以下是平台的测试样例:

测试输入: 7 enqueue 30 enqueue 98 dequeue enqueue 96 dequeue dequeue enqueue 0 预期输出: 0 The queue is Empty

输入说明: 第一行m分别表示链队列入队出队操作记录数量。 接下来m行,enqueue表示入队操作,后面接待入队元素;dequeue表示出队操作。

输出说明: 输出m个操作之后的所有队列元素。


开始你的任务吧,祝你成功!

//
//  queue_.cpp
//  Cycle
//
//  Created by ljpc on 2018/5/30.
//  Copyright © 2018年 ljpc. All rights reserved.
//

#include "queue_.h"


void creatCycleQueue(CycleQueue* que)
//  创建一个循环队列指针que
{
    que->size_ = 0;
    que->rear = NULL;
}

bool isEmpty(CycleQueue* que)
//  判断队列que是否为空
//  若空返回 true 并在一行打印 The queue is Empty 末尾换行!!!
//  否则返回 false
{
    // 请在这里补充代码,完成本关任务
    /********** Begin *********/
    if(que->size_==0){
    	printf("The queue is Empty\n");
    	return true;
	}else{
		return false;
	}

    /********** End **********/

}

void enQueue(CycleQueue* que, int item)
//  实现入队操作:将元素item加入队列que尾部
{
    // 请在这里补充代码,完成本关任务
    /********** Begin *********/
    Node *newque=(Node*)malloc(sizeof(Node));
    newque->data=item;
    if(que->size_>0)
    {
        newque->next=que->rear->next;
        que->rear->next=newque;
        que->rear=newque;
        que->size_++;
    }
    else
    {
        que->rear=newque;
        que->rear->next=newque;
        que->size_++;
    }

    /********** End **********/

}

int deQueue(CycleQueue* que)
//  实现出队操作:移除队列que首部元素,并返回元素值
{
    // 请在这里补充代码,完成本关任务
    /********** Begin *********/
    Node *p;
    int item;
    if(isEmpty(que))
        return false;
    if(que->size_==1)
    {
    	item=que->rear->data;
        p=que->rear;
	    que->rear=NULL;
	    free(p);
    } 
    else if(que->size_>1)   
    {
        p=que->rear->next;
        que->rear->next=p->next;
        item=p->data;
        free(p);
    }
    que->size_--;
    return item;
    /********** End **********/

}

void printQueue(CycleQueue* que)
//  打印队列
{
    while (isEmpty(que)==false) {
        int item = deQueue(que);
        printf("%d ", item);
    }
}

到了这里,关于【头歌】数据结构-队列的应用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 头歌(C语言)-数据结构与算法-栈的实现-第1关:实现一个顺序存储的栈

    任务描述 相关知识 栈的基本概念 栈结构的定义(C) 顺序栈的操作 编程要求 测试说明 任务描述 本关任务是实现 step1/SeqStack.cpp 中的 SS_IsFull 、 SS_IsEmpty 、 SS_Length 、 SS_Push 和 SS_Pop 五个操作函数,以实现判断栈是否为满、是否为空、求栈元素个数、进栈和出栈等功能。 相关

    2024年02月07日
    浏览(64)
  • 【算法与数据结构】 C语言实现单链表队列详解

    前面我们学习了队列的顺序表的实现,本节将用单链表实现队列。 队列也可以数组和链表的结构实现, 使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低 。下面我们先复习一下队列的基本概念: 队列:只允许在一端进行插入

    2024年04月11日
    浏览(59)
  • Java 数据结构之栈、队列(头歌平台,详细注释)

    目录 第1关:实现基于数组的 任务描述 相关知识 栈 栈的数组表示 Java 泛型简介 泛型方法 泛型类应用场景示例 代码:  第2关:实现基于链表的栈 任务描述 相关知识 栈的链式存储 入栈 出栈 代码:  第3关:基于数组的队列 任务描述 相关知识 队列 队列的数组实现 循环队列

    2024年04月25日
    浏览(44)
  • 【C/C++数据结构与算法】C语言栈与队列

    目录 一、栈 二、队列 三、循环队列 特性: 顺序存储,后进先出 优点是可随机访问,尾部增删效率高 缺点是可能会浪费空间,不知道头部增删 特性: 链式存储,先进先出 优点是无空间浪费,头部增删效率高 缺点是不能随机访问,尾部增删效率低 特性: 顺序存储,先进先

    2024年02月09日
    浏览(62)
  • C++数据结构与算法详解:链表、栈、队列、树、二叉树和图结构的实现与应用

    链表是一种常见的数据结构由一系列节点按顺序连接而成,一般每个节点包含一个数据元素和一个指向下一个节点的引用。 链表有多种类型: 单向链表:每个节点只有一个指向下一个节点的引用 双向链表:每个节点有一个指向前一个节点和一个指向后一个节点的引用 循环链

    2024年02月04日
    浏览(51)
  • 【数据结构与算法分析】使用C语言实现队列的两种(带头结点与不带头结点)链式存储,并且给出一种循环队列的设计思想

      当我们编写程序时,经常需要处理各种数据结构。队列是一种常见的数据结构,它有着广泛的应用场景。队列的基本操作包括入队和出队,应用于模拟等待队列、消息队列、计算机缓存等场合。   在实际编程中,我们可以用不同的数据结构来实现队列。本文主要介绍了

    2024年02月08日
    浏览(118)
  • 《数据结构、算法与应用C++语言描述》-列车车厢重排问题

    完整可编译运行代码见:Github::Data-Structures-Algorithms-and-Applications/_10Train_carriages_rearrangement/ 一列货运列车有 n 节车厢,每节车厢要停靠在不同的车站。假设 n个车站从 1 到n 编号,而且货运列车按照从n到1的顺序经过车站。车厢的编号与它们要停靠的车站编号相同。为了便于从

    2024年04月10日
    浏览(66)
  • 数据结构与算法-头歌【1】顺序线性表--课上练

      本意是整理和复习,理解不深或者有错误的评论区提出即可。 只有第一关的代码里面有结构体的定义,其余我只放了功能函数。 任务描述 本关要求按照完成顺序表数据类型定义,并初始化一个顺序线性表。 编程要求 顺序线性表数据结构定义如下: 本关的编程任务是补全

    2023年04月25日
    浏览(44)
  • 头歌数据结构实训参考---十大经典排序算法

    可通过 目录 快速查阅对应排序算法

    2024年02月04日
    浏览(63)
  • 头歌数据结构实训参考---二叉树及其应用

    第1关 实现二叉树的创建 第2关 计算二叉树的深度和节点个数 第3关 递归实现二叉树左右子树交换 第4关 非递归实现二叉树左右子树交换 第5关 层次遍历二叉树

    2024年02月05日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包