循环队列
- 预先分配好数组空间
#define BUFFER_SIZE 1024
// 在栈区分配空间
int buf[N];
// 在堆区分配空间
int* buf;
buf = (int*)malloc(BUFFER_SIZE * sizeof(int));
- 定义队头指针和队尾指针
int front, back;
![](/i/l/?n=23&i=blog/2641204/202303/2641204-20230320093846564-1166507433.png)
思路:front 始终指向队头元素位置的前一个位置,back 始终指向队尾元素位置。
- 出队操作就是先将
front
后移front = (front + 1) % BUFFER_SIZE
然后将队头buf[front]
出队。 - 入队操作就是先将
back
后移back = (back + 1) % BUFFER_SIZE
然后入队buf[back]=x
1 初始化
- 开始,队中没有元素。
front = back = 0
void init(){
front = back = 0;
}
2 队空和队满判断
队空条件和队满条件相同,都是
front == back
- 解决方法:
- 方法一:附设一个存储队中元素个数的变量
size
- 方法二:少用一个元素空间,使
(back + 1) % BUFFER_SIZE == front
为队满条件
- 方法一:附设一个存储队中元素个数的变量
- 方法一:
int isEmpty(){
return front == back;// 或 size == 0
}
int isFull(){
return size == BUFFER_SIZE;
}
- 方法二:
int isEmpty(){
return front == back;
}
int isFull(){
return (back + 1) % BUFFER_SIZE == front;
}
3 入队操作和出队操作
- 方法一:
#define inf 0x3f3f3f3f
int pop_front(){
if(front == back) return inf;
front = (front + 1) % BUFFER_SIZE;
return buf[front];
}
int push_back(int x){
if(size == BUFFER_SIZE) return 0;
back = (back + 1) % BUFFER_SIZE;
buf[back] = x;
return 1;
}
- 方法二:
#define inf 0x3f3f3f3f
int pop_front(){
if(front == back) return inf;
front = (front + 1) % BUFFER_SIZE;
return buf[front];
}
int push_back(int x){
if((back + 1) % BUFFER_SIZE == front) return 0;
back = (back + 1) % BUFFER_SIZE;
buf[back] = x;
return 1;
}
完整实现代码
myQueue.h
#define N 50
#define INF 0x3f3f3f3f
typedef struct
{
int* buf;
int front; ///< 队头指针
int back; ///< 队尾指针
int size; ///< 队列实际尺寸
}myQueue;
extern void initQueue(myQueue*);
extern int isEmpty(const myQueue*);
extern int isFull(const myQueue*);
extern int queueSize(const myQueue*);
extern int pop_front(myQueue*);
extern int push_back(myQueue*, int);
myQueue.c
#include "../include/myQueue.h"
#include <stdlib.h>
/// @brief 初始化循环队列
/// @param que 要初始化的队列对象的指针
void initQueue(myQueue* que)
{
que->buf = (int*)malloc(N * sizeof(int));
que->front = 0;
que->back = 0;
que->size = 0;
}
/// @brief 判断队列是否为空
int isEmpty(const myQueue* que)
{
return que->front == que->back;
}
/// @brief 判断队列是否满了
int isFull(const myQueue* que)
{
return que->size == N;
}
/// @brief 得到队列的长度
int queueSize(const myQueue* que)
{
return que->size;
}
/// @brief 出队
int pop_front(myQueue* que)
{
if(!que->size) return INF;
que->front = (que->front + 1) % N;
que->size --;
return que->buf[que->front];
}
/// @brief 入队
int push_back(myQueue* que, int x)
{
if(que->size == N) return 0;
que->back = (que->back + 1) % N;
que->buf[que->back] = x;
que->size ++;
return 1;
}
标签:myQueue,return,队列,back,int,循环,que,front,数据结构
From: https://www.cnblogs.com/Critical-Thinking/p/17235308.html