循环队列的操作与实现(c语言)_字符循环队列的表示和实现

什么是循环队列

       循环队列就是给定队列的范围，在原有队列的基础上，只要队列的后方满了，就从这个队列的前面开始进行插入，从而达到循环使用队列，由于循环队列本身跟平常的顺序一样，但是其设计思维像一个环，所以经常用一个环图来表示循环队列。

循环队列如下图所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HlbeQ7rK-1670504084833)(C:\Users\LENOVO\Desktop\屏幕截图 2022-12-08 140831.png)]

循环队列出现的原因

对于队列来说，循环队列出现的原因那是因为顺序队列的假溢出。对于假溢出来说，可以用两个图来解释：

        尾指针会随着不断的入队移动到我们可以进行队列操作的范围之外，而前面的存储空间并没有存入任何数据，但队列却出现了溢出的现象,而我们把这种现象称为"假溢出"。

循环队列的结构定义

       data表示的是数据域，front和rear指的是队首我队尾。front指针实在出队的时候才会移动，而rear指针则是在入队的时候才会移动。

typedef struct S_queues{
    ElemType data[MAXSIZE];
    int front;
    int rear;
}S_queues,*Queues;
1
2
3
4
5

循环队列初始化

Queues Init_Queues(){
     Queues q;
      q=(Queues) malloc(sizeof(S_queues));
    q->front=q->rear=0;
    return q;
}
1
2
3
4
5
6

入队操作

       对于入队操作，首先要解决的就是怎么来判断堆满的问题，要是想要来判断，而判断的条件则是队尾+1在除最大值是否等于队首。

判断的条件还是由图像来解释显得更加的形象，如图所示：

​ 判断式否队满，需要空出最后一个位置10不用于储存，因为(rear+1)/MAXSIZE，队尾指针加1的情况下如果能满足等于队首指针，等于则队满，如果不等的话，则说明队首指针前进过，可以重新插入数据到前面。

status push(Queues queues,ElemType e){
    if((queues->rear+1)%MAXSIZE==queues->front){
        printf("队列已满");
        return ERROR;
    }
    queues->rear=(queues->rear+1)%MAXSIZE;
    queues->data[queues->rear]=e;
    return OK;
}
1
2
3
4
5
6
7
8
9

连续入队操作

Queues M_Insert(Queues queues){
    int  x;
    if(queues==NULL){
        return ERROR;
    }
    while (scanf("%d",&x)!=EOF){
        if((queues->rear+1)%MAXSIZE==queues->front){
            printf("对列已满");
            return ERROR;
        }
        queues->rear=(queues->rear+1)%MAXSIZE;
        queues->data[queues->rear]=x;
    }
    return queues;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

出队操作

出队操作和入队操作的其原理式一样的，只不过队列是先入先出，所以，出队的操作是对队首进行操作。

status pop(Queues queues){
    if((queues->front+1)%MAXSIZE==queues->rear){
        printf("队列为空");
        return ERROR;
    }
    queues->front=(queues->front+1)%MAXSIZE;
    return OK;
}
1
2
3
4
5
6
7
8

打印队列

void  Print_Queues(Queues queues){
    if(queues==NULL){
        exit(ERROR);
    }
    int x=queues->front;
    while (x!=queues->rear){
        x=(x+1)%MAXSIZE;
        printf("%d\n",queues->data[x]);
    }
}
1
2
3
4
5
6
7
8
9
10

完整代码

#include "stdlib.h"
#include "stdio.h"
#define OK 1
#define ERROR 0
#define MAXSIZE 100
typedef int status;
typedef int ElemType;
typedef struct S_queues{
    ElemType data[MAXSIZE];
    int front;
    int rear;
}S_queues,*Queues;
///初始化队列
Queues Init_Queues(){
     Queues q;
      q=(Queues) malloc(sizeof(S_queues));
    q->front=q->rear=0;
    return q;
}
///连续插入
Queues M_Insert(Queues queues){
    int  x;
    if(queues==NULL){
        return ERROR;
    }
    while (scanf("%d",&x)!=EOF){
        if((queues->rear+1)%MAXSIZE==queues->front){
            printf("对列已满");
            return ERROR;
        }
        queues->rear=(queues->rear+1)%MAXSIZE;
        queues->data[queues->rear]=x;
    }
    return queues;
}
///入队
status push(Queues queues,ElemType e){
    if((queues->rear+1)%MAXSIZE==queues->front){
        printf("队列已满");
        return ERROR;
    }
    queues->rear=(queues->rear+1)%MAXSIZE;
    queues->data[queues->rear]=e;
    return OK;
}
///出队
status pop(Queues queues){
    if((queues->front+1)%MAXSIZE==queues->rear){
        printf("队列为空");
        return ERROR;
    }
    queues->front=(queues->front+1)%MAXSIZE;
    return OK;
}
///遍历打印
void  Print_Queues(Queues queues){
    if(queues==NULL){
        exit(ERROR);
    }
    int x=queues->front;
    while (x!=queues->rear){
        x=(x+1)%MAXSIZE;
        printf("%d\n",queues->data[x]);
    }
}

int main(){
    int *d ;
    Queues  q=Init_Queues();
//    push(q,1);
//    push(q,2);
   q= M_Insert(q);
    Print_Queues(q);
    pop(q,&d);
    printf("删除之后\n");
    Print_Queues(q);
    printf("出队的值\n");
    printf("%d\n",d);
}
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79