Introduction of the queue

A Queue is a restricted linear table characterized by FIFO first in first out.

The place of limited

  • Only those at the front of the queue are allowed(frontdelete
  • Only at the end of the queuerearinserting

illustrated

Queue diagram

Application of queues in programs

  • Print queue: When the computer prints multiple files, it needs to queue up to print
  • Thread queue: When multithreading is enabled, when the resources required by the newly opened threads are insufficient, they are placed in the thread queue and wait for processing by the CPU.

Implementation of queues

  • Array based implementation
  • Based on the linked list

Queue common operations

  • enqueue(element)Adds one or more elements to the end of the queue.
  • dequeue()Removes the first element in the queue and returns the removed element.
  • front()Returns the first element in the queue without any changes to the queue.
  • isEmpty()Checks whether the queue is empty.
  • size()Returns the number of elements in the queue.
  • print()Prints the values of the elements in the queue.

Code implementation

// Queues can be abstracted as queues in life

// First in first out
class Queue {

  constructor() {
    this.items = []
  }


  / / team
  enqueue(element) {
    this.items.push(element)
  }

  / / out of the team

  dequeue() {
    return this.items.shift()
  }


  // Find the head element
  front() {
    return this.items[0]}// Check whether the queue is empty
  isEmpty() {
    return this.items.length === 0
  }

  // Check the queue element length
  size() {
    return this.items.length
  }

  // Print the queue elements
  print() {
    return this.items.join("")}}module.exports = Queue
Copy the code

The test code

const Queue = require('./queue')
// Test the code

let queue = new Queue()

queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
queue.enqueue(5)

console.log(queue.print())
Copy the code

An application

Title: Drum pass flowers

There are five people A,B, C, D, E,F in A circle. Every time the number reaches 5, remove the person from the circle until only one person is left in the circle. The game is over

function passGame(data, num) {

  // Add the people in the circle to the queue first

  let queue = new Queue()

  data.forEach(element= > {
    queue.enqueue(element)
  });

  while (queue.size() > 1) {
    // If you don't count the people before you count them, put them back at the end of the queue until they are counted.
    for (let i = 0; i < num - 1; i++) {
      queue.enqueue(queue.dequeue())
    }
    queue.dequeue()
  }

  return queue.front()
}

console.log(passGame(['lily'.'lucy'.'tom'.'tony'.'jack'].4))
Copy the code