数据结构与算法 队列

栈是讲一种先进后出的数据结构，而在实际问题中还经常使用一种“先进先出”的数据结构：即插入在表一端进行，而删除在表的另一端进行，这叫数据结构被称为队列（Queue [kju]）。允许插入的一端被称为队尾（rear）,允许删除的一端成为队头（front）。如一个队列入队顺序依次为：a1;a2;a3;a4;a5，出队时顺序将依然是a1;a2;a3;a4;a5。就像超市排队的人结账。

队列也是一种运算受限的线性表，又叫先进先出表，简称“FIFO表”。

队列同样在物理存储上有两种结构

1.顺序存储的队列称为顺序队。
因为队列的队头和队尾都是活动的，因此，除了队列的数据区外还有队头、队尾两个指针。顺序队定义如下

typedef struct{
    int dataList[MAXSIZE];
    int rear;
    int font;
}SqQueue;

一些相关计算如下：

//队列的长度
int queueLength(SqQueue* queue){
    return (queue->rear - queue->font + MAXSIZE)%MAXSIZE;
}
//队列的初始化
int initQueue(SqQueue* queue){
    queue = malloc(sizeof(SqQueue));
    if (queue == NULL) {
        return 0;
    }
    queue->font = 0;
    queue->rear = 0;
    return 1;
}
//清空队列
int clearQueue(SqQueue* queue){
    queue->font = 0;
    queue->rear = 0;
    return 0;
}
//遍历队列
int traverseQueue(SqQueue* queue){
    int i = queue->font;
    while (i != queue->rear) {
        printf("%d ", queue->dataList[i]);
        i++;
    }
    printf("\n");
    return 0;
}
//队列为空的判断
int queueEmpty(SqQueue* queue){
    if (queue -> font == queue -> rear) {
        return 1;
    }
    return 0;
}
//入队
int in_queue(SqQueue* queue, int data){
    if ((queue -> rear + 1)%MAXSIZE == queue -> font) {
        return 0;
    }
    queue->dataList[queue->rear] = data;
    queue->rear = (queue->rear + 1)%MAXSIZE;
    return 1;
}
//出队
int out_queue(SqQueue* queue, int *e){
    if (queue -> font == queue -> rear) {
        return 0;
    }
    *e = queue -> dataList[queue->font];
    queue->font  = (queue -> font + 1)%MAXSIZE;
    return 1;
}

顺序存储结构由于有头和尾，在出队和入队的过程中产生假溢出的现象，

假溢出

如上图，仅仅单纯用rear = front来判断是否为空是不合理的

所以我们将之看做一个循环的队列，用来解决这种问题

循环队列原理

也就是队列为空的时候rear = front，入队： rear ++， front不变。出队：front++， rear不变。因为是循环队列，就要考虑MAXSIZE的取余运算，以达到合理运算结果，所以队列满的话：(rear + 1)%MAXSIZE= front。循环队列的入队则是（++rear）%MAXSIZE，同样出队则是（++front）%MAXSIZE

好处：
降低了出队时所耗费的时间复杂度，因为队列先进先出的原则，导致在dequeue(出栈操作)时，必须删除队首的元素，后面所有的元素都要往前移动一位，导致时间复杂度为O(n)。如果弄成循环队列，引入front（队首）、rear(队尾)指针，则出队时，后面所有的元素不用动，只要front+1,时间复杂度为O(1); 另一方面：节约了空间，因为当队前面的元素删除时，tail指向队尾后，还可以再从第一个元素循环。 补充：队列为空时，front = rear 队列满时，(rear+1）% length = front 解释: 因为rear+1 <= length，当rear+1 =length时，说明tail在队尾，余 数为0，front为0，队列已满；当rear+1<length时，余数为tail + 1,则rear+1+front = length，队也已满。 注意：循环队列满的时候，rear指向的位置是空的，说明length-1才是实际元素的个数，会有一个空位没有元素

2.链式存储的队列称为链队列。
和链栈类似，链队列可以用单链表来实现，根据队的FIFO原则，为了操作上的方便，可以分别设置一个头指针和一个尾指针。
链式存储相对来说比顺序存储相对来说可以无限链，对于MAXSIZE的考量，仁者见仁智者见智。我这里不做限制。

链式队列

typedef struct Node{
    struct Node* next;
    int data;
}Node;

typedef Node* QueuePtr;

typedef struct {
    QueuePtr rear;
    QueuePtr front;
}LinkQueue;

/// 初始化队列
/// @param queue 队列
int initQueue(LinkQueue* queue){
//    queue = malloc(sizeof(LinkQueue));
//    if (queue == NULL) {
//        return 0;
//    }
    
    Node* fristNode = malloc(sizeof(Node));
    
    if (fristNode == NULL) {
        return 0;
    }
    
    queue->rear = queue -> front = fristNode;

    queue->front->next = NULL;
    return 1;
}

/// 入队
/// @param queue 队列
/// @param data 数据
int in_queue(LinkQueue* queue, int data){
    Node* node = malloc(sizeof(node));
    if (node == NULL) {
        return 0;
    }
    node->data = data;
    node->next = NULL;
//    queue->rear = node;
    queue->rear->next = node;
    queue->rear = node;//修改队尾指针
    
    return 1;
}
//判断队列为空
int queueEmpty(LinkQueue queue){
    return queue.front == queue.rear;
}

/// 清空队列
/// @param queue 队列
int clear_queue(LinkQueue* queue){
    Node* p = queue -> front ->next;
    Node* tem = NULL;
    while (p) {
        tem = p -> next;
        free(p);
        p = tem;
    }
    queue -> front = queue -> rear;
    queue->front->next = NULL;
    return 1;
}

/// 出队
/// @param queue 队列
/// @param e 记录出队的元素
int out_queue(LinkQueue* queue, int *e){
    if (queue->front == queue->rear) {
        return 0;
    }
    Node* tem = queue->front->next;//拿到队的首的元素
    *e = tem->data;
    queue->front->next = tem->next;//将队头的next指向首元素的下一个元素，即第二个元素
    if (queue->rear == tem) {//即里面只有一个元素了，这个元素取完队尾与队首一致
        queue->rear = queue->front;
    }
    free(tem);
    return 1;
}

/// 队长度
/// @param queue 队列
int queue_length(LinkQueue queue){
    QueuePtr p = queue.front;
    int i = 0;
    while (queue.rear != p) { //不能简单的用p != null来l判断，至于为什么自己想
        i++;
        p = p->next;
    }
    return i;
    
}

/// 销毁队列
/// @param queue 队列
int destoryQueue(LinkQueue* queue){
    Node * p = queue->front;
    Node * tmp = NULL;
    while (p) {
        tmp = p ->next;
        free(p);
        p = tmp;
    }
    queue -> front = queue->rear;
    return 1;
}

/// 遍历队
/// @param queue 队列
int traverseQueue(LinkQueue* queue){
    if (queue == NULL) {
        return 0;
    }
    Node* p = queue->front->next;
//    Node* tem = NULL;
    while (p) {
        printf("%d ", p->data);
        p = p -> next;
    }
    printf("\n");
    return 1;
}