队列的数组实现

          链表遵循着先入先出的原则,类似于银行排队,这里学习的是队列模拟链表的算法

要想用数组模拟出一个队列,首先我们需要定义三个变量
1.maxSize 数组的最大长度
2.front 指向出队的指针
3.rear 指向入队的指针
具体实现代码
package queue;
import java.util.Scanner;
/

• @author Administrator
• 2019-10-30-16
  /
  public class CircleQueueDemo {
  public static void main(String[] args) {
  //假装创建了一个队列,实际上是数组
  CircleQueue queue = new CircleQueue(3);
  //从键盘中接受数据
  Scanner scanner = new Scanner(System.in);
  //定义一个空字符作为接受的对象
  char key = ’ ';
  //简单的循环,由于定义了loop,可以在后面的case中修改loop的值来改变循环
  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):查看队列头的数据”);
  //这里key是从键盘中接收的第一个字符
  key = scanner.next().charAt(0);
  switch (key) {
  case ‘s’:
  queue.showQueue();
  break;
  case ‘a’:
  System.out.println(“输出一个数”);
  int value = scanner.nextInt();
  queue.addQueue(value);
  break;
  case ‘g’:
  try {
  int res = queue.getQueue();
  System.out.printf(“队头的数据是%d\n”, res);
  } catch (Exception e) {
  System.out.println(e.getMessage());
  }
  break;
  case ‘h’:
  try {
  int res = queue.headQueue();
  System.out.printf(“队列的头部是%d\n”, res);
  } catch (Exception e) {
  System.out.println(e.getMessage());
  }
  break;
  case ‘e’:
  scanner.close();
  loop = false;
  break;
  default:
  break;
  }
  }
  System.out.println(“程序退出”);
  }
  //这里才是程序的本体
  static class CircleQueue {
  private int front;
  private int rear;
  private int[] arr;
  private int maxSize;
  //在环形队列中,front和rear的初始值都是0
  public CircleQueue(int arrmaxSize) {
  this.maxSize = arrmaxSize;
  arr = new int[maxSize];
  }
  public boolean isEmpty() {
  return rear == front;
  }
  public boolean isFull() {
  //环形队列主要的操作就是取模,哪个天才想出来的
  return (rear +1) % maxSize==front;
  }
  public void addQueue(int n) {
  if (isFull()) {
  System.out.println(“数组已满”);
  return;
  }
  arr[rear] = n;
  //在数组中我们预留了一个空间作为环形的首尾相连,所以单次达不到数组的maxSize-1
  rear=(rear+1)%maxSize;
  }
  public void showQueue() {
  if (isEmpty()) {
  System.out.println(“数组是空的,没有数据”);
  return;
  }
  //这里是环形数组取模运算的精华
  for (int i = front; i < front+size(); i++) {
  System.out.printf(“arr[%d]=%d\n”,i%maxSize, arr[i%maxSize]);
  }
  }
  public int getQueue() {
  if (isEmpty()) {
  throw new RuntimeException(“队列为空”);
  } else {
  int value=arr[front];
  front=(front+1)%maxSize;
  return value;
  }
  }
  public int headQueue() {
  if (isEmpty()) {
  throw new RuntimeException(“数组是空的”);
  }
  return arr[front];
  }
  public int size(){
  //size是整个数组中有效数据的个数
  int size=(rear+maxSize-front)%maxSize;
  return size;
  }
  }
  }*