TS实现环形队列

吐槽一下，这个是按照Java的定长数组为前提的，然而TypeScript数组是不定长的，再加上原生具有push和shift方法，其实这个实现完全没有必要。。但最近正好学数据结构，就当练习了

功能(方法)

• 实现队列的出队和入队
• 显示队列的所有数据
• 显示队列的有效数据个数

需要维护的类属性

• maxSize：数组的最大容量
• front，rear：队头队尾
• arr：存放数据的数组,模拟队列

实现思路

使用有限长度的数组，使用取模的方法使队头与队尾在预设的下标范围内移动

• 一开始队头与队尾相等，下标值为0
• 当元素入队时：队尾的移动公式为：rear = (rear + 1) % maxSize;
• 当元素出队时：队头的移动公式为：front = (front + 1) % maxSize;
• 队列有效数据的个数计算公式为：length = (rear - front + maxSize) % maxSize;
• 判断队列为空的计算公式：rear === front
• 判断队列是否满：isFull = (rear + 1) % maxSize === front

代码实现

//使用数组模拟队列
class CircleQueue<T> {
    //构造器
    constructor(arrMaxSize: number) {
        //需要预留一个
        this._maxSize = arrMaxSize + 1;
        // 初始化数组(感觉没必要)
        this._arr = new Array<T>();
        //头部和尾部一开始是相等的
        this._front = 0;
        this._rear = 0;
    }
    //数组的最大容量
    private _maxSize: number;
    //队头队尾
    private _front: number;
    private _rear: number;
    //存放数据的数组,模拟队列
    private _arr: Array<T>;

    //判断队列是否满
    public isFull(): boolean {
        let { _rear, _maxSize, _front } = this
        return (_rear + 1) % _maxSize === _front;
    }

    //判断队列是否为空
    public isEmpty() {
        return this._rear === this._front
    }

    //入队列
    public push(item: T): void {
        //判断队列是否满
        if (this.isFull()) {
            throw new Error('队列已满!');
        }
        //加入数据
        this._arr[this._rear] = item;
        this._rear = (this._rear + 1) % this._maxSize;
    }

    //出队列
    public pop(): T {
        //判断队列是否空
        if (this.isEmpty()) {
            throw new Error('队列为空!');
        }
        //取出数据
        let val = this._arr[this._front];
        this._front = (this._front + 1) % this._maxSize;
        return val;
    }

    //显示队列所有数据
    public show(): void {
        //判断队列是否空
        if (this.isEmpty()) {
            throw new Error('队列为空!');
        }
        let { _front, _rear, _maxSize } = this;
        //遍历
        let tmp = '';
        for (let i = _front; i < _front + this.length(); i++) {
            //% _maxSize 防止越界
            tmp += 'arr[' + i % _maxSize + ']=' + this._arr[i % _maxSize] + ' ';

        }
        tmp = tmp.trim();
        console.log(tmp);

    }

    //显示队列的头数据
    public head(): T {
        //判断队列是否空
        if (this.isEmpty()) {
            throw new Error('队列为空!');
        }
        let { _front, _arr } = this;
        return _arr[_front];
    }

    //计算队列有效数据个数
    public length(): number {
        let { _front, _rear, _maxSize } = this;
        let sum: number;
        sum = (_rear - _front + _maxSize) % _maxSize;
        return sum
    }
}
export default CircleQueue;