您的位置 首页 java

数组实现队列和循环队列(Java)

如何理解“队列”

  • 操作受限的 线性表 数据结构:先进先出
  • 最基本的操作:入队和出队
  • 队列分为队头和队尾,在 队尾 插入数据(入队),在 队头 删除数据(出队)。

用数组实现的顺序队列

  • 思路:使用两个指针,一个head指针指向队头,一个 tail 指针指向队尾。
  • 代码​
// 用数组实现的队列public class ArrayQueue {  // 数组:items,数组大小:n  private String[] items;  private int n = 0;  // head 表示队头下标,tail 表示队尾下标  private int head = 0;  private int tail = 0;​  // 申请一个大小为 capacity 的数组  public ArrayQueue(int capacity) {    items = new String[capacity];    n = capacity; }​  // 入队  public boolean enqueue(String item) {    // 如果 tail == n 表示队列已经满了    if (tail == n) return false;    items[tail] = item;    ++tail;    return true; }​  // 出队  public String dequeue() {    // 如果 head == tail 表示队列为空    if (head == tail) return null;    // 为了让其他语言的同学看的更加明确,把 -- 操作放到单独一行来写了    String ret = items[head];    ++head;    return ret; }} 
  • 代码存在问题:随着不停地进行入队、出队操作,head 和 tail 都会持续往后移动。当 tail 移动到最右边,即使数组中还有空闲空间,也无法继续往队列中添加数据了。
  • 代码优化思路:在tail移动到最右边时,判断head是否为0,如果是0,说明队列已满,如果不是,说明队列未满,此时进行一次队列的迁移,队列从head到tail整体迁移到从0开始。
  • 优化代码
// 入队操作,将 item 放入队尾
  public boolean enqueue(String item) {
    // tail == n 表示队列末尾没有空间了
    if (tail == n) {
      // tail ==n && head==0,表示整个队列都占满了
      if (head == 0) return false;
      // 数据搬移
      for (int i = head; i < tail; ++i) {
        items[i-head] = items[i];
      }
      // 搬移完之后重新更新 head 和 tail
      tail -= head;
      head = 0;
    }
    
    items[tail] = item;
    ++tail;
    return true;
  } 

使用循环队列避免数据搬移操作

  • 顾名思义,就是对队列的收尾是连接的,并不是真的像循环链表一样首尾连接,而是有相同的效果。
  • 使用数组实现思路:数组实现队列,就是通过两个链表来访问数组,实现先进先出的效果。所以在入队和出队时,把控好数组的下标的变换即可实现循环队列的效果。所以需要了解判断队满的情况指针变换的情况。
  • 思考:队列长度为n队满的情况(针对队尾):循环队列不能再使用tail等于n来判断是否有队满的可能。此时,因为是循环队列,由于其循环进行入队和出队的操作的特殊性,当队满时,队列就是全部被填满的,所以此时, 出队和入队指针指向的值的和为n-1 .(也可以用表达式(tail+1)%n==head)队空的情况(针对队头):不变,依然是head == tail时为队空。指针变换的思考:不考虑队满和队空时,head和tail指针需要在等于n-1时,下一次变换为0.所以,可以使用一个判断或者使用+1整除n。
  • 代码
public class CircularQueue {
  // 数组:items,数组大小:n
  private String[] items;
  private int n = 0;
  // head 表示队头下标,tail 表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为 capacity 的数组
  public CircularQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入队
  public boolean enqueue(String item) {
    // 队列满了
    if (tail + head + 1 == n) return false;
    items[tail] = item;
    tail = (tail + 1) % n;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果 head == tail 表示队列为空
    if (head == tail) return null;
    String ret = items[head];
    head = (head + 1) % n;
    return ret;
  }
} 

文章来源:智云一二三科技

文章标题:数组实现队列和循环队列(Java)

文章地址:https://www.zhihuclub.com/194747.shtml

关于作者: 智云科技

热门文章

发表回复

您的电子邮箱地址不会被公开。

网站地图