数据结构算法每日一练（八）数组循环队列

难度： ⭐⭐

题目：下面是给定容量为MAX的使用循环数组实现队列的代码片段，其中T是队列中元素类型。

static int const MAX = 256; //队列的最大容量

static T* data; //循环数组，队列元素存储在此

static 其他必要数据;

（1）请给出循环数组实现队列所需的其他必要数据的定义；

（2）请使用循环数组实现队列的下述六个功能函数，请首先用语言描述实现的方法，再给出C/C++语言的具体实现。

void ini(); //初始化函数

int size(); //返回队列中元素个数

bool full(); //判满函数

bool empty(); //判空函数

T front(); //返回队头元素; T是元素类型

void push(T v); //入队

void pop(); //出队

（1）
1
2
3
4
static typedef struct {
    T* data; //存放队列元素
    int front, rear; //队头指针和队尾指针
} SqQueue;
（2）

void ini(); //初始化函数

首先将数组初始化，将队头指针和队尾指针设置初始值为0
1
2
3
4
void ini(SqQueue &Q) {
    Q.data = new T[MAX]; //数组初始化 
	Q.front = Q.rear = 0;
}
int size(); //返回队列中元素个数

队尾指针减去队头指针，然后加上MAX，然后取模MAX。
1
2
3
init size(SqQueue Q) {
    return (Q.rear - Q.front + MAX) % MAX;
}
bool full(); //判满函数

当队尾指针加1取模等于队头指针时，判满。
1
2
3
bool full(SqQueue Q) {
    return (Q.rear + 1) % MAX == Q.front;
}
bool empty(); //判空函数

当队头指针等于队尾指针时，队列为空。
1
2
3
bool empty(SqQueue Q) {
    return Q.front == Q.rear;
}
T front(); //返回队头元素; T是元素类型

先判断队列是否为空，若为空则返回-1，否则返回队头指针。
1
2
3
4
5
T front(SqQueue Q) {
    if(empty(Q))
        return -1;
	return Q.data[Q.front]; //返回
}
void push(T v); //入队

当入队时，先判断队列是否满，不满，则将数据加入队尾指针，然后队尾指针加1取模。
1
2
3
4
5
6
void push(SqQueue &Q, T v) {
    if(full(Q))
        return;
    Q.data[Q.rear] = v;
    Q.rear = (Q.rear + 1) % MAX;
}
void pop(); //出队

判断队列是否为空，若不为空，则先取出队头指针的数据，然后队头指针加1取模。
1
2
3
4
5
6
void pop(SqQueue &Q, T &x) {
    if(empty(Q))
        return;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MAX; //队头指针加1取模
}