1. 简介
队列是一种先进先出的线性表，只允许在表的一端进行插入，而在另一端删除元素。插入端叫队头，删除端叫队尾。
根据存储空间的分配方式可以分为
①、用连续内存空间的数组实现的顺序队列
②、用动态分配的堆空间实现的链队列
2. 顺序队列
顺序队列
rear > front
/* 顺序队列结构。元素存放在连续的内存空间（系统数组）。
采用循环存储。当 rear 到达 MAXSIZE 时，对 MAXSIZE 取余并赋值给 rear
rear = (rear + 1) % MAXSIZE；
保留一个空的内存，用于判断队列是否已满。
*/
typedef struct Queue
{
int data[MAXSIZE];
int front;
int rear; // 注意：rear > front
} Queue;
/// 初始化队列
void initQueue(Queue * queue)
{
queue->rear = queue->front = 0;
}
/// 空队列
bool isEmptyQueue(Queue * queue)
{
return (queue->rear == queue->front);
}
/// 满队列
bool isFullQueue(Queue * queue)
{
// 如果队尾"追上"队头，则已满
return (queue->rear + 1) % MAXSIZE == queue->front;
}
/// 入队
bool inputQueue(Queue * queue, int data)
{
if (isFullQueue(queue)) {
return NO;
}
queue->data[queue->rear] = data; // 队尾存入
queue->rear = (queue->rear + 1) % MAXSIZE; // 队尾对应的索引值增加
return YES;
}
/// 出队。由 data 返回删除的值
bool outputQueue(Queue * queue, int * data)
{
if (isEmptyQueue(queue))
return NO;
*data = queue->data[queue->front]; // 取出队头的值
queue->front = (queue->front + 1) % MAXSIZE;
return YES;
}
/// 打印队列的内容
void printQueue(Queue * queue)
{
if (isEmptyQueue(queue))
return;
int i = queue->front;
while (i != queue->rear) {
printf("%d\t", queue->data[i]);
i = (i + 1) % MAXSIZE;
}
printf("\r\n");
}
/// 调用
{
int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int i = 0;
int data = 0;
Queue queue = { 0 };
initQueue(&queue);
for (i = 0; i < sizeof(array)/sizeof(int); i++) {
inputQueue(&queue, array[i]);
}
printQueue(&queue);
outputQueue(&queue, &data);
printf("%d\n", data);
outputQueue(&queue, &data);
printf("%d\n", data);
printQueue(&queue);
inputQueue(&queue, 11);
inputQueue(&queue, 12);
printQueue(&queue);
}
1 2 3 4 5 6 7 8 9
1
2
3 4 5 6 7 8 9
3 4 5 6 7 8 9 11 12
3. 链队列
链队列
/* 链队列结构。元素存放在动态分配的堆上，非连续的内存空间。
采用线性存储。队列不会满。
*/
typedef struct Node
{
int data;
struct Node * next;
} Node;
typedef struct Queue
{
Node * front;
Node * rear;
} Queue;
/// 初始化队列
void initQueue(Queue * queue)
{
queue->front = queue->rear = (Node *)malloc(sizeof(Node));
}
/// 空队列
bool isEmptyQueue(Queue * queue)
{
return (queue->rear == queue->front);
}
/// 入队
void inputQueue(Queue * queue, int data)
{
Node * node = (Node *)malloc(sizeof(Node));
node->data = data;
node->next = NULL;
queue->rear->next = node; // 将上一个节点的 next 指向 node
queue->rear = node; // 移动 rear 的位置
}
/// 出队。若队列不空，由 data 返回删除的值
bool outputQueue(Queue * queue, int * data)
{
if (isEmptyQueue(queue))
return NO;
Node * firstNode = queue->front->next; // 指向第一个结点
*data = firstNode->data;
queue->front->next = firstNode->next; // 将头节点指向新的"第一个结点"
if (queue->rear == firstNode) { // 删除的正好是队尾结点
queue->rear = queue->front; // 将 rear 指针指向头结点
}
return YES;
}
/// 打印队列的内容
void printQueue(Queue * queue)
{
if (isEmptyQueue(queue))
return;
Node * node = queue->front->next; // 指向头结点
while (node) {
printf("%d\t", node->data);
node = node->next;
}
printf("\r\n");
}
/// 调用
{
int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int i = 0;
int data = 0;
Queue queue = { 0 };
initQueue(&queue);
for (i = 0; i < sizeof(array)/sizeof(int); i++) {
inputQueue(&queue, array[i]);
}
printQueue(&queue);
outputQueue(&queue, &data);
printf("%d\n", data);
outputQueue(&queue, &data);
printf("%d\n", data);
printQueue(&queue);
inputQueue(&queue, 11);
inputQueue(&queue, 12);
printQueue(&queue);
}
1 2 3 4 5 6 7 8 9
1
2
3 4 5 6 7 8 9
3 4 5 6 7 8 9 11 12
3、循环队列
循环链实现队列
循环队列与链队列的比较
①、时间：循环队列和链队列的基本操作都是 O(1)。不过循环队列是事先已申请好空间，使用期间不会释放。而对于链队列，每次申请和释放结点也会存在一些时间开销。如果入队和出队频繁，链队列会耗费更多的时间。
②、空间：循环队列必须有一个固定的长度，所以就会有存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但是是可以接受的。所以从空间上说，链队列更加灵活。
总的来说，在可以确定链队列最大长度的情况下，建议使用循环队列。如果无法预估队列的长度，则使用链队列。
网友评论