The queue

What is a queue

A queue is a special linear table that allows nodes to be deleted only at the head of the queue and new elements to be added at the end.

In our real life, the supermarket checkout line is a typical example. After the first checkout line, leave the head of the queue. Those who want to check out should come in at the end of the line and wait.

Common methods

  • Enqueue adds an element from the end of the queue.
  • Dequeue removes an element from the head of the queue (I’m ready to check out and leave the queue)
  • Head returns the header element (let me see who comes first)
  • Size Returns the queue size (how many people are in the queue?).
  • It’s eleven o ‘clock. It’s close enough. Leave the team.
  • IsEmpty checks if the queue isEmpty (let me see if there is anyone queuing)
  • Tail returns the last element of the queue (let me see who is last now)

Implement queue logic

function Queue() {
  const items = []

  this.enqueue = function (item) {
    items.push(item)
  }

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

  this.head = function () {
    return items[0]}this.tail = function () {
    return items[items.length - 1]}this.size = function () {
    return items.length
  }

  this.clear = function () {
    items.length = 0
  }

  this.isEmpty = function () {
    return items.length === 0}}Copy the code

Simple exercise

1. Joseph ring

Topic request

An array a[100] holds 0 to 99. At the end, the loop continues at the beginning of the value, finding the last deleted number.

Train of thought

Let’s look at it and delete the third element every second. Because when the cycle is over, you have to start all over again. This allows us to borrow the form of a queue and store all the data in a queue. Loop through the queue and define index to record the current position. When index is a multiple of 3, we remove the element, otherwise we add it back to the header. This loop continues until there is only one element left in the queue. Finally, we return the header element, which is our final result.

Code implementation
const test1 = [5.6.7.8.9.10.0.1.2.3.4]
const test2 = []
for (let i = 0; i < 100; i++) test2.push(i)

function delRing(arrList) {
  const queue = new Queue()
  for (let i = 0; i < arrList.length; i++) queue.enqueue(arrList[i])
  let index = 0
  while(queue.size() ! = =1) {
    index++
    const takeItem = queue.dequeue()
    if (index % 3! = =0) queue.enqueue(takeItem)
  }
  return queue.head()
}

console.log(delRing(test1))
console.log(delRing(test2))
Copy the code

2. Fibonacci numbers

Topic request

The sequence starts with 0 and 1, and each successive digit is the sum of the preceding two. The NTH time.

Train of thought

This problem has many general solutions, here for the theme, so the way to solve the problem in a queue. Because we know the first two are 0 and 1 to start with. Let’s start at 2, because we know 2 is 0 plus 1 is 1. So we just add two ones to the queue, with the head representing position 1 and the tail representing position 2. And then we loop by argument, n minus 2 because we ignore 0 and 1. And define index to record the number of times the current loop is performed. Each time we take the value at the head of the queue and add it to the rest of the queue to get the next value. Add the value back to the end of the queue. We loop until at the end of the loop, we have two values in the queue, and the value at the end of the queue is our final result. Return the value at the end of the line.

Code implementation
function fibonacci(n) {
  if (n < 2) return n
  const queue = new Queue()
  queue.enqueue(1)
  queue.enqueue(1)
  let index = 0
  while (index < n - 2) {
    const delQueue = queue.dequeue()
    queue.enqueue(delQueue + queue.head())
    index++
  }
  return queue.tail()
}
Copy the code

3. Implement stacks with queues

The three basic operations of the stack, push, POP and top, are implemented by using queues.

Train of thought

We define two queues, Queue1 and queue2, and two variables, dataQueue and emptyQueue. Define an initQueue method that saves an emptyQueue into the emptyQueue variable. Save the queue holding the data to the dataQueue. We need to execute initQueue when we push, pop, and top. When we push, we just add our data to the dataQueue. When pop, we need to remove the element at the end of the queue, but the queue can only exit from the head. Data from the dataQueue can be dequeued and added to emptyQueue until the dataQueue size is 1, indicating that the end of the queue has been reached. So we’re just going to dequeue this element. After deletion, dataQueue is empty. After the next initQueue, the original address of dataQueue will point to emptyQueue and vice versa.

Code implementation
function QueueStack() {
  const queue1 = new Queue()
  const queue2 = new Queue()
  let dataQueue = null
  let emptyQueue = null
  
  function initQueue() {
    if (queue1.isEmpty() && queue2.isEmpty() || queue2.isEmpty()) {
      dataQueue = queue1
      emptyQueue = queue2
    } else {
      dataQueue = queue2
      emptyQueue = queue1
    }
  }
  
  this.push = function(item) {
    initQueue()
    dataQueue.enqueue(item)
  }
  
  this.pop = function() {
    initQueue()
    while (dataQueue.size > 1) {
      emptyQueue.enqueue(dataQueue.dequeue())
    }
    return dataQueue.dequeue()
  }
  
  this.top = function() {
    initQueue()
    return dataQueue.tail()
  }
}
Copy the code

4. Yang Hui Triangle

Train of thought

We define a queue for the elements in row n-1 and row NTH. For example, now loop to line 2, we should have [1, 1, 1] in the queue. When we recirculate, we observe that the number of rows is equal to the number of rows. So we can use the for statement to control the output to the number of lines in the current loop, and output only n-1 rows of data. The remaining n rows are reserved for the next calculation. Output only the last line of data at a time. But because we’re counting each line, the last element is missing, so we just add a 1 at the end.

Code implementation
function printYangHui(n) {
  const queue = new Queue()
  queue.enqueue(1)
  for (let i = 1; i <= n; i++) {
    let output = ""
    let preValue = 0
    for (let j = 0; j < i; j++) {
      const cur = queue.dequeue()
      output += cur + ""
      const next = cur + preValue
      preValue = cur
      queue.enqueue(next)
    }
    queue.enqueue(1)
    console.log(output)
  }
}
Copy the code

The other implementation is basically the same and can be distinguished by tags. The output is terminated when 0 is encountered.

function printYangHui(n) {
  const queue = new Queue()
  queue.enqueue(1)
  queue.enqueue(0)
  for (let i = 1; i <= n; i++) {
    let output = ' '
    let preValue = 0
    while (true) {
      const cur = queue.dequeue()
      if (cur === 0) {
        queue.enqueue(1)
        queue.enqueue(0)
        break
      } else {
        output += cur + ""
        queue.enqueue(cur + preValue)
        preValue = cur
      }
    }
    console.log(output)
  }
}
Copy the code