《数据结构》—— 队列-白红宇

本文内容，参考自《大话数据结构》(程杰著) ，一部分自己修改，如：把C语言换成了Java语言。写作目的，意在加强记忆。

本文写作工具，使用 Typora。

你们在用电脑时有没有经历过，机器有时会处于疑似死机的状态，点击什么都没用，双击任何快捷方式都不动弹。就当你失去耐心，打算重启时。突然它像酒醒了一样，把你刚才的所有操作都按顺序执行了一次。

操作系统，就是应用了一种数据结构来实现刚才提到的先进先出的排队功能，这就是队列。

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出 (Frist In Frist Out) 的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

循环队列

线性表有顺序存储和链式存储，栈是线性表，所以有这两种存储方式。同样，队列作为一种特殊的线性表，也同样存在这两种存储方式。

我们假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即为队头。所谓的入队列操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为O(1)。

与栈不同的是，队列元素的出队列是在队头，即下标为0的位置，那就意味着，队列中的所有元素都得向前移动，以保证队列的队头，也就是下标为0的位置不为空，因此时间复杂度为O(n)。

为了解决这问题，我们需要循环队列。

循环队列是指头尾相接的顺序存储结构。

循环队列，有几个重要概念：

front：指向队头元素位置

rear：指向队尾元素的下一个位置

QueueSize：队列最大长度

空队列：当 front == rear 时，为空

队列满：(rear+1) % QueueSize = front

队列长度：(rear - front + QueueSize) % QueueSize

循环队列代码

public class Queue {        int MAXSIZE;    int front;    int rear;    int[] data;        public Queue() {        MAXSIZE = 5;        front = 0;        rear = 0;        data = new int[MAXSIZE];    }        //队列长度    public int length() {        return (rear-front+MAXSIZE) % MAXSIZE;    }        //插入元素    public boolean insert(int e) {        //判断队列是否已经满        if((rear+1)%MAXSIZE == front) {            return false;        }                data[rear] = e;//将元素e赋值给队尾        rear = (rear+1) % MAXSIZE;//rear向后移动一个位置，若到最后则转到数组头部                return true;    }        //删除元素    public boolean delete() {        //判断队列是否为空        if(front == rear) {            return false;        }                front = (front+1) % MAXSIZE;//front向后移动一个位置，若到最后则转到数组头部                return true;    }    }复制代码

队列的链式存储结构及实现

**队列的链式结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。**为了操作上的方便，我们将队头指向链队列的头结点，而队尾指向终端结点。空队列时，front 和 rear 都指向头结点。

链队列代码

public class QueueNode {        int data;    QueueNode next;    }public class LinkedQueue {        QueueNode front;    QueueNode rear;        //插入元素    public void insert(int e) {                QueueNode n = new QueueNode();        n.data = e;        n.next = null;        rear.next = n;        rear = n;            }        //删除元素    public boolean delete() {        if(front == rear) {            return false;        }        QueueNode n = front.next;        front.next = n.next;        if(rear == n) {            rear = front;        }        n = null;        return true;    }    }复制代码

对于循环队列与链队列的比较，可以从两方面来考虑，从时间上，其实它们的基本操作都是常数时间，即都为O(1)，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有差异的。对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。

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