一、概念
-
队列是允许在两端（队头、队尾）进行插入和读出操作的线性表
-
默认情况下，队尾插入，队头读出（这一点和排队很像），先进先出FIFO
-
队中没有元素时称为空队
-
当队列两端都允许插入、读出时，称为双端队列
二、顺序队列的结构模型
typedef int data_t
#define N (128) //队列容量
typedef struct{
data_t data[N]; //数组作为队列的存储空间
int front; //队头 指向队头元素
int rear; //队尾 指向队尾元素的下一个位置
}sequeue;2.1队空
刚创建的空队列就是如此，由此也可以得到空队的条件就是：front == rear
2.2入队
假设入队D1、D2、D3
这里入队的逻辑是，先入队元素，rear再移动（实际上也是rear++）
特殊情况是：入队的元素过多导致rear溢出，可以利用取余操作来避免这一风险
即：rear = (rear+1) % N
因此，这样一来也促成了“循环队列”
2.3出队
依次出队D1、D2
这里出队的逻辑是：先出队元素，front再移动
这里出队实际上也会遇到溢出情况，因为是循环队列，所以front的移动也对N取余即可
2.4满队
当队列再入队D7时，rear会移动到和front相同位置，但此刻是“满队”，会和“空队”冲突
为了避免这个情况，D7不允许入队，解决办法是：入队时进行判断，如果rear+1等于front，那么不执行入队操作
三、顺序队列的实现
typedef int data_t;
#define N 128
typedef struct{
data_t data[N]; //数组作为队列的存储空间
int front; //队头 指向队头元素
int rear; //队尾 指向队尾元素的下一个位置
}sequeue;
sequeue *queue_create(void); //创建队列
int enqueue(sequeue *q, data_t value); //入队
data_t dequeue(sequeue *q); //出队
int queue_is_empty(sequeue *q); //判断队列是否为空
int queue_is_full(sequeue *q); //判断队列是否已满
int queue_clear(sequeue *q); //清空队列
sequeue *queue_free(sequeue *q); //释放队列空间
3.1创建
sequeue *queue_create(void)
{
sequeue *q;
//申请空间
q = (sequeue*)malloc(sizeof(sequeue));
if(q == NULL)
{
printf("queue_create:malloc space failed!\n");
return NULL;
}
//初始化
memset(q->data,0,sizeof(q->data));
q->front = 0;
q->rear = 0;
return q;
} 3.2入队
int enqueue(sequeue *q, data_t value)
{
//参数检查
if(q == NULL)
{
printf("enqueue:queue passed is NULL!\n");
return -1;
}
//判断队列是否已满
if( (( q->rear + 1) % N) == q->front)
{
printf("enqueue:queue is full!\n");
return -1;
}
//入队
q->data[q->rear] = value;
//队尾++ 对N取余保证不溢出
q->rear = (q->rear + 1) % N;
return 1;
}3.3出队
data_t dequeue(sequeue *q)
{
data_t ret;//保存出队元素
//参数检查
if(q == NULL)
{
printf("dequeue:queue passed is NULL!\n");
return -1;
}
//应由程序判断队列是否为空，这里就不判断了
ret = q->data[q->front];
//front移动
q->front = (q->front + 1) % N;
return ret;
}3.4判断队列是否为空
int queue_is_empty(sequeue *q)
{
//参数检查
if(q == NULL)
{
printf("queue_is_empty:queue passed is NULL!\n");
return -1;
}
return (q->front==q->rear? 1 : 0);
}3.5判断队列是否已满
int queue_is_full(sequeue *q)
{
//参数检查
if(q == NULL)
{
printf("queue_is_full:queue passed is NULL!\n");
return -1;
}
//判断队列是否已满
if( (( q->rear + 1) % N) == q->front)
{
return 1;
}
else
{
return 0;
}
}3.6清空队列
int queue_clear(sequeue *q)
{
//参数检查
if(q == NULL)
{
printf("queue_clear:queue passed is NULL!\n");
return -1;
}
q->front = 0;
q->rear = 0;
return 1;
}3.7释放队列空间
sequeue *queue_free(sequeue *q)
{
//参数检查
if(q == NULL)
{
printf("queue_free:queue passed is NULL!\n");
return NULL;
}
free(q);
q = NULL;
return NULL;//传回主程序，避免野指针
}四、应用
#include <stdio.h>
#include "sequeue.h"
int main(void)
{
sequeue *q;
q = queue_create();
if(q == NULL)
{
printf("queue_create:create failed!\n");
return -1;
}
enqueue(q,10);
enqueue(q,20);
enqueue(q,30);
enqueue(q,40);
enqueue(q,50);
enqueue(q,60);
while(!queue_is_empty(q))
{
printf("dequeue:%d\n",dequeue(q));
}
q = queue_free(q);
return 0;
}
