引入

前面我们讲了，如何初始化一个循环队列，今天我们就来讲讲如何在队列中插入和删除数据。

入队列操作

如何判断队列已经满了

0 1 2 3 4 front rear 新 rear : (rear+1)%MAXSIZE
a 0:a 1: (1+1)%5=2
a b 0:a 2: (2+1)%5=3
a b c 0:a 3: (3+1)%5=4
b c d 1:b 4: (4+1)%5=0
c d e 2:c 0: (0+1)%5=1
f c d e 2:c 1 (1+1)%5=2
f g c d e 2:c 2 front=rear 所以满栈了

利用取模这个思路判断满栈就是

  • 就是让尾指针从头到尾不断的移动
  • 利用取模，让尾指针不断的在0~4之间移动
  • 如果尾指针指向了头部，也就是说
  • 可以插入的位置等于队列的第一个结点的位置了
  • 那就证明满栈了
void InsertQueue(struct Queue *q , int e){
    if((q->rear+1)% MAXSIZE==q->front){
        return;
    }
    q->base[q->rear]=e;
    q->rear = (q->rear+1) % MAXSIZE;
}

代码思路

  • 队头是当前排第一个的结点位置
  • 队尾是当前可插入的结点位置

出队操作

void delete_queue(struct Queue *q){
    if(q->front==q->rear){
        return ;
    }
    printf("%d号是：%d\n",q->front,q->base[q->front]);
    q->front=(q->front+1) % MAXSIZE;
}

计算队列长度

int queue_length(struct Queue*q){
    int i=0;
    i=(q->rear-q->front+MAXSIZE)%MAXSIZE;
    return i;
}

全部代码

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 5
#define LEN sizeof(struct Queue)

struct Queue{
    int *base;  // 也可以直接使用数组，我们这里用的是基地址
    int front;  //用于存储头部
    int rear;   //用于存储尾部
};

void initqueue(struct Queue *q){
    //先动态生成存储单元，给 base
    q->base=(int *)malloc(MAXSIZE * sizeof(int));
    //然后让指针归位到 0
    q->front=q->rear=0;
}

void InsertQueue(struct Queue *q , int e){
    if((q->rear+1)% MAXSIZE==q->front){
        return;
    }
    q->base[q->rear]=e;
    q->rear = (q->rear+1) % MAXSIZE;
}

void delete_queue(struct Queue *q){
    if(q->front==q->rear){
        return ;
    }
    printf("%d号是：%d\n",q->front,q->base[q->front]);
    q->front=(q->front+1) % MAXSIZE;
}

int queue_length(struct Queue*q){
    int i=0;
    i=(q->rear-q->front+MAXSIZE)%MAXSIZE;
    return i;
}

int main(){
    struct Queue *p;
    p=(struct Queue *)malloc(LEN);
    initqueue(p);
    
    InsertQueue(p, 1);
    printf("目前长度是%d\n",queue_length(p));
    InsertQueue(p, 2);
     printf("目前长度是%d\n",queue_length(p));
    InsertQueue(p, 3);
     printf("目前长度是%d\n",queue_length(p));
    InsertQueue(p, 4);
     printf("目前长度是%d\n",queue_length(p));
    InsertQueue(p, 5);
     printf("目前长度是%d\n",queue_length(p));
    delete_queue(p);
    delete_queue(p);
    delete_queue(p);
    delete_queue(p);
    delete_queue(p);
}

输出
目前长度是1
目前长度是2
目前长度是3
目前长度是4
目前长度是4
0号是：1
1号是：2
2号是：3
3号是：4

困惑

老实说，我也没搞明白，MAXSIZE 是5，最后一个结点因为 insert 的判断，竟然没有能够赋值。我明明输入了5个数进去，却只返回了4个数。
但书上《数据结构(C语言版)》确实是这么写的…

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。