用JS实现一个队列

ゝ一世哀愁。 2022-11-10 14:55 182阅读 0赞

我们先来看一道携程2021春招的面试题：

***用JS实现一个队列***

想象中午食堂吃饭时、等电梯时、早晚高峰进地铁时，都需要排队。那么肯定是先排队的有优先权，然后依次进入。队列也是这个道理，只有一个出口，一个入口，特点是`先进先出`，这和栈的思想相反。队列有一个入口，取名为`enqueue`;出口取名为`dequeue`;正常情况下，还需要读取队首和队尾元素，命名为`front`和`back`，读取队列所有元素，命名为`toStringData`, 判断队列是否空，命名为`isEmpty`。现在可以完成队列的构造函数了，如下：

### 入队enqueue() ###

//在队尾添加一个元素即为入队
    function enqueue(element) {
        this.data.push(element);
    }

### 出队dequeue() ###

//在队首删除一个元素，并返回被删除的值
    function dequeue() {
        return this.data.shift();
    }

### 返回队首元素front() ###

//返回数组第一项即返回队首元素
    function front() {
        return this.data[0];
    }

### 返回队尾元素back() ###

//返回数组最后一项即返回队尾元素
    function back() {
        return this.data[this.data.length - 1];
    }

### 判断队列是否为空isEmpty() ###

//数组长度为0即队列为空
    function isEmpty() {
        return this.data.length === 0;
    }

### 查看队列内的所有元素toStringData() ###

//打印队列
    function toStringData() {
        return this.data;
    }

至此，我们就用JS完整地实现了一个**单向队列**！

## 队列的完整代码 ##

## 使用Queue类 ##

测试一下：

/*测试*/
    var q = new Queue();
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.enqueue(4);
    console.log(q.toStringData());//[1, 2, 3, 4]
    console.log(q.dequeue());//1
    console.log(q.toStringData());//[2, 3, 4]
    console.log(q.front());//2
    console.log(q.back());//4
    console.log(q.isEmpty());//false

到这里，整个队列的功能测试完成。

### 双向队列 ###

双向队列即队列的首尾都能进能出，那么只需在单向队列中添加两个方法，队首添加一个元素方法(`fenqueue`)，队尾删除一个元素的方法('bdequeue'),即可。队列的构造函数添加两个方法，如下：

现在就完成了双向队列。双向队列能实现什么功能呢？如回文之类的使用双向队列能很方便的实现，使用双向队列无论从前还是后插入数据，都一个原理