队列的抽象数据类型描述：
- 类型名称：队列（Queue）
- 数据对象集： 一个用 0 个或多个元素的又穷线性表。
-
操作集：长度为
max_size的队列Q∈Queue，队列元素item∈ElementType。
-
Queue creat_queue(int max_size): 生成长度为max_size的空队列； -
int is_full_q(queue q, int max_size): 判断队列Q是否已满； -
void add_q(queue q, element_type item): 将元素item插入队列Q中； -
int is_empty(queue q): 判断队列Q是否为空； -
element_type delete_q(queue q)：将队列元素从队列中删除并返回。
队列的顺序存储实现：
队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量 front 以及一个记录队列尾元素位置的变量 rear 组成。
纯C语言实现：
// 队列(Queue)
#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 10
#define elem_type int
#define Position int
#define bool int
#define True 1
#define Flase 0
#define ERROR -1 // 错误标识
typedef struct {
elem_type data[MAXSIZE];
Position front; // 出队
Position rear; // 入队
int len;
} Queue;
// 初始化
Queue* create_queue(void)
{
Queue* Q = (Queue*)malloc(sizeof(Queue));
Q->front = 0;
Q->rear = -1;
Q->len = 0;
return Q;
}
// 队列是否已满
bool is_full(Queue* Q)
{
bool n = Flase;
if (Q->len == MAXSIZE){
n = True;
}
return n;
}
// 入队
bool add_q(Queue* Q, elem_type x)
{
bool n = Flase;
if (is_full(Q) == 0){
// 用取余实现循环队列
Q->rear = (Q->rear + 1) % MAXSIZE;
Q->data[Q->rear] = x;
Q->len++;
n = True;
}
return n;
}
// 队列是否为空
bool is_empty(Queue* Q)
{
bool n = Flase;
if (Q->len == 0){
n = True;
}
return n;
}
// 出队
elem_type delete_q(Queue* Q)
{
Position idx;
if (is_empty(Q) == 0){
idx = Q->front;
Q->front = (Q->front + 1) % MAXSIZE; // 更新出队指针
Q->len--;
return Q->data[idx];
} else {
return ERROR;
}
}
// 输出队列元素
void print(Queue* Q)
{
int i;
int n;
for (i=0; i<Q->len; i++){
n = (Q->front + i) % MAXSIZE;
printf("%d\t", Q->data[n]);
}
printf("\n");
}
int main(void)
{
Queue* Q = NULL;
Q = create_queue();
// 才创建的队列应为空
if (is_empty(Q)){
printf("队列为空\n");
}
int i = 0;
// 入队 0 1 2 3 4
while (i<5){
add_q(Q, i++);
}
// 出队 0
delete_q(Q);
// 输出 1 2 3 4
print(Q);
printf("Q->front = %d\tQ->rear = %d\tQ->len = %d", Q->front, Q->rear, Q->len);
return 0;
}
IMG_20170629_225417.jpg
