1. Definition of queues

Queues are special linear tables that only allow you to delete elements at the head of the queue and add new elements at the end of the queue.

2. Queue methods

  • Enqueue adds an element from the end of the queue.
  • Dequeue removes an element from the head of the queue (the first person in the queue has just checked in and left the queue)
  • Head returns the element in the header, not deleted (just to see who comes first).
  • Size Returns the queue size (count how many people are in the queue)
  • Clear the queue. (The flight is cancelled, everyone should clear the queue.)
  • IsEmpty determines whether the queue isEmpty (to see if someone is queuing)
  • Tail Returns the last node of the queue

3. Implement queues

I’m going to do it as an array. As follows:

function Queue () {
    var items = [];
    this.enqueue = function(item){
        items.push(item)
    }
    this.dequeue = function(){
        items.shift()
    }
    this.head = function(){
        return items[0]
    }
    this.size = function(){
        return items.length
    }
    this.clear = function(){
        items = []
    }
    this.isEmpty = function(){
        return items.length === 0
    }
    this.tail = function(){
        return items[items.length-1]
    }
}
Copy the code

4. Queue exercises

Q1: Joseph ring problem. There is an array a[100] that holds 0–99; Ask to delete a number every two, at the end of the cycle to continue to the beginning, find the last deleted number.

The code:

function del_circle(arr){ var _queue = new Queue(); var index = 0; For (var I =0; i<arr.length; i++){ _queue.enqueue(arr[i]); } var index = 0; while(_queue.size() ! Var item = _queue.dequeue(); index += 1; // If (index %3! == 0){ _queue.enqueue(item); } } return _queue.head(); } var arr = []; for(var i=0; i<100; i++){ arr.push(i); } console.log(del_circle(arr));Copy the code

Ideas:

Prepare a queue (the header can remove elements, the tail can add elements) and push 100 numbers to the stack. Remove one in every two numbers and place them at the end of the queue. Mod every three, find the number to delete, mark it with index, and queue the first two numbers. And so on…

Q2: Fibonacci sequence

The first two terms are 1, 1, and then each term is the sum of the first two terms, so f of n is equal to f of n minus 1 plus f of n minus 2.

1. Recursive implementation:

function fibonacci(n){
    if(n<=2) return n;
    return fibonacci(n-1) + fibonacci(n-2);
}
Copy the code

2. Queue implementation

function fibonacci(n){ var queue = new Queue(); var index = 0; Queue.enqueue (1); queue.enqueue(1); queue.enqueue(1); queue.enqueue(1); While (index < n-2){var del_item = queue.dequeue(); Var head_item = queue.head(); var next_item = del_item + head_item; Queue. Enqueue (next_item); index += 1; } queue.dequeue(); return queue.head(); }Copy the code

Ideas:

The sum of the first two items is added to the queue from the end of the queue. Two numbers are added to the queue first. The element deleted from the head of the queue is denoted as del_item, which is the remaining head_item in the queue.