前文

需要看本系列其他文章的请转到：

(一)Android数据结构学习之链表
(二)Android数据结构学习之数组
(三)Android数据结构学习之队列
(四)Android数据结构学习之栈

今天的文章我们来一起学习一下数据结构之队列。

正文

对于队列稍有耳闻的同学肯定会知道它有一个特点：先进先出。正是这个特点使得队列在处理一些对于顺序要求很高的需求时有很好的效果，就像网络请求的排序，队列大概是这样的：

上图可以队列是一个很明显的先进先出的结构，中间的元素是不允许修改的。

java中使用Queue来描述队列，它里面有一系列方法：
- offer方法，向队列尾部入列一个元素;
- poll方法，把队列的第一个元素出列;
- peek方法，查看队列的第一个元素，但是不出列。

除了上面3个方法，其实还有3个方法：add，remove，element与上面3个方法对应，唯一的区别就是这3个方法会抛出异常，这不是我们关注的重点，所以我们跳过。

java种关于Queue的实现结构如下：

其中：
- PriorityQueue虽然是Queue的实现类，但是它的实现与队列的“先进先出”特点是有些出入的，因为它会对每次进入队列的元素进行排序，也就是说当使用peek方法取出来的元素可能不会是第一个进入队列的元素，而是整个队列中最小的元素。
- Deque是一个继承了Queue的接口，它在Queue的基础上增加了几个方法，使它成为了一个双端队列的结构，可以通过这些方法来操作队列两端的元素
- ArrayDeque是Deque的一个典型实现。
- LinkedList，哈哈哈，又遇到它了，在我们数据结构系列文章中的第一篇提到过它，当时是把它当做链表来讲解的，其实它还实现了Deque，也就是说它还可以当做双端队列来使用。

既然java没有给我们提供一个规范的队列实现，我们就自己动手来写一个遵循”先进先出“规则的简单队列，毕竟我们学习数据结构更多的是理解这些数据结构的特点，而不是过多的关心它的实现。

public class Queue {    private Object[] data = null;// 队列    private int front;// 队列头，允许删除    private int rear;// 队列尾，允许插入    public Queue() {        this(10);// 默认队列的大小为10    }    public Queue(int initialSize) {        data = new Object[initialSize];        front = rear = 0;    }    // 入列一个元素    public void offer(E e) {        data[rear++] = e;    }    // 返回队首元素，但不删除    public E peek() {        return (E) data[front];    }    // 出队排在最前面的一个元素    public E poll() {        E value = (E) data[front];// 保留队列的front端的元素的值        data[front++] = null;// 释放队列的front端的元素        return value;    }}

来测试一下：

Queue<String> queue = new Queue<>();queue.offer("1");queue.offer("2");queue.offer("3");queue.offer("4");System.out.println("当前第一个元素: " + queue.peek());// 取队列第一个元素System.out.println("出列第一个元素: " + queue.poll());// 出列第一个元素System.out.println("当前第一个元素: " + queue.peek());// 取队列第一个元素

结果如下：

当前第一个元素: 1出列第一个元素: 1当前第一个元素: 2

代码很简单，没有做异常处理和各种边界处理，但是遵循了“先进先出的原理”。

(三)Android数据结构学习之队列

前文

正文

更多相关文章

随机推荐