第1关:循环队列
任务描述
本关任务:编写一个循环队列,实现入队、出队操作,判断队空、队满等特殊情况。
相关知识
为了完成本关任务,你需要掌握:1.循环队列定义,2.入队、出队的定义,3.队空、队满的情况。
循环队列定义
循环队列将数组存储区看成是一个首尾相接的环形区域(下图)。当数据存放到尾地址后,下一个地址就跳转到首地址。循环队列定义如下:
struct Queue{
int maxSize; // 队列最大长度
int *data; // 数据指针
int front; // 头指针索引
int rear; // 尾指针索引
};
入队出队定义
入队操作:队列未满,在队尾插入一个元素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
编程要求
本关的编程任务是补全右侧代码片段isFull
、isEmpty
、enQueue
和deQueue
中Begin
至End
中间的代码,具体要求如下:
- 在
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
开始你的任务吧,祝你成功!文章来源地址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.队空的情况。
链队列定义
链队列的定义是在单链表的基础上,增加一个尾指针。队列的特点是“先进先出”,因此只需要一头一尾两个指针,就可以快速地在队头取出数据,在队尾插入数据。
链队列动态创建节点,不需要预设大小,内存空间不需要连续,入队、出队更容易实现。但是存取速度慢,操作也比数组的方式更加复杂。
struct Node // 数据节点
{
int data; // 数据类型
Node *next; // 指向下一个节点的指针
};
struct LinkQueue // 链表队列
{
Node *front; // 头指针
Node *rear; // 尾指针
};
入队出队定义
入队操作:
- 第一步:为待入队元素创建数据节点
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
。
编程要求
本关的编程任务是补全右侧代码片段isEmpty
、enQueue
和deQueue
中Begin
至End
中间的代码,具体要求如下:
- 在
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
,不设头指针。队尾添加数据的时候,只需要在rear
和rear->next
之间插入该数据节点,然后将rear
指向这个节点。因为没有头指针,所以添加一个整形变量size_
来判定队列空的情况。
struct Node // 数据节点
{
int data; // 数据类型
Node *next; // 指向下一个节点的指针
};
struct CycleQueue // 循环链表队列
{
int size_; // 目前队列元素个数
Node *rear; // 尾指针
};
入队出队定义
注意初始队列时,尾指针rear = NULL
以及rear->next = NULL
。
入队操作:
- 为待入队元素创建数据节点
Node* node
; - 如果队列为空,则尾节点指向新节点
rear = node
,rear->next
指向队首节点rear->next = node
。 - 如果队列非空,则在
rear
和rear->next
之间插入新节点:Node *temp = rear->next;
rear->next = node;
node->next = temp;
rear = node;
rear->next = temp;
出队操作:队列不空,返回队首元素值。
- 第一步:获取队首节点
Node *node = rear->next
; - 第二步:移除队首节点,修改
rear->next = node->next
。
队空情况
队列中不含数据节点,通过变量size_
来判定队列空的情况。
编程要求
本关的编程任务是补全右侧代码片段isEmpty
、enQueue
和deQueue
中Begin
至End
中间的代码,具体要求如下:
- 在
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模板网!