队列

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)。不过循环队列是事先已申请好空间，使用期间不会释放。而对于链队列，每次申请和释放结点也会存在一些时间开销。如果入队和出队频繁，链队列会耗费更多的时间。
　　
②、空间：循环队列必须有一个固定的长度，所以就会有存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但是是可以接受的。所以从空间上说，链队列更加灵活。

总的来说，在可以确定链队列最大长度的情况下，建议使用循环队列。如果无法预估队列的长度，则使用链队列。