循环队列

2023-12-10 15:45:03

循环队列类似栈，但是有两个口，一个专门用来入队，一个专门用来出队。由于入队出队不在一个端口，因此如果不适用循环队列，随着队列的使用，存储空间马上就被耗光了。在循环队列中，一个主要的知识点，就是如何判断队列为空，或者队列满。

这里主要有两个方法：

1 设置一个标记位，初始时，队列为空，我们设置flag=0;随着数据的使用，如果队满，设置flag=1;

2 使用一个空的数据位，这样rear指针永远也不能追上front指针。当front==rear时，队列即为空；当(rear-front)%SIZE==SIZE时，队列为满

数据结构

typedef struct Queue{
    int data[MAXSIZE];
    int front;
    int rear;
}Queue;

入队操作

int inQueue(Queue *q,int num){
    if((q->rear+1)%MAXSIZE == q->front)
        return 0;
    q->data[q->rear] = num;
    q->rear = (q->rear+1)%MAXSIZE;
    return 1;
}

出队操作

int outQueue(Queue *q,int *tar){
    if(q->front == q->rear)
        return 0;
    *tar = q->data[q->front];
    q->front = (q->front+1)%MAXSIZE;
    return 1;
}

示例代码

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #define MAXSIZE 10
 4 
 5 typedef struct Queue{
 6     int data[MAXSIZE];
 7     int front;
 8     int rear;
 9 }Queue;
10 
11 void initQueue(Queue *q,int n);
12 void showQueue(Queue *q);
13 int getLength(Queue *q);
14 int inQueue(Queue *q,int num);
15 int outQueue(Queue *q,int *tar);
16 
17 int main()
18 {
19     Queue *q = (Queue *)malloc(sizeof(Queue));
20     initQueue(q,3);
21     showQueue(q);
22 
23     if(inQueue(q,9))
24         showQueue(q);
25 
26     int *tar = (int *)malloc(sizeof(int));
27     if(outQueue(q,tar))
28         printf("the number %d out Queue\n",*tar);
29     showQueue(q);
30 
31     if(outQueue(q,tar))
32         printf("the number %d out Queue\n",*tar);
33     showQueue(q);
34 
35     if(inQueue(q,110))
36         showQueue(q);
37 
38     if(outQueue(q,tar))
39         printf("the number %d out Queue\n",*tar);
40     showQueue(q);
41 
42     if(outQueue(q,tar))
43         printf("the number %d out Queue\n",*tar);
44     showQueue(q);
45 
46     if(outQueue(q,tar))
47         printf("the number %d out Queue\n",*tar);
48     showQueue(q);
49 
50     free(tar);
51     free(q);
52     return 0;
53 }
54 
55 void initQueue(Queue *q,int n){
56     int i;
57     q->front=0;
58     q->rear =0;
59     for(i=0;i<n;i++){
60         q->data[q->rear]=2*i+1;
61         q->rear++;
62     }
63 }
64 void showQueue(Queue *q){
65     int i;
66     int len=getLength(q);
67     printf("front-");
68     for(i=0;i<len;i++){
69         if(q->front+i<MAXSIZE)
70             printf("%d-",q->data[q->front+i]);
71         else
72             printf("%d-",q->data[q->front+i-MAXSIZE]);
73     }
74     printf("rear\n");
75 }
76 int getLength(Queue *q){
77     return (q->rear-q->front+MAXSIZE)%MAXSIZE;
78 }
79 int inQueue(Queue *q,int num){
80     if((q->rear+1)%MAXSIZE == q->front)
81         return 0;
82     q->data[q->rear] = num;
83     q->rear = (q->rear+1)%MAXSIZE;
84     return 1;
85 }
86 int outQueue(Queue *q,int *tar){
87     if(q->front == q->rear)
88         return 0;
89     *tar = q->data[q->front];
90     q->front = (q->front+1)%MAXSIZE;
91     return 1;
92 }

运行结果