6-1 循环队列操作集

时间:2021-05-07作者:klpeng分类:IT综合浏览:884评论:0

目录

1.题目:

2.题解:


1.题目:

本题要求实现循环队列操作集。

函数接口定义:

在这里描述函数接口。例如:

#define MAXSIZE 10

typedef struct _queue
{
    int front;//队头指针
    int rear;//队尾指针
    int *data;//指向数据区
}queue;

//创建一个空队列
queue* createQueue();
//入队
void enQueue(queue* q, int x);
//判断队列是否已满
bool isFull(queue* q);
//出队
void deQueue(queue* q);
//得到队头元素的值
int front(queue* q);
//判断队列是否为空
bool isEmpty(queue* q);
//返回队列长度
int size(queue* q);
//销毁队列
void destroyQueue(queue* q);
//从0号位置开始输出数据区的所有元素。无效位置输出'X'
void show(queue* q);

裁判测试程序样例:

在这里给出函数被调用进行测试的例子。例如:
/*循环队列*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAXSIZE 10

typedef struct _queue
{
    int front;//队头指针
    int rear;//队尾指针
    int *data;//指向数据区
}queue;

//创建一个空队列
queue* createQueue();
//入队
void enQueue(queue* q, int x);
//判断队列是否已满
bool isFull(queue* q);
//出队
void deQueue(queue* q);
//得到队头元素的值
int front(queue* q);
//判断队列是否为空
bool isEmpty(queue* q);
//返回队列长度
int size(queue* q);
//销毁队列
void destroyQueue(queue* q);
//从0号位置开始输出数据区的所有元素。无效位置输出'X'
void show(queue* q);

int main(void)
{
    char cmd[20];
    queue *pQueue = createQueue();
    int x;
    scanf("%s", cmd);
    while (strcmp(cmd, "END") != 0)
    {
        if (strcmp(cmd, "ENQUEUE") == 0)
        {
            if (isFull(pQueue) == true)
            {
                printf("FULL\n");
            }
            else
            {
                scanf("%d", &x);
                enQueue(pQueue, x);
            }
        }
        if (strcmp(cmd, "DEQUEUE") == 0)
        {
            if (isEmpty(pQueue) == true)
            {
                printf("EMPTY\n");
            }
            else
            {
                deQueue(pQueue);
            }
        }
        if (strcmp(cmd, "GETFRONT") == 0)
        {
            x = front(pQueue);
            printf("%d\n", x);
        }
        if (strcmp(cmd, "SIZE") == 0)
        {
            printf("SIZE = %d\n", size(pQueue));
        }
        if (strcmp(cmd, "SHOW") == 0)
        {
            show(pQueue);
        }
        scanf("%s", cmd);
    }
    destroyQueue(pQueue);
    return 0;
}

//从0号位置开始输出数据区的所有元素。无效位置输出'X'
void show(queue* q)
{
    if (q->front == q->rear)
        return;
    if (q->front < q->rear)
    {
        for (int i = 0; i < q->front; i++)
        {
            printf("X ");
        }
        for (int i = q->front; i < q->rear; i++)
        {
            printf("%d ", q->data[i]);
        }
        for (int i = q->rear; i < MAXSIZE; i++)
        {
            printf("X ");
        }
    }
    else
    {
        for (int i = 0; i < q->rear; i++)
        {
            printf("%d ", q->data[i]);
        }
        for (int i = q->rear; i < q->front; i++)
        {
            printf("X ");
        }
        for (int i = q->front; i < MAXSIZE; i++)
        {
            printf("%d ", q->data[i]);
        }
    }
    printf("\n");
}
/* 请在这里填写答案 */

输入样例:

在这里给出一组输入。例如:

DEQUEUE
ENQUEUE 1
ENQUEUE 2
ENQUEUE 3
SHOW
GETFRONT
SIZE
ENQUEUE 4
ENQUEUE 5
ENQUEUE 6
ENQUEUE 7
ENQUEUE 8
ENQUEUE 9
ENQUEUE 10
ENQUEUE 11
SHOW
GETFRONT
SIZE
DEQUEUE
DEQUEUE
DEQUEUE
SHOW
GETFRONT
SIZE
ENQUEUE 12
ENQUEUE 13
SHOW
GETFRONT
SIZE
END

输出样例:

在这里给出相应的输出。例如:

EMPTY
1 2 3 X X X X X X X 
1
SIZE = 3
FULL
FULL
1 2 3 4 5 6 7 8 9 X 
1
SIZE = 9
X X X 4 5 6 7 8 9 X 
4
SIZE = 6
13 X X 4 5 6 7 8 9 12 
4
SIZE = 8

2.题解:

 题目看起来很长,其实不难,由主函数可知,入队,出队中判满,判空是额外有新的函数来处理的,并且出队也没有本质上改变数组元素的组成,只是修改了出队指针而已。就是认真看题,基本能够做。

其中队列为空时:q->front == q->rear;

队列为满时:(q->rear+1)%MAXSIZE  == q->front;

求队列长度:  ((q->rear-q->front)+MAXSIZE)%MAXSIZE  。之所以要加一个MAXSIZE是因为q->rear-q->front可能是负数。


//创建一个空队列
queue* createQueue()
{
	queue * q;
	q = (queue*)malloc(sizeof(queue));
	q->data = (queue*)malloc(sizeof(int)*MAXSIZE);
	q->front=0;
	q->rear = 0;
	return q;
}
//入队
void enQueue(queue* q, int x)
{
	
	q->data[q->rear] = x;
	q->rear=(q->rear+1)%MAXSIZE;
	
}
//判断队列是否已满
bool isFull(queue* q)
{
	return (q->rear+1)%MAXSIZE==q->front;
}
//出队
void deQueue(queue* q)
{
	q->front=(q->front+1)%MAXSIZE;
	
}
//得到队头元素的值
int front(queue* q)
{
	return q->data[q->front];
}
//判断队列是否为空
bool isEmpty(queue* q)
{
	return q->front==q->rear;
	
	
}
//返回队列长度
int size(queue* q)
{
	return ((q->rear-q->front)+MAXSIZE)%MAXSIZE;
}
//销毁队列
void destroyQueue(queue* q)
{
	free(q);
	q->front=0;
	q->rear=0;
}

 

打赏
文章版权声明:除非注明,否则均为彭超的博客原创文章,转载或复制请以超链接形式并注明出处。
相关推荐

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

猜你喜欢