1. Introduction to queues:

A queue is a special kind of linear table, special in that it:

  • Delete operations are allowed only at the front of the table and insert operations are allowed only at the rear.
  • Like a stack, a queue is a linear table with limited operations. The end that inserts is called the end of the queue, and the end that deletes is called the head of the queue. A queue with no elements is called an empty queue.

The data elements of a queue are also called queue elements. Inserting a queue element into a queue is called enqueueing, and removing a queue element from a queue is called enqueueing. Because the queue can only be inserted at one end and deleted at the other end, only the earliest element in the queue can be deleted from the queue first, so the queue is also called a first-in, first-out (FIFO) linear table.

2. Some operation methods of queue:
  • enqueue(element): Adds (or reads) a new item to the end of the queue.
  • dequeue(): Removes the first item in the queue and returns the removed element.
  • front(): returns the first element in the queue, the first to be added, and the first to be removed. The queue does nothing (does not overflow elements, only returns element information – very similar to the PEEK method of the Stack class).
  • isEmpty(): Returns true if the queue contains no elements, false otherwise.
  • size(): Returns the number of elements contained in the queue, similar to the length property of an array.
  • toString(): Converts the contents of the queue to a string.
3. Encapsulate the above methods:
// Encapsulate the above methods: Queue.prototype.enqueue = function(element){function Queue(){this.items = []; Queue.prototype. Dequeue = function(){return this.items.shift()} //front Queue.prototype.front = function(){return this.items[0]} //isEmpty queue.prototype. isEmpty = Queue. Prototype. Size = function(){return this.items. Function (){this.items. Join (',')}} // var Queue = new Queue() // queue.enqueue('1') // queue.enqueue('2') // queue.enqueue('3') // queue.dequeue() // console.log(queue.items)Copy the code
4. Application:

  • Think of the train station as a queue. When the train pulls in, the train in the first station starts first. Conforms to the first in, first out characteristics of the queue.

  • Think of the dining room as a queue. Restaurant staff, first in, first out.

5.

ABCDEF 6 elements enter a queue one by one.

  • (1) ABCDEF
  • (2) ABDCFE
  • (3) BAFEDC
  • (4) ABCFED
6. Interview questions

For example, the number is A, B, C, D, E, F, 6 people around the table (clockwise), the judge say A number, this number is ABCDEF6 people need to report the number, in order to count (for example, the judge said this number is 3, then A number 1, B number 2,…) When the number is reported, the person is eliminated, the next person is eliminated, count again from 1 (according to the table around), until the last person left, as the winner.

// Use the encapsulation method described above. Come undone. Function passGame(nameList,num){var newQueue = newQueue (); For (var I =0; i<nameList.length; I ++){newQueue. Enqueue (nameList[I])} // 3, if the element in the queue is greater than 1, continue the game. While (newqueue.size ()>1){for(var I =0; i<num-1; I++){newqueue.enqueue (newqueue.dequeue ())} Newqueue.dequeue ()} var endName = newqueue.front () console.log(endName) return namelist.indexof (endName) // Return the subscript of the last element} // 4, verify:  var names = ['tom','jack','lili','lucy','merry','zhangsan','lisi','wangwu'] console.log(passGame(names,5))Copy the code
7, realize

A preliminary understanding of the idea of the algorithm, the principle of the whole understand abstract structure, want to figure out the realization of an algorithm, first of all to roughly know the principle of the algorithm, this is the simplest step, but also the most basic step.