PTA（栈和队列）1-6 循环队列入队出队

1-6 循环队列入队出队

分数 4

作者 张瑞霞

单位 桂林电子科技大学

本题要求实现队列的顺序存储表示，包括入队、出队和取队头操作

函数接口定义：

1
2
3
void EnQueue_seq(SeqQueue squeue, DataType x)  ;
void DeQueue_seq(SeqQueue squeue)  ;
DataType FrontQueue_seq(SeqQueue squeue) ;

其中，squeue 是操作的队列，x是入队的元素

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>
#include <stdlib.h>
typedef char DataType;
struct Queue
{
    int Max;  
    int f;   
    int r;  
    DataType *elem; 
};
typedef struct Queue *SeqQueue;

SeqQueue SetNullQueue_seq(int m) 
{
    SeqQueue squeue;
    squeue = (SeqQueue)malloc(sizeof(struct Queue));
    if (squeue == NULL)
    {
        printf("Alloc failure\n");
        return NULL;
    }
    squeue->elem = (char*)malloc(sizeof(DataType)*m);
    if (squeue->elem != NULL)
    {
        squeue->Max = m;
        squeue->f = 0;
        squeue->r = 0;
        return squeue;
    }
}

int IsNullQueue_seq(SeqQueue squeue) 
{
    return (squeue->f == squeue->r);
}
void EnQueue_seq(SeqQueue squeue, DataType x)  
{
    @@
}
void DeQueue_seq(SeqQueue squeue)  
{
    @@
}
DataType FrontQueue_seq(SeqQueue squeue) 
{
    @@
}

int main()
{
    char ch;
    SeqQueue queueA = SetNullQueue_seq(5);
    ch = getchar();
    while (ch != '#')
    {
        EnQueue_seq(queueA, ch);
        ch = getchar();
    }
    DeQueue_seq(queueA);
    printf("%c" ,FrontQueue_seq(queueA));
    return 0;
}

输入样例：

1
ABCD#

输出样例：

1
B

输入样例：

1
A#

输出样例：

1
It is empty queue!

输入样例：

1
ABCDEF#

输出样例：

1
It is FULL Queue!It is FULL Queue!B

要记住循环队列是先放入尾指针的地方，尾指针再++，出循环队列是头指针++

image-20251024210007088

image-20251024210023828

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 入队：应该是入队尾
void EnQueue_seq(SeqQueue squeue, DataType x)
{
    if ((squeue->r + 1 + squeue->Max) % squeue->Max == squeue->f) { // 循环队列满了
        printf("It is FULL Queue!");
        return;
    }
    squeue->elem[squeue->r] = x; // 插入x
    squeue->r = (squeue->r + 1) % squeue->Max; // 移到下一个位置
}

// 出队：从对头出队，f前移
void DeQueue_seq(SeqQueue squeue)
{
    if (squeue->f == squeue->r) { // 循环队列为空
        return;
    }
    squeue->f = (squeue->f + 1) % squeue->Max;
}

// 取队头
DataType FrontQueue_seq(SeqQueue squeue)
{
    if (squeue->f == squeue->r) {
        printf("It is empty queue!");
        return 0;
    }
    return squeue->elem[squeue->f];
}