队列
建议你在看这篇文章先看一下 顺序表知识。
我在这里通过顺序表的写法实现 先进先出的特征来实现队列。当然顺序表也可以实现栈，感兴趣的朋友可以看 顺序表实现栈。
概念篇
图示
代码篇
1. 队列的声明
把一些属性封装起来表示队列。
因为有队首和队尾索引，所以就不需要size成员了。
q->rear-q->front==size;
typedef struct queue
{
int front;
//队头索引
int rear;
//队尾索引
int*elements;
int capacity;
}queue;
2.队列的创建
初始化时，队头索引和队尾索引设置为0，为数组分配内存空间
void queue_creat(queue*q)
{
q->elements=(int*)malloc(sizeof(int)*8);
/*在这里我为栈分配足够的内存以存储8个整数，
也可以不是8，但不能是零
*/
q->front=q->rear=0;
//最开始队列为空，所以队头索引和队首索引都为0
q->capacity=8;
}
3.队列的销毁
释放生成的内存空间，初始化队首和队尾索引，elements指针指向空。
void queue_destroy(queue*q)
{
free(q->elements);
q->front=q->rear=0;
q->capacity=0;
q->elements=NULL;
//防止野指针
}
4.队列扩容
当队列满时需要扩容，用顺序表实现队列通常都需要扩容。
void queue_expand(queue*q)
{
int *newelements=(int*)realloc(q->elements,sizeof(int)*q->capacity*2);
//倍数是任意的根据具体情况而定
if(newelements=NULL)
exit(1);
//内存分配失败时，终止程序进行。
q->elements=newelements;
q->capacity*=2;
}
5.入列
从队尾索引位置插入元素
void queue_push(queue*q,int value)
{
if(q->rear-q->front==q->capacity)
queue_expand(&q);
q->elements[q->rear++]=value;
}
6.出列
每次都删除的是队头索引对应的元素
int queue_pop(queue*q)
{
if(q->rear==q->front)
{
printf("queue is empty!");
exit(1);
}
return q->elements[q->front++];
}
6.队首元素
int queue_front(queue*q)
{
return q->elements[q->front];
}
7.队列的元素个数
int queue_size(queue*q)
{
return q->rear-q->front;
}
完整代码
#include<stdio.h>
#include<stdlib.h>
typedef struct queue
{
int front;
//队头索引
int rear;
//队尾索引
int*elements;
int capacity;
}queue;
void queue_creat(queue*q)
{
q->elements=(int*)malloc(sizeof(int)*8);
/*在这里我为栈分配足够的内存以存储8个整数，
也可以不是8，但不能是零
*/
q->front=q->rear=0;
//最开始队列为空，所以队头索引和队首索引都为0
q->capacity=8;
}
void queue_destroy(queue*q)
{
free(q->elements);
q->front=q->rear=0;
q->capacity=0;
q->elements=NULL;
//防止野指针
}
void queue_expand(queue*q)
{
int*newelements=(int*)realloc(q->elements,sizeof(int)*q->capacity*2);
//倍数是任意的根据具体情况而定
if(newelements=NULL)
exit(1);
//内存分配失败时，终止程序进行。
q->elements=newelements;
q->capacity*=2;
}
void queue_push(queue*q,int value)
{
if(q->rear-q->front==q->capacity)
queue_expand(&q);
q->elements[q->rear++]=value;
}
int queue_pop(queue*q)
{
if(q->rear==q->front)
{
printf("queue is empty!");
exit(1);
}
return q->elements[q->front++];
}
int queue_front(queue*q)
{
return q->elements[q->front];
}
int queue_size(queue*q)
{
return q->rear-q->front;
}
int main()
{
queue q;
queue_creat(&q);
queue_push(&q,10);
queue_push(&q,20);
queue_push(&q,30);
//在队尾插入，所以顺序为：
/* 10 20 30
队头 队尾
*/
printf("q size is:%d\n",queue_size(&q));
//q size is :3
printf("q pop is:%d\n",queue_pop(&q));
//队头删除，10
printf("q front is:%d\n",queue_front(&q));
/* 20 30
队头 队尾
*/
//q front is 20
printf("q size is:%d\n",queue_size(&q));
//q size is:2
queue_destroy(&q);
return 0;
}
运行结果
在下一篇文章中，我将会写如何用链表实现栈，感兴趣的朋友可以先看一下链表的知识和链表实现栈这两篇文章