数据结构-队列 queue

队列

队列的基本概念

队列是有限个同类型元素的线性序列
队列也是一种运算受限的线性表，而且是先进先出的线性表 FIFO
新加入的数据元素加入在队尾，出队列的数据元素在队列首部被删除

如下图所示

屏幕快照 2019-04-24 16.49.55.png

队列的基本运算

队列初始化
队列判空
入队
出队
取队列首元素
清空队列
销毁队列
获取队列长度

队列的两种存储结构

顺序存储

先看一个图：

屏幕快照 2019-04-24 17.24.59.png

从上图看出，随着队列的入队、出队进行，会使整体队列向上移动（也就是向后移动），当队尾指针指向最上端的存储区域时，就不能入队了，再入队会出现溢出，但是实际上队列中还有空余空间；这种现象称为"假溢出"。
解决假溢出的方法：

方法一：每次队列出队时，让队列整体向前移动一个位置，这样就保证了队首元素始终在最前边（存储空间的首个元素地址）；但是这样每次都需移动N个元素，平均时间复杂度为O(n)；效率低
方法二：当队尾出现溢出时，可判断头指针位置，如果前边有空余位置，则把当前队列整体前移，这样可减少元素的移动次数，可以看做是方法一的优化；
方法三：引入循环队列的概念。可以将队列看成首尾相接的循环结构，当队尾指针到队尾后，再从头指针开始；这种方法就不需要移动元素了，这种顺序队列称为循环队列。

循环队列

当使用了循环队列，入队的队尾指针加1操作及出队的队首指针加1操作要做响应的修改，当front==rear时，有可能是空队列，也有可能队列已满，为了区分开，队列最多可容纳maxsize-1个元素。

循环队列 C语言实现

const int maxsize = 10;

typedef struct queue {
    int front;
    int rear;
    int data[maxsize];//数据为int类型
}CycleQueue;

1、队列初始化

CycleQueue *initCycleQueue() {
    CycleQueue *queue = (CycleQueue *)malloc(sizeof(CycleQueue));
    queue->front = 0;
    queue->rear = 0;
    return queue;
}

2、队列判空

int emptyQueue(CycleQueue *queue) {
    if (queue->front == queue->rear) {
        return 1;
    }
    return 0;
}

3、入队

int enQueue(CycleQueue *queue,int x) {
    if ((queue->rear+1) % maxsize == queue->front) {
        printf("队列已满");
        return 0;
    } else {
        queue->rear = (queue->rear+1) % maxsize;
        queue->data[queue->rear] = x;
        return 1;
    }
}

4、出队

int outQueue(CycleQueue *queue) {
    if (emptyQueue(queue)) {
        printf("队列为空");
        return 0;
    } else {
        queue->front = (queue->front+1) % maxsize;
        return 1;
    }
}

5、取队列首元素

int getFirst(CycleQueue *queue) {
    if (emptyQueue(queue)) {
        printf("队列为空");
        return -1;
    } else {
        return queue->data[queue->front+1];
    }
}

6、清空队列

void clearQueue(CycleQueue *queue) {
    queue->front = 0;
    queue->rear = 0;
}

7、销毁队列

void destoryQueue(CycleQueue *queue) {
    free(queue);
    queue = NULL;
}

8、获取队列长度

int lengthQueue(CycleQueue *queue) {
    return (queue->rear-queue->front+maxsize) % maxsize;
}

链队列

1、初始化

LinkQueue *initLinkQueue(void) {
    LinkQueue *queue = (LinkQueue *)malloc(sizeof(LinkQueue));
    LinkQueueNode *node = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
    node->next = NULL;
    queue->front = node;//队列头指针指向头结点
    queue->rear = node;//队列尾指针指向尾结点
    return queue;
}

2、判空

int emptyLinkQueue(LinkQueue *queue) {
    if (queue->front == queue->rear) {
        return 1;
    }
    return 0;
}

3、入队

void enLinkQueue(LinkQueue *queue,int x) {
    LinkQueueNode *node = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
    node->data = x;
    node->next = NULL;
    queue->rear->next = node;//上个尾结点的下一结点为新加入的结点
    queue->rear = node;//重新指向尾结点
}

4、出队

void outLinkQueue(LinkQueue *queue) {
    if (emptyLinkQueue(queue)) {
        printf("队列为空");
    } else {
        LinkQueueNode *node = queue->front->next;
        queue->front->next = node->next;
        if (node->next == NULL) {
            queue->rear = queue->front;//无首结点，首尾指向头结点
        }
        free(node);
    }
}

5、获取首元素

int getFirstLinkQueue(LinkQueue *queue) {
    if (emptyLinkQueue(queue)) {
        printf("队列为空");
        return -1;
    } else {
        LinkQueueNode *node = queue->front->next;
        return node->data;
    }
}

6、获取队列长度：可添加一个变量 count，这样就不用每次都遍历一遍

int lengthLinkQueue(LinkQueue *queue) {
    int k = 0;
    if (emptyLinkQueue(queue)) {
        return k;
    }
    LinkQueueNode *node = queue->front->next;
    while (node != NULL) {
        k++;
        node = node->next;
    }
    return k;
}

7、清空队列

void clearLinkQueue(LinkQueue *queue) {
    if (!emptyLinkQueue(queue)) {
        LinkQueueNode *p,*q;
        p = queue->front->next;
        queue->front->next = NULL;//头结点指向null
    
        while (p) {//销毁结点
            q = p->next;
            free(p);
            p = q;
        }
        queue->rear = queue->front;//都指向头结点
    }
}

8、销毁队列

void destoryLinkQueue(LinkQueue *queue) {
    while (queue->front) {//销毁内部结点
        queue->rear = queue->front->next;
        free(queue->front);
        queue->front = queue->rear;
    }
}

顺序队列与链队列的优缺点

顺序队列需要预留出空间，而链队列不需要
链队列没有容量限制
链队列除了销毁和清空队列时间复杂度为O(n),其余均为O(1)
顺序队列所有操作时间复杂度均为O(1)
顺序队列存在假溢出现象，需要使用环形队列来避免