Queue definition

A queue is an ordered item that follows a first-in, first-out rule. A very vivid example is the queue for dry rice, the first to come first service, then the queue at the end.

Calm analysis

The functions of queues include the following:

  1. Add new elements to the end of the queue
  2. Remove the first item in the queue
  3. Returns the first element in the queue
  4. Whether the queue contains elements
  5. Length of queue

Code implementation

class Queue {

    constructor() {
        this.index = 0;
        this.outIndex = 0; // The index of the first queue item
        this.items = {};
    }

    add(ele) {
        this.items[this.index] = ele
        this.index++
    }
    remove() {
        if (this.isEmpty()) {
            return undefined
        }
        const delEle = this.items[this.outIndex]
        delete this.items[this.outIndex]
        this.outIndex++
    }
    size() {
        return this.index - this.outIndex
    }
    isEmpty() {
        return this.size()
    }
    clear(){
        this.index = 0;
        this.outIndex = 0;
        this.items = {}; }}Copy the code

Double – endian queue (Deque) definition

A special queue that allows us to add or remove elements from the front and back of the queue, following the principle of fifO and FIFO, is a combination of stack and queue data structure.

Calm analysis

The functions of a dual-ended queue include the following:

  1. Adds a new element to the front of a two-ended queue
  2. Adds a new element to the back-end of the two-ended queue
  3. Remove the first item in a two-end queue
  4. Remove the first item at the back end of a two-end queue
  5. Returns the first element at the beginning and end of a two-ended queue
  6. Whether a double-ended queue contains elements
  7. The length of a two-endian queue

Code implementation

class Deque {
    constructor() {
        this.count = 0
        this.outIndex = 0 // The front end index value
        this.items = {}
    }
    addFront(ele) {
        /** there are three ways to add elements to the front end of a double-ended queue: * 1- The front end queue is empty, so adding elements to the front end is the same as adding elements to the front end * 2- If the front end element is deleted,outIndex will be ++, so the front end needs to outIndex before adding elements to the front end - * 3- If the front end queue has elements */
        if (this.isEmpty()) {
            this.addBack(ele)
        } else if (this.outIndex > 0) {
            this.outIndex--
            this.items[this.outIndex] = ele
        } else {
            for (let i = this.count; i > 0; i--) {
                this.items[i] = this.items[i - 1]}this.count++
            this.outIndex = 0
            this.items[this.outIndex] = ele
        }
    }
    addBack(ele) {
        this.items[this.count] = ele
        this.count++;
    }
    removeFront() {
        if (this.isEmpty()) {
            return undefined
        }
        const delEle = this.items[this.outIndex]
        delete this.items[this.outIndex]
        this.outIndex++
    }
    removeBack() {
        if (this.isEmpty()) {
            return undefined
        }
        this.count--
        const delEle = this.items[this.count]
        delete this.items[this.count]
        return delEle
    }
    peekFront() {
        if (this.isEmpty()) {
            return undefined
        }
        return this.items[0]}peekBack() {
        if (this.isEmpty()) {
            return undefined
        }
        return this.items[Object.keys(this.items).length - 1]}size() {
        return this.count
    }
    isEmpty() {
        return this.size() == 0}}Copy the code