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

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

• 从图中可以看出,队列允许在两端进行操作,一段进行添加操作,称为队尾,以便进行删除操作称为队头,他遵循了先进先出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