队列（先进先出表）

一、什么是队列

  队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
  队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

二、定义队列接口

  队列是一种特殊的线性表，所以队列的接口也继承我们之前定义的 IQueue 接口，IQueue 接口包含一些队列的基本操作。

 1public interface IQueue<T> extends MyList<T> {
 2    /**
 3     * 入队
 4     */
 5    void enqueue(T e);
 6
 7    /**
 8     * 出队
 9     */
10    T dequeue();
11
12    /**
13     * 返回队列的大小
14     */
15    @Override
16    int getSize();
17
18    /**
19     * 判断队列是否为空
20     */
21    boolean empty();
22
23    /**
24     * 取队首元素
25     */
26    T peek();
27}

三、队列的实现

  数据的存储结构有两种：顺序存储结构和链式存储结构。队列只能对队首和队尾进行操作（入队/出队），所以底层的存储结构用链表比数组更好些。为了方便获取元素的前驱，我们使用双链表来实现队列。我们只需要将队列的实现类继承 DoubleLinkedList 类就可以使用双链表进行存储栈的数据了。（DoubleLinkedList 类是我们上一篇双链表的实现类）

1public class MyQueue<T> extends DoubleLinkedList<T> implements IQueue<T> {
2}

1、入队

  入队就是向队尾添加元素，等同于向链表末尾添加元素，所以我们只需要调用双链表的 add 方法即可。

1    @Override
2    public void enqueue(T e) {
3        super.add(e);
4    }

2、出队

  出栈包含两个操作：获取队首元素并将其删除；也就是获取链表的头结点并将其删除。

 1    @Override
 2    public T dequeue() {
 3        ListNode<T> head = first.next;
 4        // 将头部的哑元指向第二个节点
 5        first.next=head.next;
 6        // 第二个节点指向哑元
 7        head.next.pre = first;
 8        head.pre = null;
 9        head.next = null;
10        size--;
11        return head.data;
12    }

3、其他方法

  MyQueue 类完整的代码如下：

 1public class MyQueue<T> extends DoubleLinkedList<T> implements IQueue<T> {
 2    @Override
 3    public void enqueue(T e) {
 4        super.add(e);
 5    }
 6
 7    @Override
 8    public T dequeue() {
 9        ListNode<T> head = first.next;
10        // 将头部的哑元指向第二个节点
11        first.next = head.next;
12        // 第二个节点指向哑元
13        head.next.pre = first;
14        head.pre = null;
15        head.next = null;
16        size--;
17        return head.data;
18    }
19
20    @Override
21    public boolean empty() {
22        return getSize() == 0;
23    }
24
25    @Override
26    public T peek() {
27        return first.next.data;
28    }
29}

四、关于队列的练习题

1、用两个栈来实现一个队列

 1/**
 2 * 用两个栈来实现一个队列，完成队列的push和pop操作，对列中的元素类型为Integer
 3 **/
 4public class MyQueue {
 5    Stack<Integer> stack1 = new Stack<>();
 6    Stack<Integer> stack2 = new Stack<>();
 7
 8    /**
 9     * 入队
10     */
11    public void enqueue(int node) {
12        if (stack1.isEmpty()) {
13            move(stack2, stack1);
14        }
15        stack1.push(node);
16    }
17
18    /**
19     * 出队
20     */
21    public int dequeue() {
22        if (stack2.isEmpty()) {
23            move(stack1, stack2);
24        }
25        return stack2.pop();
26    }
27
28    /**
29     * 将source栈中的元素装入target队列中
30     */
31    private void move(Stack<Integer> source, Stack<Integer> target) {
32        while (!source.empty()) {
33            target.push(source.pop());
34        }
35    }
36}

2、动物收容所

  有家动物收容所只收留猫和狗，但有特殊的收养规则，收养人有两种收养方式。

• 第一种为直接收养所有动物中最早收入收容所的动物。
• 第二种为选着收养的动物类型（猫或狗），并收养该种动物中最早进入收容所的。

  给定一个操作序列 int[][2] ope 代表所有时间。

• 若第一个元素为 1，则代表有动物进入收容所，第二个元素为动物的编号，正数代表狗，负数代表猫。
• 若第一个元素为 2，则代表有人收养动物，第二个元素若为 0，则采取第一种收养方式（最早）。若为 1，则指定收养狗，若为 -1 则指定收养猫。

  请按顺序返回收养的序列，若出现不合法的操作，即没有可以符合领养要求的动物，则将这次领养操作忽略。

例子：

• 输入：[[1, 1], [1, -1], [2, 0], [2, -1]]
• 输出：[1, -1]

 1public static ArrayList<Integer> asylum(int[][] ope) {
 2        // 保存结果
 3        ArrayList<Integer> res = new ArrayList<>();
 4        // 用队列记录所有的猫
 5        Queue<Animal> cats = new LinkedList<>();
 6        // 用队列记录所有狗
 7        Queue<Animal> dogs = new LinkedList<>();
 8        // 遍历操作序列
 9        for (int[] row : ope) {
10            int op = row[0];
11            int typeNumber = row[1];
12            if (op == 1) {
13                // 添加动物
14                if (typeNumber > 0) {
15                    // 添加狗
16                    dogs.add(new Animal(typeNumber));
17                }
18                if (typeNumber < 0) {
19                    // 添加猫
20                    cats.add(new Animal(typeNumber));
21                }
22            } else if (op == 2) {
23                // 减少动物
24                // 从两个队列中选 timeline 最小的
25                if (typeNumber == 0) {
26                    // 得到狗和猫最早进入收容所的
27                    // 狗不为空 且（猫为空 或 狗进的时间比猫早）
28                    if ((!dogs.isEmpty()) && (cats.isEmpty() || dogs.peek().time < cats.peek().time)) {
29                        res.add(dogs.poll().type);
30                        // 狗不满足条件，只要猫不为空就取猫
31                    } else if ((!cats.isEmpty())) {
32                        res.add(cats.poll().type);
33                    }
34                } else {
35                    // 用户指定了类型
36                    if (typeNumber == 1 && !dogs.isEmpty()) {
37                        res.add(dogs.poll().type);
38                    } else if (typeNumber == -1 && !cats.isEmpty()) {
39                        res.add(cats.poll().type);
40                    }
41                }
42            }
43        }
44        return res;
45    }