算法面经-队列

队列

一、队列介绍

1. 队列是一个有序列表，可以用数组或是链表来实现。

2. 遵循<u style="box-sizing: border-box;">先入先出</u>的原则。即：先存入队列的数据，要先取出。后存入的要后取出

队列1.png

二、数组模拟队列vs循环队列

2.1 普通队列入队

1. 将尾指针往后移：rear+1 , 当 front == rear 【空】 2) 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear 所指的数组元素中，否则无法存入数据。rear == maxSize - 1[队列满]

代码实现：

 // 使用数组模拟队列-编写一个 ArrayQueue 类
 class ArrayQueue {
  private int maxSize; // 表示数组的最大容量
  private int front; // 队列头
  private int rear; // 队列尾
  private int[] arr; // 该数据用于存放数据, 模拟队列
 // 创建队列的构造器
 publicArrayQueue(int arrMaxSize) {
  maxSize = arrMaxSize;
  arr = new int[maxSize];
  front = -1; // 指向队列头部，分析出 front 是指向队列头的前一个位置.
  rear = -1; // 指向队列尾，指向队列尾的数据(即就是队列最后一个数据)
 }
 // 判断队列是否满
 public boolean isFull() {
  return rear == maxSize - 1;
 }
 // 判断队列是否为空
 public boolean isEmpty() {
  return rear == front;
 }
 // 添加数据到队列
 public void addQueue(int n) {
 // 判断队列是否满
  if (isFull()) {
  System.out.println("队列满，不能加入数据~");
  return;
  }
  rear++; // 让 rear 后移
  arr[rear] = n;
 }
 // 获取队列的数据, 出队列
 public int getQueue() {
  // 判断队列是否空
  if (isEmpty()) {
  // 通过抛出异常
  throw new RuntimeException("队列空，不能取数据");
  }
  front++; // front 后移
  return arr[front];
 }
 // 显示队列的所有数据
 public void showQueue() {
  // 遍历
  if (isEmpty()) {
  System.out.println("队列空的，没有数据~~");
  return;
 }
 for (int i = 0; i < arr.length; i++) {
  System.out.printf("arr[%d]=%d\n", i, arr[i]);
  }
 }
 // 显示队列的头数据， 注意不是取出数据
 public int headQueue() {
 // 判断
  if (isEmpty()) {
  throw new RuntimeException("队列空的，没有数据~~");
  }
  return arr[front + 1];
  }
 }

问题分析并优化

1. 目前数组使用一次就不能用， <u style="box-sizing: border-box;">没有达到复用的效果</u> 2) 将这个数组使用算法，改进成一个列 环形的队列 取模：%

2.2 循环队列

分析说明： 1) 尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,这个在做判断队列满的时候需要注意 (rear + 1) % maxSize == front 满] 2) rear == front [空]

队列2.png

代码实现：

class CircleArray {
  private int maxSize; // 表示数组的最大容量
  //front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素
  //front 的初始值 = 0
  private int front;
  //rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.
  //rear 的初始值 = 0
  private int rear; // 队列尾
  private int[] arr; // 该数据用于存放数据, 模拟队列
 public CircleArray(int arrMaxSize) {
  maxSize = arrMaxSize;
  arr = new int[maxSize];
 }
 ​
 // 判断队列是否满
 public boolean isFull() {
  return (rear + 1) % maxSize == front;
 }
 // 判断队列是否为空
 public boolean isEmpty() {
  return rear == front;
 }
 // 添加数据到队列
 public void addQueue(int n) {
  // 判断队列是否满
  if (isFull()) {
  System.out.println("队列满，不能加入数据~");
  return;
 }
  //直接将数据加入
  arr[rear] = n;
  //将 rear 后移, 这里必须考虑取模
  rear = (rear + 1) % maxSize;
 }
 // 获取队列的数据, 出队列
 public int getQueue() {
 ​
  // 判断队列是否空
  if (isEmpty()) {
  // 通过抛出异常
  throw new RuntimeException("队列空，不能取数据");
  }
  // 这里需要分析出 front 是指向队列的第一个元素
  // 1\. 先把 front 对应的值保留到一个临时变量
  // 2\. 将 front 后移, 考虑取模
  // 3\. 将临时保存的变量返回
  int value = arr[front];
  front = (front + 1) % maxSize;
  return value;
 }
 // 显示队列的所有数据
 public void showQueue() {
  // 遍历
  if (isEmpty()) {
  System.out.println("队列空的，没有数据~~");
  return;
  }
  // 思路：从 front 开始遍历，遍历多少个元素
  // 动脑筋
  for (int i = front; i < front + size() ; i++) {
  System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
 ​
  }
 }
 // 求出当前队列有效数据的个数
 public int size() {
  // rear = 2
  // front = 1
  // maxSize = 3
  return (rear + maxSize - front) % maxSize;
 }
 // 显示队列的头数据， 注意不是取出数据
 public int headQueue() {
  // 判断
  if (isEmpty()) {
  throw new RuntimeException("队列空的，没有数据~~");
  }
  return arr[front];
  }
 }