队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

一、简介

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

• 用数组实现一个顺序队列
• 用链表实现一个链式队列
• 实现一个循环队列

二、手写

1. 数组队列

function ArrayQueue() {
    let queue = []
    this.push = function(value) {
        queue.push(value)
    }
    this.pop = function(value) {
        queue.shift(value)
    }
    this.getFront = function() {
        return queue[0]
    }
    this.getRear = function() {
        return queue[queue.length - 1]
    }
    this.clear = function() {
        queue = []
    }
    this.size = function() {
        return queue.length
    }
}

2. 链表队列

class Node {
    constructor(value) {
        this.value = value
        this.next = null
    }
}

class LinkedQueue {
    constructor() {
        this.head = null
        this.tail = null
    }
    enqueue(value) {
        if (this.head === null) {
            this.head = new Node(value)
            this.tail = this.head
        } else {
            this.tail.next = new Node(value)
            this.tail = this.tail.next
        }
    }
    dequeue() {
        if (this.head === null) {
            return -1
        } else {
            const value = this.head.value
            this.head = this.head.next
            return value
        }
    }
}

三、思考题

1. 设计双端队列（#641）

题目：

设计实现双端队列。
你的实现需要支持以下操作：

MyCircularDeque(k)： 构造函数, 双端队列的大小为k。
insertFront()： 将一个元素添加到双端队列头部。 如果操作成功返回 true。
insertLast()： 将一个元素添加到双端队列尾部。 如果操作成功返回 true。
deleteFront()： 从双端队列头部删除一个元素。 如果操作成功返回 true。
deleteLast()： 从双端队列尾部删除一个元素。 如果操作成功返回 true。
getFront()： 从双端队列头部获得一个元素。 如果双端队列为空， 返回 - 1。
getRear()： 获得双端队列的最后一个元素。 如果双端队列为空， 返回 - 1。
isEmpty()： 检查双端队列是否为空。
isFull()： 检查双端队列是否满了。
示例：

MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1); // 返回 true
circularDeque.insertLast(2); // 返回 true
circularDeque.insertFront(3); // 返回 true
circularDeque.insertFront(4); // 已经满了，返回 false
circularDeque.getRear(); // 返回 2
circularDeque.isFull(); // 返回 true
circularDeque.deleteLast(); // 返回 true
circularDeque.insertFront(4); // 返回 true
circularDeque.getFront(); // 返回 4

提示：

所有值的范围为[1, 1000]
操作次数的范围为[1, 1000]
请不要使用内置的双端队列库。

（待续）