一、什么是队列

  队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(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    }

标题:队列(先进先出表)
作者:Yi-Xing
地址:http://zyxwmj.top/articles/2020/03/03/1583243431118.html
博客中若有不恰当的地方,请您一定要告诉我。前路崎岖,望我们可以互相帮助,并肩前行!