菜鸟笔记
提升您的技术认知

循环队列详解-ag真人游戏

1. 循环队列

1.1 概念及结构

循环队列是一种特殊类型的队列数据结构,也被称为”唤醒缓冲器“。它在数组的基础上实现了循环利用空间的功能。在循环队列中,队尾和队头之间形成了一个循环,当队尾指针“追上”队头指针时,队列不再继续增长,而是继续利用之前出队的空间。

循环队列通常由两个指针来辅助构建:

  1. 队尾指针(rear):指向队尾元素的下一个位置,也就是即将插入新元素的位置。
  2. 队头指针(front):指向队头元素的位置

入队和出队:

  • 入队操作会将元素插入到队尾指针所指向的位置,并将队尾指针后移。当队列满时,入队操作会失败。

  • 出队操作会**删除队头元素,并将队头指针后移。**当队列为空时,出队操作会失败。

队空和队满的条件:

  • 当队列为空时,front指针和rear指针同时指向下标为0的位置,因此循环队列为空的条件为front == rear
  • 需要清楚,由于循环队列需要预留一个空间来区分队列为空和队列满的状态队列满的条件为rear 1 == head

为什么需要预留一个空间?

假设我们不预留空间,要对下面的队列插入元素‘7’

那么插入后,front(head)rear(tail)两个指针的关系就变成了这样:

可以看到,frontrear又相等了,这不就和队列为空的条件混到一起了吗。所以说要多预留一个空间用来判断队列满的情况:

1.2 结构的定义

这里我们用数组来模拟实现循环队列

typedef struct {
  
    int *data;	//动态数组
    int front;	//队头指针
    int rear;	//队尾指针
    int capacity;	//最大容量
} mycircularqueue

1.3 基本功能实现

1.3.1 初始化(返回一个循环队列指针)

mycircularqueue* mycircularqueuecreate(int k);
  • k为循环队列的最大容量
  • 该函数用来返回一个已经初始化好的循环队列指针
mycircularqueue* mycircularqueuecreate(int k) {
  
    mycircularqueue* cqueue = (mycircularqueue*)malloc(sizeof(mycircularqueue));
    
    cqueue->data = (int*)malloc(sizeof(int) * (k   1));	//申请k 1个空间
    cqueue->front = 0;
    cqueue->rear = 0;
    cqueue->capacity = k;
    return cqueue;
}

1.3.2 判空

bool mycircularqueueisempty(mycircularqueue* obj) {
  
    return obj->front == obj->rear;
}

1.3.3 判满

可不要简单的以为循环队列满的条件就是rear 1 == front,我们要考虑下面两种情况(假设最大容量为4):

情况一:

情况二:

上面两种情况队列都是满的,显然我们不能简单的用front == rear 1来判断队列是否已满。

直接下结论:我们可以用表达式(rear 1) % (capacity 1) == front来判断队列是否已满

bool mycircularqueueisfull(mycircularqueue* obj) {
  
    return (obj->rear   1)  % (obj->capacit   1) == obj->front;
}

1.3.4 入队

入队移动的是队尾指着,同样也要考虑两种情况:

情况一:

情况二:

bool mycircularqueueenqueue(mycircularqueue* obj, int value) {
  
    if (mycircularqueueisfull(obj))	//如果已满,插入失败
        return false;
    //如果队尾指针在队列尾部,那么插入过后,队尾指针移到最前面
    if (obj->rear == obj->capacity)
    {
  
        obj->data[obj->rear] = value;
        obj->rear = 0;
    }
    //否则队尾指针加以即可
    else
    {
  
        obj->data[obj->rear] = value;
        obj->rear  ;
    }
    return true;
}

1.3.5 出队

出队移动的是队头指针,考虑两种情况:

情况一:

情况二:

bool mycircularqueuedequeue(mycircularqueue* obj) {
  
    if (mycircularqueueisempty(obj))	//如果队列为空,则出队失败
        return false;
    //如果队头指针位于队列最后一个位置,那么删除后就要回到最前面
    if (obj->front == obj->capacity)
        obj->front = 0;
    //否则队头指针往后移即可
    else    
        obj->front  ;
    return true;
}

1.3.5 返回队头元素

由于队头指针指向的就是队头元素,因此直接返回下标位置的元素即可

int mycircularqueuefront(mycircularqueue* obj) {
  
    if (mycircularqueueisempty(obj))	//队列为空,返回-1
        return -1;
    return obj->data[obj->front];
}

1.3.6 返回队尾元素

由于队尾指针指向的是队尾元素的下一个位置,因此要考虑两种情况:

情况一:

情况二:

int mycircularqueuerear(mycircularqueue* obj) {
  
    if (mycircularqueueisempty(obj))	//队列为空,返回-1
        return -1;
    //如果队尾指针在下标为0的位置,就说明队尾元素位于数组最后的位置
    if (obj->rear == 0)
        return obj->data[obj->capacity];
    //否则,队尾元素就是队尾指针下标-1的位置
    else
        return obj->data[obj->rear - 1];
}

1.3.7 销毁队列

void mycircularqueuefree(mycircularqueue* obj) {
  
    free(obj->data);	//销毁数组
    free(obj);	//销毁队列
}

1.4 练习

学习完循环队列的相关知识,可以做这一题来加深印象设计循环队列

网站地图