队列定义

同样也是操作受限的线性表，底层也是基于数组实现，但顺序是先进先出FIFO，从队尾进队，从队头出队

队列分为：

• 顺序队列
• 循环队列
• 链式队列
• 双端队列

顺序队列

顺序队列的特征：

• 队头指针指向第一个元素
• 队尾指针一般指向最后一个元素的下一个位置

进队：先送值到队尾，再将队尾指针+1

Q.data[Q.rear] = x;
rear ++;

出队：先取出队头元素，再将队头指针+1

x = Q.data[Q.front]
front ++;

顺序队列存在的问题 ：会导致上溢出；是一种 假溢出 ，在data数组中任然存在可以存放数组的位置

解决方法：

• 建立一个足够大的存储空间以避免溢出，但这样做空间使用率低，浪费存储空间
• 移动元素：每当出队一个元素，就将移动队列中所有的已有元素向队头移动一个位置
• 循环队列：将队头和队尾看作是一个首尾相接的循环队列

循环队列

循环队列可以弥补顺序队列的缺点，其定义是：

1. 队列长度固定，即队列容量有限
2. 队列的头尾相接形成一个环，当队尾到达数组的最后一个位置时，下一个位置是数组的第一个位置

具体实现步骤如下：

1. 定义一个数组和两个指针：front 和 rear，分别表示队头和队尾的位置。初始时，队头和队尾都指向数组的第一个位置，即 front = rear = 0。
2. 入队时，首先检查队列是否已满，即 rear+1 是否等于 front。如果满了则返回错误，否则将元素添加到队尾，即 data[rear] = element，然后将 rear 指针向后移动一位，即 rear = (rear + 1) % capacity。
3. 出队时，首先检查队列是否为空，即 front 是否等于 rear。如果为空则返回错误，否则将队头元素取出并返回，即 element = data[front]，然后将 front 指针向后移动一位，即 front = (front + 1) % capacity。
4. 在队列的任何时刻，队列中的元素数量为 (rear - front + capacity) % capacity。
5. 如何判断队列满？牺牲一个单元来区分队空和队满：(rear + 1) % maxsize = front

以下是一个基于数组实现循环队列的 Java 代码示例：

public class CircularQueue {
    private int[] data;
    private int front, rear;
    private int capacity;

    public CircularQueue(int k) {
        capacity = k;
        data = new int[capacity];
        front = 0;
        rear = 0;
    }

    public boolean enqueue(int element) {
        if (isFull()) {
            return false;
        } else {
            data[rear] = element;
            rear = (rear + 1) % capacity;
            return true;
        }
    }

    public boolean dequeue() {
        if (isEmpty()) {
            return false;
        } else {
            front = (front + 1) % capacity;
            return true;
        }
    }

    public int front() {
        if (isEmpty()) {
            return -1;
        } else {
            return data[front];
        }
    }

    public int rear() {
        if (isEmpty()) {
            return -1;
        } else {
            return data[(rear - 1 + capacity) % capacity];
        }
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }
}

简单总结就是：

• 初始/队空：Q.front = Q.rear (队空条件）
• 出队：Q.front = (Q.front+1) % maxsize (最大元素个数)
• 进队：Q.rear = (Q.rear+1) % maxsize
• 队列长度 = (Q.rear - Q.front + maxsize) % maxsize
• 队满：( 牺牲一个单元来区分队空和队满 ）(Q.rear + 1) % maxsize = Q.front

链式队列

实际就是一个同时带有头指针和尾指针的单链表

头指针指向队头结点，尾指针指向队尾结点（即单链表最后一个结点，与顺序存储有所不同）

适合于数据元素变动较大的情况，而且不存在队列满或者溢出的问题。

• 队空： Q.rear == Q.front == NULL
• 出队：（带头结点）

LinkNode *p = Q.front->next;
x = p->data;
Q.front->next = p->next; //插入头节点之后
if(Q.rear = p) //若原队列中只有一个结点，删除后变空，还需修改尾指针
    Q.rear = Q.front;
free(p);

• 进队：（带头节点）

LinkNode *s = (LinkNode *) malloc (sizeof(LinkNode)); //创建新结点
s->data = x; s->next = NULL;
Q.rear->next = s; //插入到表尾
Q.rear = s;

双端队列

允许两端都进行入队和出队操作的队列

• 输出受限：有一端允许插入和删除；另一端只允许插入
• 输入受限：有一端允许插入和删除；另一端只允许删除

队列的应用

• 层次遍历
• 计算机系统中的应用
• 解决主机与外部设备之间速度不匹配的问题（ex:打印机数据缓冲区中所存储的数据就是一个队列）
• 解决由多用户引起的资源竞争问题（CPU将请求按时间先后排成队列）