• 今天要学习的队列,也是一种线性结构,他包括两类

  • 顺序队列:即使用一组地址连续的内存单元依次保存队列中的数据
  • 链式队列:即使用链表形式保存队列中各元素的值
• 队列用图来表示就是这样的

• 从图中可以看出,队列允许在两端进行操作,一段进行添加操作,称为队尾,以便进行删除操作称为队头,他遵循了先进先出FIFO(first in first out)的规则,那这是什么意思呢?拿生活中的例子就是排队,先来的拍前面,前面的先接受服务

• 从上面也可以看出来,队列的基本操作只有两种

  • 入队:就是将元素添加到队尾
  • 出队:就是将队头的元素移出
• 那么我们来看的一下队列的入队出队流程

• 注意:上图的添加顺序是按照数字的大小顺序添加的,而非从右到左添加的:即添加顺序为0>1>2>3>4>5>6,而不是类似压入栈的顺序:6>5>4>3>2>1>0

• 如上就反映出来一个问题:随着出队和入队的操作,tail指针一直在往后移,也就导致了整个队列在"假变小",因为入队只能在一端进行,所以tail就一直往后移,导致了前面的出队后的位置不能再次利用,那么我们应该怎么去解决这个问题

  • 我的想法是:head从0开始计算,数组的Max_Size是最大下标加一的值,所以当head==Max_Size的时候,就代表了head指针已经到数组外了,那么就代表数组内元素全部取完了,是一个空队列,在这个时候,将head和tail都恢复到空队列状态
  • 如上图,当tail到达末尾,而head之前有一个空位置,这个现象造成的原因就是先将队列插满,然后取出一个,当遇到这种情况下,在执行插入元素的时候,是插入不进去的,因为tail到达末尾了,所以我们将head到tail之间的元素移动到最前方位置,然后更改head和tail的指针即可,这时候后面就会空出一个位置让新元素插入进来,如下图

• 知道了基本的入队出队规律,下面就是代码实现

顺序队列

import java.util.Arrays; public class MyQueue<T> { //头指针 private int head; //尾指针 private int tail; //默认大小 private final int MAX_SIZE ; //存放数据的数组 private Object[] elementData; public MyQueue() { this.MAX_SIZE = 5; elementData = new Object[MAX_SIZE]; } public MyQueue(int init_size) { this.MAX_SIZE = init_size; elementData = new Object[MAX_SIZE]; } //添加tail public void put(T element){ //代表空队列 if (head == MAX_SIZE){ //将头指针和尾指针都恢复到空队列状态 tail = 0; head = 0; } //代表tail已经添加到队列末尾了 if (tail == MAX_SIZE){ //不等于0就说明head前面已经有取出的元素了,代表有可用位置 if (head != 0){ //临时数组 Object[] temp = new Object[MAX_SIZE]; //将元素拷贝到临时数组的开始位置,排除原来数组之前的可以空位置 System.arraycopy(elementData,head,temp,0,tail - head); //拷贝完成赋值 elementData = temp; //tail就是指向数组有效元素的最后一个下标 tail = MAX_SIZE - head; //既然已经将数组元素移动到最开始了,那么head肯定是指向最开始的位置了 head = 0; //然后将本次数据存放在数组最后一个元素中 elementData[tail] = element; //tail后移 tail ++; return; } //代表head=0并且tail等于最大值,那么就说明存满了 throw new RuntimeException("队列已满"); } //正常存放 elementData[tail] = element; tail ++; } //拿出head public T get(){ //空的 if (head >= tail){ return null; } //取出头元素 T element = (T) elementData[head]; //释放头元素位置空间 elementData[head] = null; //head后移 head ++; //返回数据 return element; } @Override public String toString() { return Arrays.toString(elementData) + head + " : " + tail; } }

• 测试

  public static void main(String[] args) { MyQueue<Integer> queue = new MyQueue<>(); queue.put(1); System.out.println(queue); queue.put(2); System.out.println(queue); queue.put(3); System.out.println(queue); queue.put(4); System.out.println(queue); queue.put(5); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.put(6); System.out.println(queue); queue.put(7); System.out.println(queue); queue.put(8); System.out.println(queue); queue.put(9); System.out.println(queue); queue.put(10); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); System.out.println("-----------------------"); queue.put(11); System.out.println(queue); queue.put(12); System.out.println(queue); queue.put(13); System.out.println(queue); }

• 结果

  [1, null, null, null, null]0 : 1 [1, 2, null, null, null]0 : 2 [1, 2, 3, null, null]0 : 3 [1, 2, 3, 4, null]0 : 4 [1, 2, 3, 4, 5]0 : 5 [null, 2, 3, 4, 5]1 : 5 [null, null, 3, 4, 5]2 : 5 [null, null, null, 4, 5]3 : 5 [null, null, null, null, 5]4 : 5 [null, null, null, null, null]5 : 5 [6, null, null, null, null]0 : 1 恢复操作 [6, 7, null, null, null]0 : 2 [6, 7, 8, null, null]0 : 3 [6, 7, 8, 9, null]0 : 4 [6, 7, 8, 9, 10]0 : 5 [null, 7, 8, 9, 10]1 : 5 [null, null, 8, 9, 10]2 : 5 [null, null, null, 9, 10]3 : 5 ----------------------- [9, 10, 11, null, null]0 : 3 迁移操作 [9, 10, 11, 12, null]0 : 4 [9, 10, 11, 12, 13]0 : 5

链式队列

• 链式结构就不存在可用空位置了,只要取出直接改变引用即可,同样需要头指针和尾指针,下面是代码实现

  public class MyLinkedQueue<T> { private int size; private Node<T> head; private Node<T> tail; private class Node<T>{ private T element ; private Node<T> next; public Node(T element, Node<T> next) { this.element = element; this.next = next; } @Override public String toString() { return String.valueOf(element); } } public MyLinkedQueue() { head = new Node<>(null,null); tail = new Node<>(null,null); } //入队 public void put(T element){ //代表空链表 if (head.next == null){ head.next = new Node<>(element,null); tail = head.next; return; } Node<T> node = new Node<>(element,null); tail.next = node; tail = tail.next; size ++; } //出队 public T get(){ if (head.next == null) { return null; } Node<T> next = head.next; head = head.next; size --; return (T) next; } public int getSize() { return size; } @Override public String toString() { StringBuilder builder = new StringBuilder(); builder.append("["); for (Node<T> node = head.next ; node != null ; node = node.next){ builder.append(node.toString()+" "); } return builder.toString(); } }

• 测试

  public static void main(String[] args) { MyLinkedQueue<Integer> queue = new MyLinkedQueue<>(); queue.put(1); queue.put(2); queue.put(3); queue.put(4); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.get(); System.out.println(queue); queue.put(5); System.out.println(queue); queue.put(6); System.out.println(queue); System.out.println(queue.get()); }

• 结果

  [1 2 3 4 [2 3 4 [3 4 [4 [ [ [5 [5 6 5