数据结构——循环队列

数据结构——循环队列

目录

一、概念

1.1 基本概念

1.2 队列的特点

1.3 循环队列

二、基本操作

2.1 结构体设计​编辑5

2.2 初始化

2.3 入队

2.4 出队

2.5 获取队头元素

2.6 查找

2.7 判空

2.8 判满

2.9 获取有效值元素个数

2.10 清空

2.11 销毁

2.12 打印

2.13 主函数测试

---

一、概念

1.1 基本概念

队列是只允许在一端进行插入操作，另一端删除操作的线性表。

1.2 队列的特点

• 先进先出（FIFO）：队列的元素按照进入的顺序排队，先进入的元素先被处理。

• 两端操作：队列有两个主要的操作端：

  • 队尾（rear）：新元素从队尾进入队列。

  • 队头（front）：元素从队头被移除。

1.3 循环队列

循环队列通过将数组的头尾相连，解决了普通队列的假溢出问题。具体来说，当队尾指针移动到数组的末尾时，它会自动跳转到数组的开头，形成一个循环。这样，队列可以更有效地利用数组的空间。 

二、基本操作

2.1 结构体设计

#define MAX_SIZE 10//循环队列的结构体设计：sequence
typedef int ELEM_TYPE;
typedef struct CQueue
{ELEM_TYPE* base;//用来接收malloc的返回值int front;//队头指针int rear;//队尾指针
}CQueue;

• base 它的作用是指向队列的起始内存地址。队列中的所有元素都存储在这块连续的内存空间中。

• int front;

• **front**是队头指针，用来标记队列的第一个元素的位置。

• 在循环队列中，front始终指向队列的第一个元素。

• 当队列为空时，front和rear都指向同一个位置（通常是0）。

• 当从队列中移除一个元素时，front会向前移动一位。

• int rear;

• rear是队尾指针，用来标记队列的最后一个元素的下一个位置。

• 在循环队列中，rear始终指向队列的最后一个元素的下一个位置。这是为了方便判断队列是否已满。

• 当向队列中添加一个新元素时，rear会向前移动一位。

• 队列已满的条件是：rear的下一个位置是front

2.2 初始化

void Init_Circle_Queue(struct CQueue* pcq)
{assert(pcq != NULL);pcq->base = (ELEM_TYPE *)malloc(MAX_SIZE * sizeof(ELEM_TYPE));pcq->front = 0;pcq->rear = 0;
}

• struct CQueue* pcq：这是一个指向CQueue结构体的指针，表示要初始化的循环队列。

• 这个指针pcq告诉函数“我要初始化的是哪一个队列”。

• pcq->base：这是队列的基地址指针，用来存储队列的起始内存地址。为队列分配内存空间 

• malloc：这是一个动态内存分配函数，用于在堆上分配一块指定大小的内存空间。

2.3 入队

bool Push(struct CQueue* pcq, ELEM_TYPE val)
{//0.安全性处理//1.判满if (IsFull(pcq))return false;pcq->base[pcq->rear] = val;pcq->rear = (pcq->rear + 1)%MAX_SIZE;//考虑队尾指针有可能由尾到头return true;
}

rear是队尾指针，用来标记队列的最后一个元素的下一个位置。 

• pcq的作用是让我们能够访问和操作这个队列的各个成员（比如base、front和rear）。

• 在循环队列中，base是一个动态分配的数组，用来存储队列中的所有元素。

• pcq->rear表示队尾指针的位置，pcq->base[pcq->rear]通过指针偏移访问队列中rear位置的元素。

• pcq->rear = (pcq->rear + 1) % MAX_SIZE;这行代码的作用是更新队尾指针rear的位置，确保它在数组范围内循环移动。具体步骤如下：

• pcq->rear + 1：将rear指针向前移动一位。

• % MAX_SIZE：使用模运算确保rear指针在0到MAX_SIZE-1的范围内循环。

2.4 出队

bool Pop(struct CQueue* pcq)
{//0.安全性处理//1.判空if (IsEmpty(pcq))return false;pcq->front = (pcq->front + 1) % MAX_SIZE;return true;
}

从循环队列中移除队头元素 

• pcq->front + 1：队头指针向前移动一位。

• % MAX_SIZE：使用模运算确保队头指针在数组范围内循环。如果队头指针移动到数组的末尾，它会自动跳转到数组的开头。 更新队头位置

2.5 获取队头元素

ELEM_TYPE Front(struct CQueue* pcq)
{//0.安全性处理//1.判空if (IsEmpty(pcq))return false;return pcq->base[pcq->front];
}

2.6 查找

int Search(struct CQueue* pcq, ELEM_TYPE val)
{//0.安全性处理for (int i = pcq->front; i != pcq->rear; i = (i + 1) % MAX_SIZE){if (pcq->base[i] == val)return i;}return -1;
}

• i != pcq->rear：循环条件是i不等于队尾指针pcq->rear。在循环队列中，rear指向队列的最后一个元素的下一个位置，因此当i等于rear时，表示已经遍历完整个队列。

• i = (i + 1) % MAX_SIZE：每次循环将i向前移动一位，并通过模运算确保i在数组范围内循环。如果i移动到数组的末尾，它会自动跳转到数组的开头。

2.7 判空

bool IsEmpty(struct CQueue* pcq)
{return pcq->front == pcq->rear;
}

2.8 判满

bool IsFull(struct CQueue* pcq)
{//判满条件：尾向后再走一步遇到了头return (pcq->rear + 1) % MAX_SIZE == pcq->front;
}

• 判满的条件是队尾指针的下一个位置与队头指针重合

• (pcq->rear + 1) % MAX_SIZE == pcq->front：检查队尾指针的下一个位置是否与队头指针重合。如果重合，说明队列已满。

2.9 获取有效值元素个数

int Get_Size(struct CQueue* pcq)
{//0.return ((pcq->rear - pcq->front) + MAX_SIZE) % MAX_SIZE;
}

2.10 清空

void Clear(struct CQueue* pcq)
{//0.assert pcq//pcq->front = pcq->rear;//pcq->rear = pcq->front;pcq->front = pcq->rear = 0;
}

2.11 销毁

void Destroy(struct CQueue* pcq)
{//0.assert pcqfree(pcq->base);
}

2.12 打印

void Show(struct CQueue* pcq)
{for (int i = pcq->front; i != pcq->rear; i = (i + 1) % MAX_SIZE){printf("%d ", pcq->base[i]);}printf("\n");
}

2.13 主函数测试

int main()
{struct CQueue head;Init_Circle_Queue(&head);Push(&head, 1);Push(&head, 2);Push(&head, 3);Show(&head);Pop(&head);Push(&head, 4);Show(&head);Push(&head, 5);Push(&head, 6);Push(&head, 7);Push(&head, 8);Push(&head, 9);Push(&head, 10);Show(&head);Push(&head, 11);Show(&head);Pop(&head);Push(&head, 111);Show(&head);printf("队头元素值=%d\n", Front(&head));return 0;
}