04队列.md

队列

• 队列是一个有序列表，可以使用数组/链表来实现
• 遵循先入先出的原则

数组模拟队列

• 初始化
  • font = -1 指向队列头数据的前一个位置
  • rear = -1 指向队列尾部数据
  • maxSize 数组大小
• 边界判断
  • ifFull rear == maxSize - 1
  • isEmpty rear == font
• addQueue
  • if !isFull
  • rear + 1
  • rear == data
• getQueue
  • if !isEmpty
  • return queue[++font];
• showHead
  • if !isEmpty
  • console.log(font + 1)

队列优化-circle Queue

上图所示的队列有一些问题，就是在取值的时候队首指针后移，导致数组前面的内存空间无法访问和存储。

这里不再使用队头队尾双指针控制队列，而选择使用size->队列的大小来操控队列。

循环队列的难点

• enterQueue

  • 入队的时候要注意下标的控制，Queue[( font + size ) % maxSize] = element。
  • size++

• getQueueHead

  • 出队的时候要先保存值，再移动front指针。
  • 出队的元素可能指向对象类型，让其指向null，回收无用的数据。

使用size而不是尾队列指针的优势

• isEmpty
  • size===0
• isFull
  • size === maxSize

代码实现

class circleQueue {
    constructor(maxSize) {
        this.font = 0;
        this.size = 0;
        this.maxSize = maxSize;
        this.queue = [];
    }

    isEmpty() {
        return this.size === 0;
    }

    isFull() {
        return this.size === this.maxSize;
    }

    enterQueue(element) {
        if (this.isFull()) {
            console.log('the queue is fulled');
            return;
        }
        this.queue[(this.font + this.size) % this.maxSize] = element;
        this.size++;
    }

    deQueue() {
        if (this.isEmpty()) {
            console.log('the queue is empty');
            return;
        }
        let fontVal = this.queue[this.font];
        // 回收
        this.queue[this.font] = null;

        // 校正
        this.font = (this.font + 1) % this.maxSize;
        this.size--;
        return fontVal;
    }

    showQueue() {
        if (!this.isEmpty()) {
            for (let i = this.font; i < this.size; i++) {
                console.log(this.queue[i % this.maxSize]);
            }
        }
    }

}

​