数据结构（3）：队列的原理和实现

完整代码拉到最底下

一、介绍

队列顾名思义就像我们生活中排队一样，先进先出。

如上图所示，25、16、5、9依次在队列中，按照顺序拿出的数据也分别是25、26、5、9。

二、实现过程及思路

底层使用数组来实现，实现的功能有插入数据到队尾、移除队首数据、查看队首数据、判断队列是否为空、判断队列是否存满。

将队列的元素存储在数组的某个区间内，队列在数组中是连续的，所以使用变量标记队列在数组中的位置。

1、编写类及属性

我们可以使用elements变量标记队列中元素的数量，使用front变量标记队首元素在数组的索引，end变量标记队尾元素在数组中的索引。

public class MyQueue { private Object[] arr;//存放队列元素的数组 private int elements;//队列元素数量 private int front;//队头元素在数组中的索引 private int end;//队尾元素在数组中的索引 public MyQueue() { arr = new Object[10]; elements = 0; front = 0; end = -1; } public MyQueue(int maxSize) { arr = new Object[maxSize]; elements = 0; front = 0; end = -1; } }

2、队列是否为空

标记队列元数量的变量 elements 为 0 即为空

public boolean isEmpty() { return elements == 0; }

3、队列是否已经满了

队列元素个数与数组的长度相等即为满

public boolean isFull() { return elements == arr.length; }

4、获取队头元素

获取数组中索引为 front的元素

public Object peek() { return arr[front]; }

5、移除队首元素

每次都是移除数组中索引为 front 的元素，下一个元素就变成了队首，即front+1，队列元素个数elements-1。共有三种情况要考虑，如果队列已经空了就无须做任何操作，如果已经是最后一个元素，直接将标记位置的变量重置即可，其他情况正常操作。

public Object remove() { if (isEmpty()) { throw new RuntimeException("队列已经是空的，放心使用吧"); } Object value = arr[front++]; //如果已经是最后一个元素了,将指针重置即可 if (elements == 1) { end = -1; front = 0; elements = 0; } else { elements--; } return value; }

6、插入

我们编写一个持续可用的队列，所以要考虑到以下情况。

(1)存储队列的数组满了(队列满了)，这个好理解，满了就无法向队尾加入元素了。

(2)因为队列在数组中是连续的，如果队列的元素在数组中最后，需要将元素从队首到队尾移到数组中第一位，也就是将后面的位置空出来(参考下图)。

public void insert(Object value) { //检测队列是否已经满了 if (isFull()) { throw new RuntimeException("队列内元素已达到设定长度"); } //如果后面没有空位置，将余下元素放到数组的头 if (elements > 1 && end == arr.length - 1) { int i = 0; for (; i < elements; i++, front++) { arr[i] = arr[front]; } front = 0; end = i-1; } //其他情况正常向后添加元素 arr[++end] = value; elements++; }

7、测试

public static void main(String[] args) { MyQueue queue = new MyQueue(4); queue.insert(11); queue.insert(12); queue.insert(13); queue.insert(14); queue.remove(); queue.remove(); queue.insert(16); //queue.remove(); //queue.remove(); //queue.insert(19); //queue.insert(20); queue.remove(); queue.remove(); queue.insert(21); queue.insert(22); while (!queue.isEmpty()) { System.out.println(queue.remove()); } }

三、完整代码

package com.jikedaquan.datastruct; public class MyQueue { private Object[] arr; private int elements;//队列元素数量 private int front;//队头元素在数组中的索引 private int end;//队尾元素在数组中的索引 public MyQueue() { arr = new Object[10]; elements = 0; front = 0; end = -1; } public MyQueue(int maxSize) { arr = new Object[maxSize]; elements = 0; front = 0; end = -1; } //从队尾插入 public void insert(Object value) { //检测队列是否已经满了 if (isFull()) { throw new RuntimeException("队列内元素已达到设定长度"); } //如果后面没有空位置，将余下元素放到数组的头 if (elements > 1 && end == arr.length - 1) { int i = 0; for (; i < elements; i++, front++) { arr[i] = arr[front]; } front = 0; end = i-1; } arr[++end] = value; elements++; } //删除数据，从队头删除 public Object remove() { if (isEmpty()) { throw new RuntimeException("队列已经是空的，放心使用吧"); } Object value = arr[front++]; //如果已经是最后一个元素了,将指针重置即可 if (elements == 1) { end = -1; front = 0; elements = 0; } else { elements--; } return value; } //查看数据，从队头查看 public Object peek() { return arr[front]; } //判断是否为空 public boolean isEmpty() { return elements == 0; } public boolean isFull() { return elements == arr.length; } public static void main(String[] args) { MyQueue queue = new MyQueue(4); queue.insert(11); queue.insert(12); queue.insert(13); queue.insert(14); queue.remove(); queue.remove(); queue.insert(16); // queue.remove(); // queue.remove(); // queue.insert(19); // queue.insert(20); queue.remove(); queue.remove(); queue.insert(21); queue.insert(22); while (!queue.isEmpty()) { System.out.println(queue.remove()); } } }