循环队列的顺序队列实现

孙泽辉

发布于：2021年8月29日

字数：393字

时长：1分钟

次浏览

学到队列了，写个循环队列练练手。

队列结构：

interface seqQueue {
  data: Array<number | null>;
  front: number;
  rear: number;
}

why not 普通队列？

在普通队列下：

入队：SQ.rear = SQ.rear + 1

出队：SQ.front = SQ.front + 1

在一直入队之后一直出队，到达数组尾部的时候，这时如果判断尾指针到达数组尾部为结束条件的话，再次添加元素将超出数组的下标范围，但前面还有很多空闲空间，这种现象称为“假溢出”。

此时，循环队列出现了！

循环队列

循环队列提出了两种方案：

1. 设置一个标志，用来区分队列是空还是满
2. 队列少用一个空间，当只剩下一个元素的时候即认为队列已满

书上采用了第二种方案。

队列满的条件为：

(CQ.rear + 1) % maxSize === CQ.front 成立

队列空的条件为：

CQ.rear === CQ.front 成立

循环队列的代码实现：

class SequenceQueue implements seqQueue {
  maxSize: number = 10;
  data: Array<number | null>;
  front: number;
  rear: number;
  constructor() {
    this.data = new Array<number | null>(this.maxSize).fill(null);
    this.front = 0;
    this.rear = 0;
  }
  isEmpty(): boolean {
    return this.front === this.rear;
  }
  enQueue(x: number): boolean {
    if ((this.rear + 1) % this.maxSize === this.front) {
      throw new Error("队列满了");
    }
    this.rear = (this.rear + 1) % this.maxSize;
    this.data[this.rear] = x;
    return true;
  }
  outQueue(): boolean {
    if (this.isEmpty()) {
      throw new Error("队列没东西了");
    }
    this.data[this.front] = null;
    this.front = (this.front + 1) % this.maxSize;
    return true;
  }
  getHead(): number | null {
    return this.isEmpty() ? null : this.data[(this.front + 1) % this.maxSize];
  }
}

总结

哈哈哈哈哈哈哈