@TOC

Definition of queues

Queue is a special kind of linear table. What is special is that it only allows deletion in the front of the table and insertion in the rear of the table. Like stack, queue is a linear table with limited operation. The end that performs the insert operation is called the tail of the queue, and the end that performs the delete operation is called the head of the queue.

Method of queue

1. Enqueue (Element): Adds one (or more) new entries to the end of the queue.
2. Dequeue () : Removes the first (or first) item in the queue and returns the removed element.
3. Front (): returns that the first element in the queue __ was added first and will be the first to be removed. Nothing is done to the queue (no element is removed and only element information is returned – much like the peek method of the Stack class).
4. IsEmpty (): returns true if the queue contains no elements, false otherwise.
5. Size (): returns the number of elements in the queue, similar to the length attribute of an array.
6. ToString (): converts the contents of the queue to a string

Simple encapsulation of queues

    // Queue packaging is first in, first out
    function Queue (element) {
      / / property
      this.items = []
      / / method
      // 1. Add elements to the queue
      Queue.prototype.enqueue = function (element) {
        this.items.push(element)
      }
      // 2. Remove the front element from the queue and delete it
      Queue.prototype.dequeue = function () {
        return this.items.shift()
      }
      // 3. Take a look at the front-end elements
      Queue.prototype.front = function () {
        return this.items[0]}// 4. Check whether the queue is empty
      Queue.prototype.isEmpty = function () {
        return this.items.length === 0
      }
      // 5. Obtain the number of elements in the queue
      Queue.prototype.size = function () {
        return this.items.length
      }
      // 6. ToString method
      Queue.prototype.toString = function () {
        return this.items.join(' ')}}Copy the code

call

	let q = new Queue()
	q.enqueue('District Wudang District')
	q.enqueue('District black')
	q.enqueue('District Black 23')
	q.enqueue(123)
	q.enqueue(1)
	alert(q)
	alert(q.dequeue())
	alert(q.front())
	alert(q.isEmpty())
	alert(q.size())
	alert(q.toString()) 
Copy the code

Interview question –> drum pass flowers

  // Beat the drum to pass the flowers
    function passGame (nameList, num) {
      // 1. Create queue
      let queue = new Queue()
      // 2. Add everyone to the queue in turn
      for (let i = 0; i < nameList.length; i++) {
        queue.enqueue(nameList[i])
      }
      /* 3. Delete the num number from the queue and add it back to the end of the queue
     while (queue.size() > 1) { 
      for (let i = 0; i < num - 1; i++) {
        queue.enqueue(queue.dequeue())
      }
      // 3.2 Num Delete the number of
      queue.dequeue()
     }
      // 4. Get the remaining one
      // alert(queue.size())
      let endName = queue.front()
      alert('The last person left is:' + endName)
      return nameList.indexOf(endName)
    }
    let arr = ['Lily'.'Lucy'.'Tom'.'Lilei'.'Why']
    alert(passGame(arr, 3))
Copy the code

The illustration

Priority queue implementation

      // Encapsulate the priority queue
      function ProorityQueue () {
        // Create a class in the PriorityQueue: inner class
        function QueueElement (element, priority) {
          this.element = element
          this.priority = priority
        }
        // Encapsulate attributes
        this.items = []

        ProorityQueue.prototype.enqueue = function (element, priority) {
          // Create QueueElement object
          let queueElement = new QueueElement(element, priority)
          // If the array has no elements, do not add them directly
          if (this.items.length === 0) {
            this.items.push(queueElement)
          } else {
            let added = false
            // Iterate over the elements for comparison
            for (let i = 0 ; i < this.items.length ; i++) {
              // Determine the priority
              if (queueElement.priority < this.items[i].priority) {
                this.items.splice(i, 0, queueElement)
                added = true
                break; }}if(! added) {this.items.push(queueElement)
            }
          }
        }
        // 2. Remove the front element from the queue and delete it
        ProorityQueue.prototype.dequeue = function () {
          return this.items.shift()
        }
        // 3. Take a look at the front-end elements
        ProorityQueue.prototype.front = function () {
          return this.items[0]}// 4. Check whether the queue is empty
        ProorityQueue.prototype.isEmpty = function () {
          return this.items.length === 0
        }
        // 5. Obtain the number of elements in the queue
        ProorityQueue.prototype.size = function () {
          return this.items.length
        }
        // 6. ToString method
        ProorityQueue.prototype.toString = function () {
          // return this.items.join(' ')
          let str = ' '
          this.items.forEach((item, i) = > {
            str += item.element + ' ' + item.priority + The '-'
          })
          return str
        }
      }


Copy the code