队列

队列是一种和栈相反的数据结构，属于FIFO（First In, First Out）的线性表，我们只能够在队列的一端进行插入在另一端进行删除元素的操作。允许插入的一端称为队尾， 允许删除的一端称为队头。在程序设计中，典型的队操作是操作系统中的作业排队。

循环队列

将顺序队列臆造出一个环状的空间，称之为循环队列。如图

注意这里少用一个元素空间是为了区别队列是空还是满， 因为如果front中存储数据的话，front==rear不足以判断队是空还是满

还有一种方式是设置标志位来区分

循环队列的结构

front为队首指针 rear为队尾指针

typedef char Elemtype; typedef struct{ Elemtype *base; int front; int rear; }SqQueue;

循环队列的基本操作实现

初始化循环队列 /* 初始化循环队列 */ Status InitSqQueue(SqQueue *q) { q->base = (Elemtype *)malloc(sizeof(Elemtype)* DATA_MAX_SIZE); if (!q->base) return ERROR; q->front = q->rear = 0; return OK; } 销毁循环队列 /* 销毁队列 */ Status DestoryQueue(SqQueue *q) { free(q->base); q->base = NULL; q->front = q->rear = 0; return OK; } 计算队列长度 /* 队列的长度 */ int SqQueueLength(SqQueue q) { return (q.rear - q.front + DATA_MAX_SIZE) % DATA_MAX_SIZE; } 入队 /* 入队 */ Status EnSqQueue(SqQueue *q, Elemtype e) { if ((q->rear + 1) % DATA_MAX_SIZE == q->front)//队满检测 return ERROR; q->base[q->rear] = e; q->rear = (q->rear + 1) % DATA_MAX_SIZE;//确保指针rear的取值范围在0-DATA_MAX_SIZE中 return OK; } 出队 /* 出队 */ Status DeSqQueue(SqQueue *q, Elemtype *e) { if (q->front == q->rear) return ERROR; *e = q->base[q->front]; q->front = (q->front + 1) % DATA_MAX_SIZE; return OK; }

测试使用代码

#if 0 循环队列， 使用front和rear 少使用一个元素空间，约定"队列指针在队尾指针的下一位置（环状的下一位置上）作为队列呈满状态标识" #endif #include <stdio.h> #include <stdlib.h> #define DATA_MAX_SIZE 10 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; typedef char Elemtype; typedef struct{ Elemtype *base; int front; int rear; }SqQueue; /* 初始化循环队列 */ Status InitSqQueue(SqQueue *q) { q->base = (Elemtype *)malloc(sizeof(Elemtype)* DATA_MAX_SIZE); if (!q->base) return ERROR; q->front = q->rear = 0; return OK; } /* 销毁队列 */ Status DestoryQueue(SqQueue *q) { free(q->base); q->base = NULL; q->front = q->rear = 0; return OK; } /* 入队 */ Status EnSqQueue(SqQueue *q, Elemtype e) { if ((q->rear + 1) % DATA_MAX_SIZE == q->front)//队满检测 return ERROR; q->base[q->rear] = e; q->rear = (q->rear + 1) % DATA_MAX_SIZE;//确保指针rear的取值范围在0-DATA_MAX_SIZE中 return OK; } /* 出队 */ Status DeSqQueue(SqQueue *q, Elemtype *e) { if (q->front == q->rear) return ERROR; *e = q->base[q->front]; q->front = (q->front + 1) % DATA_MAX_SIZE; return OK; } /* 队列的长度 */ int SqQueueLength(SqQueue q) { return (q.rear - q.front + DATA_MAX_SIZE) % DATA_MAX_SIZE; } int main() { SqQueue q; Elemtype e; printf("初始化循环队列\n"); InitSqQueue(&q); printf("开始入队a, b, c\n"); if (EnSqQueue(&q, 'a') == ERROR) printf("错误：队满\n"); if (EnSqQueue(&q, 'b') == ERROR) printf("错误：队满\n"); if (EnSqQueue(&q, 'c') == ERROR) printf("错误：队满\n"); if (EnSqQueue(&q, 'd') == ERROR) printf("错误：队满\n"); if (EnSqQueue(&q, 'e') == ERROR) printf("错误：队满\n"); printf("开始出队\n"); if (DeSqQueue(&q, &e) == ERROR) printf("错误：队空\n"); printf("出队： %c\n", e); if (DeSqQueue(&q, &e) == ERROR) printf("错误：队空\n"); printf("出队： %c\n", e); if (DeSqQueue(&q, &e) == ERROR) printf("错误：队空\n"); printf("出队： %c\n", e); printf("销毁队列\n"); DestoryQueue(&q); system("pause"); return 0; }