Constrained linear structure

Another constrained linear structure: the stack structure

This limited data structure is particularly useful for solving certain problems

There is another limited data structure: queues

Queue (Queue)

It’s a limited linear table, first in, first out

The limitation is that he only allows deletions at the front of the table

Inserts are performed at the back end of the table

Queues, like stacks, can be implemented in two ways

Array-based implementation

Based on linked list implementation

What are the common operations on queues

Enqueue (Element) : Adds one or more new items to the end of the queue

Dequeue () : Removes the first item in the queue and returns the removed element (first in the queue)

Front () : returns the first element in the queue — the first element added, that is, the first element removed. The queue does not change, only returns

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 of the array

ToString () : Converts the contents of a queue to a string

Class Queue {// constructor() {this.items = []} // method // 1. Enqueue (element) {this.items.push(element)} // 2 Dequeue () {return this.items. Shift ()} // 3 Front () {return this.items[0]} // 4. IsEmpty () {return this.items. Length === 0} // 5. Size () {return this.items. Length} // 6.toString method toString() {let res = "for (let I = 0; i < this.items.length; i++){ res += this.items[i] + ' ' } return res } }Copy the code

Interview question: Using a queue to achieve a drum pass

Function passGame(nameList,num){// 1. Let queue = new queue () // 2 Join everyone in the queue for (let I = 0; i < nameList.length; i++){ queue.enqueue(nameList[i]) } // 3. While (queue.size() > 1){// If num is not, rejoin the queue // if nun, remove it from the queue for (let I = 0; i < num - 1; I++){queue.enqueue(queue.dequeue())} Console.log (queue.size()) console.log(queue.front()) console.log(namelist.indexof (queue.front()))} passGame(['a','b','c','d','e','f','g'],4)Copy the code