一个循环队列的C语言实现,数据类型Queue
定义如下,注意在 typedef struct{...}Queue;
中Queue为数据类型,而在struct {...}Queue;
中Queue为一个变量名。 front
为队首元素下标,始终指向队首元素,tail
为队尾元素的下一个位置的下标。初始状态为front=tail=0
typedef struct {
int size,eleNum;
int* array;
int front,tail; //front指向第一个元素,rear指向最后一个元素的下一个位置
} Queue;
基本操作有: add()
, 添加元素到队尾 peek()
, 获取但并不移出头 poll()
, 获取并移出队首元素 create(n)
, 创建大小为n的队列 isempty()
, 判断队列是不是空
另外,队列操作函数的参数都为指针,这样可以实现模拟引用传递的效果,如果参数为add(Queue q,int n)
, 对队列的修改并不会影响到初始的队列。可以修改运行试一下。
代码实现如下:
#include<stdio.h>
#include<stdlib.h>
/*用c语音实现队列基本操作 add(), 添加元素到队尾 peek(), 获取但并不移出头 poll(), 获取并移出队首元素 create(n), 创建大小为n的队列 isempty(), 判断队列是不是空 */
typedef struct {
int size,eleNum;
int* array;
int front,tail; //front指向第一个元素,rear指向最后一个元素的下一个位置
} Queue;
//取出并移除第一个元素
int poll(Queue* q){
int res = q->array[q->front];
q->front = (++(q->front))%q->size;
q->eleNum--;
return res;
}
//获取长度
int len(Queue* q){
return q->eleNum;
}
//插入k,返回1表示插入成功
int add(Queue* q,int k){
if(q->size==q->eleNum){
return 0;
}
q->eleNum++;
q->array[q->tail] = k;
q->tail = (q->tail+1) % q->size;
return 1;
}
//取出头部元素,不删除此元素,peek是“偷看”的意思
int peek(Queue* q){
return q->array[q->front];
}
//返回1表示为空,0表示不空
int isEmpty(Queue* q){
if(q->eleNum==0){
return 1;
}
return 0;
}
//创建大小为n的队列
Queue* createQue(int n){
Queue* que = (Queue*)malloc(sizeof(Queue));
que->size = n;
que->eleNum = 0;
que->array = (int*)malloc(sizeof(int)*n);
que->front = 0;
que->tail = 0;
return que;
}
void display(Queue* q){
int i = q->front;
printf("elements: ");
while(i!=q->tail){
printf("%d ",q->array[i]);
i = (i+1)%q->size;
}
printf("\n");
printf("size: %d,elements num: %d\n",q->size,q->eleNum);
printf("front: %d, tail:%d \n",q->front,q->tail);
}
int main(){
Queue* q = createQue(10);
add(q,10); add(q,11); add(q,12);
poll(q); poll(q);
display(q);
return EXIT_SUCCESS;
}