一，数组模拟队列
规定头指针front和尾指针rear都为-1，front=-1表示头指针指向队头的前一个位置，尾指针rear=-1表示指向队尾，这两句话要好好的理解，
maxSize为队列的大小
arr[ ]使用来存储数据的数组，大小由maxSize来定，
判断队列是否为空：当队尾和队头合并则代表队列为空,rear == front
判断队列是否已满：当队尾的索引等于队列长度-1，因为索引从0开始，所以队列的长度要-1才和队尾索引相等，rear == maxSize-1
入队：先判断是否已满，不满的话尾指针后移一个位置（rear++),然后将元素放入数组
出队：判断队列是否为空，不为空的话头指针后移（front++)
代码：
package Queue; import java.util.Scanner; public class ArrayQueue { public static void main(String[] args) { ArrayQueue arrayQueue = new ArrayQueue(6); Scanner scanner = new Scanner(System.in); char key = ' '; boolean loop = true; while (loop) { System.out.println("a 入队"); System.out.println("r 出队"); System.out.println("g 遍历队列"); System.out.println("h 查看队头元素"); key = scanner.next().charAt(0);//接收一个字符串 switch (key) { case 'a': System.out.println("输入一个数"); int value = scanner.nextInt(); arrayQueue.addQueue(value); break; case 'r': try { int removeNum = arrayQueue.removeQueue(); System.out.println("取出的数据为：" + removeNum); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 'g': try { arrayQueue.getAllQueue(); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 'h': try { int headNum = arrayQueue.headQueue(); System.out.println("队头为："+headNum); }catch (Exception e){ System.out.println(e.getMessage()); } } } } int maxSize; int rear; int front; int arr[]; public ArrayQueue(int arrMaxSize){ maxSize = arrMaxSize; rear = -1; front = -1; arr = new int[maxSize]; } //判断队列是否为空 public boolean isEmpty(){ return rear == front; } //判断队列是否已满 public boolean isFull(){ return rear == maxSize-1; } //入队 public void addQueue(int num){ if (isFull()){ System.out.println("队列满的"); return; } rear++; arr[rear] = num;//入队 } //出队(单个元素） public int removeQueue(){ if (isEmpty()){ throw new RuntimeException("队列没有元素"); } front++; return arr[front]; } //遍历队列所有元素 public void getAllQueue(){ if (isEmpty()){ throw new RuntimeException("队列为空"); } for (int i = 0 ; i <= arr.length ; i++){ System.out.println("队列元素下标："+i+" "+"队列元素值:"+arr[i]); } } //查看队头元素 public int headQueue(){ if (isEmpty()){ throw new RuntimeException("队列为空"); } return arr[front+1]; } }
但是上述代码存在一个问题，数组使用过一次就不能使用了（因为头指针front和尾指针rear都指向了入队口，虽然里面还有很多空间，但是不能用，是一个“假的”满队列），如果要复用，则应该改造成环形队列
二：环形队列
思路：对front变量的含义做调整，front指向队列第一个元素，初始值为0，rear指向最后一个元素的前一个元素，留出一个空位作为约定，rear初始值为0
判断队满：（rear+1)%maxSize == front;
上图：rear=4,front=0,maxSize=5
(4+1)%5=0
判断队空：rear == front
rear和front初始化都为0，如果rear==front,为空
队列中元素个数:（rear+maxSize-front)%maxSize
如上队满图：（4+5-0）%5 = 4
代码：
package Queue; import java.util.Scanner; public class CircleArrayQueue { public static void main(String[] args) { CircleArray arrayQueue = new CircleArray(4); Scanner scanner = new Scanner(System.in); char key = ' '; boolean loop = true; while (loop) { System.out.println("a 入队"); System.out.println("r 出队"); System.out.println("g 遍历队列"); System.out.println("h 查看队头元素"); key = scanner.next().charAt(0);//接收一个字符串 switch (key) { case 'a': System.out.println("输入一个数"); int value = scanner.nextInt(); arrayQueue.addQueue(value); break; case 'r': try { int removeNum = arrayQueue.removeQueue(); System.out.println("取出的数据为：" + removeNum); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 'g': try { arrayQueue.getAllQueue(); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 'h': try { int headNum = arrayQueue.headQueue(); System.out.println("队头为："+headNum); }catch (Exception e){ System.out.println(e.getMessage()); } } } } } class CircleArray{ int maxSize; int rear; int front; int arr[]; public CircleArray(int arrMaxSize){ maxSize = arrMaxSize; arr = new int[maxSize]; front = 0; rear = 0; } //判断队列是否为空 public boolean isEmpty(){ return rear == front; } //队列是否已满 public boolean isFull(){ return (rear+1)%maxSize == front; } //入队 public void addQueue(int num){ if (isFull()){ System.out.println("队列满的"); return; } arr[rear] = num;//入队 rear = (rear+1)%maxSize; } //出队(单个元素） public int removeQueue(){ if (isEmpty()){ throw new RuntimeException("队列没有元素"); } int value = arr[front]; front = (front + 1) % maxSize; return value; } //元素有效个数 public int size(){ return (rear+maxSize-front)%maxSize; } //遍历队列所有元素 public void getAllQueue(){ if (isEmpty()){ throw new RuntimeException("队列为空"); } //从front开始遍历 for (int i = front ; i <= size() ; i++){ System.out.printf("arr[%d]=%d\n",i % maxSize,arr[i % maxSize]); } } //查看队头元素 public int headQueue(){ if (isEmpty()){ throw new RuntimeException("队列为空"); } return arr[front]; } }
环形队列还不是很清楚
