1. Concept (Queue)

As with the data structure of the stack mentioned earlier, the data in the queue is arranged linearly. Although somewhat similar to a stack, data is added and removed from a queue at both ends. Like the name “queue,” it’s easier to think of it as a line of people. In the queue, processing always starts from the first to the last, and new arrivals are relegated to the back of the queue.

Second, the characteristics of

  • LIFO(First In First Out) means that the data added First is retrieved First
  • Linear structural arrangement

Note that, like stacks, there are limits to where data can be manipulated in queues. On the stack, data is added and deleted on the same side, while on the queue, data is added and deleted on both sides. The queue cannot directly access the data in the middle. The queue must be dequeued to make the target data first.

Three, javascript simple implementation

Let’s start by enumerating the basic methods a queue needs to implement:

  • Enqueue is added to the end of the queue.
  • The dequeue is dequeued. The first data in the queue is removed.
  • Peek gets the data at the front of the queue (only for viewing, not changing the queue data)
  • Size returns the number of queue elements
  • IsEmpty returns whether the queue isEmpty
  • Clear Clear queue
  • ToArray converts a queue to an array

Same as the data structure of the stack mentioned above, we use WeakMap and closure to realize method privatization:

export let Queue = (function(){ const items = new WeakMap(); class Que { constructor(){ items.set(this,[]); } enqueue(item){ let q = items.get(this); q.push(item) } dequeue(){ let q = items.get(this); return q.shift(); } peek(){ let q = items.get(this); return q.length > 0 ? q[q.length -1] : undefined; } size(){ let q = items.get(this); return q.length; } clear(){ let q = items.get(this); q = []; } isEmpty(){ let q = items.get(this); return q.length <= 0; } toArray(){ return items.get(this); } } return Que; }) ()Copy the code

Four, the actual use of Queue

1. Beat the drum and pass the flowers

A group of people form a circle to pass flowers around, and whoever has the flowers when they call stop is eliminated (everyone may be at the front, and each participant’s position in the queue changes constantly), and when there is only one left, the winner is the winner. It’s like when you’re a kid and you’re in a circle and you’re throwing handkerchiefs.

const getWinner = (arr,num) => { let len = arr.length; let out = []; const queue = new Queue(); for(let i=0; i<len; i++){ queue.enqueue(arr[i]); } while(queue.size() >1){for(let j=0; j<num -1; Queue. Enqueue (queue. Dequeue ()); queue. console.log(queue.toArray()); Push (queue.dequeue()); push(queue.dequeue()); Console. log(' this round is already out :',out); } const winner = queue.dequeue(); console.log('winner is ' + winner); return winner; } getWinner (,2,4,5,6,7,9] [1, 2); // Eliminate the second person each timeCopy the code

2. Base conversion

const toBainary = num =>{ const queue = new Queue(); while(num>0){ queue.enqueue(num % 2); num = parseInt(num / 2); Return queue.toarray ().reverse().join(''); return queue.toarray ().reverse().join(''); }Copy the code

3. Breadth First (BFS) search algorithm

“First come first” is a very common idea, so the application of queues is very broad. The most common breadth-first search algorithm usually selects the earliest data from the search candidates as the next vertex. At this point, queues can be used for the management of alternate vertices.

I’m going to leave a hole here, for example, for the maze problem, for the path problem algorithm, and we’ll talk about it in more detail.