队列

https://github.com/toyranger/DataStructureAlgorithm.git

1. 什么是队列

先进先出
可以使用数组或者链表来实现

image.png

front 队列头，随着数据输出而改变
rear队列尾，随着数据输入而改变

2. 数组模拟队列

addQueue

1. 将rear向后移动，rear + 1，当front == rear时队列为空
2. 若rear小于maxSize - 1，则将数据存入rear所指向的元素位置，否则无法存入数据，rear = maxSize - 1为队列满
   rear 是队列最后（含）
   front是队列最前元素（不含）

package com.ds.queue;

public class ArrayQueue {

  private int maxSize;
  private int front;
  private int rear;
  private int[] arr; //数组用于存放数据，模拟队列

  /***
   * 构造器
   * @param queueSize
   */
  public ArrayQueue(int queueSize) {
    maxSize = queueSize;
    arr = new int[queueSize];
    front = -1;
    rear = -1;
  }

  /***
   * 判满
   * @return
   */
  public boolean isFull() {

    return rear == maxSize - 1;
  }

  /***
   * 判空
   * @return
   */
  public boolean isEmpty() {
    return front == rear;
  }

  /***
   * 添加元素
   * @param elem
   */
  public void addElemToQueue(int elem) {

//    判断是否满
    if (isFull()) {
      System.out.println("队列满。");
      return;
    }

    rear++;
    arr[rear] = elem;
  }

  /***
   * 取数据
   * @return
   */
  public int getElemFromQueue() {

//    判空
    if (isEmpty()) {
//      这里不抛异常的话，不知道怎么处理return
      throw new RuntimeException("队列空");
    }

    front++;
    return arr[front];

  }

  /***
   * 打印队列
   */
  public void printQueue() {

   if (isEmpty()) {
            System.out.println("队列空的，没有数据~~");
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d\n", i, arr[i]);
        }

  }

  /***
   * 显示队列头数据
   * @return
   */
  public int getHeader() {

    return arr[front + 1];
  }
}

测试代码：

package com.ds.queue;

import java.util.Scanner;

public class Test {

  public static void main(String[] args) {

    ArrayQueue arrayQueue = new ArrayQueue(3);
    char key = ' '; // 用户输入
    Scanner scanner = new Scanner(System.in);

    boolean loop = true;

    while (loop) {

      System.out.println("s(show): 显示队列");
      System.out.println("e(exit): 退出程序");
      System.out.println("a(add): 添加数据");
      System.out.println("g(get): 取出数据");
      System.out.println("h(head): 查看队列头数据");
      System.out.println("-------------------------");

      key = scanner.next().charAt(0); // 接收第一个字符
      switch (key) {
        case 's':
          arrayQueue.printQueue();
          break;
        case 'a':
          System.out.println("输入一个数：");
          int anInt = scanner.nextInt();
          arrayQueue.addElemToQueue(anInt);
          break;
        case 'g':
          try {
            int res = arrayQueue.getElemFromQueue();
            System.out.printf("取出的数是：%d\t", res);
          } catch (Exception e) {
            System.out.println(e);
          }
          break;
        case 'h':
          try {
            int header = arrayQueue.getHeader();
            System.out.printf("队列头是： %d\t", header);
          } catch (Exception e) {
            System.out.println(e);
          }
          break;
        default:
          break;
      }
    }
  }
}

这样写并不合理，因为即使取出数据，实际上数组的空间还是被占用的，优化成环形队列可以解决空间浪费的问题。