队列是一种受限的线性表，它是只在队首进行插入，且只能在队尾进行删除。队列具有先进先出的特性，广泛应用在树的层次遍历、图的广度优先遍历、键盘的输入缓冲区、操作系统和事务管理等方面。
顺序队列有两种类型，一是使用数组静态存储元素，二是使用指针动态分配空间存储元素。
区分队空和队满，有以下两种方法：
1.少用一个存储单元。队空的判断条件为front==rear；队满的判断条件为front==(rear+1%MaxSize;
2.增加一个标志位。设标志位为tag，初始时，tag=0；当入队成功，则tag=1；出队成功，tag=0。则判断队空的条件为：front==rear&&tag==0;队满的条件为：front==rear&&tag==1.
静态队列
方案一
数据结构
#define MaxSize 5//定义栈中元素的最大个数
typedef int ElemType;
typedef struct Squeue {
ElemType data[MaxSize];
int front, rear;
}Squeue, *seqQueue;
初始化
//初始化
void InitSqueue(seqQueue q) {
q->front = q->rear = 0;
}
判空
//判空
int isEmptyQueue(seqQueue q) {
if (q->front == q->rear) {
printf("isEmptyQueue...\n");
return 0;
}
return -1;
}
判满
//判满
int isFullQueue(seqQueue q) {
if ((q->rear+1) % MaxSize == q->front) {
printf("isFullQueue...\n");
return 0;
}
return -1;
}
入队
//入队
int EnterQueue(seqQueue q, ElemType data) {
if (isFullQueue(q) == 0) {
return -1;
}
q->data[q->rear] = data;
q->rear = (q->rear + 1) % MaxSize;
return 0;
}
出队
//出队
int DeleteQueue(seqQueue q, int *data) {
if (isEmptyQueue(q) == 0) {
return -1;
}
*data = q->data[q->front];
q->front = (q->front + 1)%MaxSize;
return *data;
}
求队长
//求队长
int LengthQueue(seqQueue q, int *length) {
if (isEmptyQueue(q) == 0) {
return -1;
}
if (isFullQueue(q) == 0) {
return MaxSize;
}
*length = (q->rear-q->front+MaxSize)%MaxSize;
return *length;
}
测试
void testQueue() {
int data, length;
Squeue seq;
seqQueue q = &seq;
InitSqueue(q);
EnterQueue(q, 23);
EnterQueue(q, 45);
EnterQueue(q, 89);
EnterQueue(q, 23);
EnterQueue(q, 45);
data = DeleteQueue(q, &data);
printf("%d\n", data);
length = LengthQueue(q, &length);
printf("%d\n", length);
}
方案二
结构体
#define MaxSize 5//定义栈中元素的最大个数
typedef int ElemType;
typedef struct STqueue {
ElemType data[MaxSize];
int front, rear;
int tag;
}STqueue, *seqTQueue;
初始化
//初始化
void init_squeue(seqTQueue q) {
q->front = q->rear = 0;
q->tag = 0;
}
判空
//判空
int is_empty_queue(seqTQueue q) {
if (q->front == q->rear && q->tag == 0) {
printf("is_empty_queue...\n");
return 0;
}
return -1;
}
判满
//判满
int is_full_queue(seqTQueue q) {
if (q->front == q->rear && q->tag == 1) {
printf("is_full_queue...\n");
return 0;
}
return -1;
}
入队
//入队
int enter_queue(seqTQueue q, ElemType data) {
if (is_full_queue(q) == 0) {
return -1;
}
if (q->rear == MaxSize) {
return -1;
}
q->data[q->rear] = data;
q->tag = 1;
q->rear = (q->rear + 1) % MaxSize;
return 0;
}
出队
//出队
int delete_queue(seqTQueue q, int *data) {
if (is_empty_queue(q) == 0) {
return -1;
}
*data = q->data[q->front];
q->tag = 0;
q->front = (q->front + 1) % MaxSize;
return *data;
}
求队长
//求队长
int length_queue(seqTQueue q, int *length) {
if (is_empty_queue(q) == 0) {
return -1;
}
if (is_full_queue(q) == 0) {
return MaxSize;
}
*length = (q->rear-q->front+MaxSize)%MaxSize;
return *length;
}
测试
void test_queue() {
int data, length;
STqueue seq;
seqTQueue q = &seq;
init_squeue(q);
enter_queue(q, 23);
enter_queue(q, 29);
enter_queue(q, 45);
enter_queue(q, 56);
enter_queue(q, 66);
enter_queue(q, 90);
data = delete_queue(q, &data);
printf("%d\n", data);
length = length_queue(q, &length);
printf("%d\n", length);
}
动态队列
结构体
#define MaxSize 5
typedef int ElemType;
typedef struct sequeue {
ElemType *data;
int front, rear;
int max;//记录队列分配的存储容量
}sequeue, *psequeue;
初始化
//初始化
void init_sequeue(psequeue q) {
q->data = (ElemType *)malloc(sizeof(ElemType)*MaxSize);
if (!q->data) {
exit(-1);
}
q->front = q->rear = 0;
q->max = MaxSize;
}
判空
//判空
int is_empty_sequeue(psequeue q) {
if (q->front == q->rear) {
return 0;
}
return -1;
}
扩容
//判满扩容
void check_capacity(psequeue q) {
if ((q->rear+1)%q->max == q->front) {
ElemType *temp = (ElemType *)realloc(q->data, sizeof(ElemType)*(q->max+MaxSize));
q->data = temp;
q->max += MaxSize;
}
}
入队
//入队
int enter_sequeue(psequeue q, ElemType data) {
check_capacity(q);
q->data[q->rear] = data;
q->rear = (q->rear+1) % q->max;
return 0;
}
出队
//出队
int delete_sequeue(psequeue q, int *data) {
if (is_empty_sequeue(q) == 0) {
return -1;
}
*data = q->data[q->front];
q->front = (q->front+1) % q->max;
return *data;
}
求队长
//求队长
int length_sequeue(psequeue q, int *length) {
if (is_empty_sequeue(q) == 0) {
return -1;
}
*length = (q->rear-q->front+q->max) % q->max;
return *length;
}
测试
void test_sequeue() {
int data, length;
sequeue seq;
psequeue q = &seq;
init_sequeue(q);
enter_sequeue(q, 92);
enter_sequeue(q, 34);
enter_sequeue(q, 56);
enter_sequeue(q, 92);
enter_sequeue(q, 34);
enter_sequeue(q, 56);
enter_sequeue(q, 92);
enter_sequeue(q, 34);
enter_sequeue(q, 56);
data = delete_sequeue(q, &data);
printf("%d\n", data);
length = length_sequeue(q, &length);
printf("%d\n", length);
}
