“This is the fourth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Summary: A queue is a common data structure. It is a special kind of linear table. It allows only delete operations at the front of the table and insert operations at the rear of the table. The end that inserts is called the end of the queue, and the end that deletes is called the head of the queue.

preface

The front-end algorithm series is a record of my algorithm learning, which mainly analyzes the learning algorithm knowledge from common algorithms, data structure, algorithm thinking and common skills. It realizes deliberate practice through LeetCode platform, and practices Feynman learning method through digging gold and the output of STATION B. I will update the quality content and synchronously update it to Nuggets, B station and Github in the future, so as to record the complete process of learning algorithm. Welcome to communicate, like and collect more, let us make progress together, daydayUp 👊

Directory address: directory section

Code address: Github

Bilibili – 100 days algorithm series

What is a queue

Queue could be seen in our daily life most a data structure, such as need to line up our every day in the subway security checks, noon meal need to line up dozen rice, etc., are the queue in the reflection of life, as a kind of linear table structure We usually do the queue and stack, compared with the stack out after the first, adhere to the principle of first-in, first-out queue.

We call the process of inserting data from the back of the queue joining

We call the process of deleting data from the head of the team out of the team

Second, the characteristics of queues

Compared with the characteristics of stacks, queues have the following characteristics:

  • On both ends of the operation
  • First in, first out

Without it, remember first in, first out.

Third, the application of queues

With regard to the application of the queue, we the most familiar is the browser message queue, personal understanding queue actually biggest role is that current limiting and buffer, it will allow us to some now too late to deal with things according to the order of the stored, after we solved the present, to deal with the rest of the things in the future.

  • The task queue of the thread pool

When a process involves frequent thread creation and destruction, because thread to create the cost is very big, in order to make our threads are not frequent create and delete, so we put forward the concept of the thread pool, and the number of threads in the pool is limited, when the task of the thread pool can’t handle a large number of concurrent tasks, We can create a queue for buffering.

  • CPU hyperthreading technology
  • The task queue of the thread pool
  • Task scheduler
  • Maze problem
  • Yang hui triangle
  • Fibonacci numbers
  • Breadth-first Search for binary trees (BFS)

(Ask to add…)

In fact, simple data structures such as stacks and queues, the simpler they are, the more widely used and basic they are, often presented as a small part of an algorithm.

Fourth, the front end of the queue

The basic implementation of queues usually has two kinds, one is through the array to achieve the sequential queue, and one is through the linked list to achieve the chain queue, the difference between the two methods is mainly between the array and the linked list.

In addition, on the basis of the simple queue, we also have circular queue, double-ended queue, monotonous queue, priority queue and other implementation methods applied to different scenarios, but this is not the main content of this article, will be analyzed in the subsequent queue article.

// Array implementation
function Queue(k) {
  let head = 0
  let tail = 0
  let items = new Array(k)

  // Append the element to the end
  this.enqueue = function (item) {
    if (this.isFull()) return -1
    items[tail] = item
    tail++
  }

  // Delete the element in the header
  this.dequeue = function () {
    if (this.isEmpty()) return
    head++
  }

  // return to the queue head
  this.head = function () {
    return items[head]
  }

  // return to the end of the queue
  this.tail = function () {
    return items[tail]
  }

  // Queue size
  this.size = function () {
    return tail - size
  }

  // Whether the queue is empty
  this.isEmpty = function () {
    return tail === head
  }
  
  / / is full
  this.isFull = function () {
    return tail === items.length
  }

  // Clear the queue
  this.clear = function () {
    items = new Array(k)
  }

  / / print
  this.print = function () {
    console.log(items)
  }
}
Copy the code

Five, queue algorithm practice

// leetcode: https://leetcode-cn.com/

LeetCode #621Task scheduler LeetCode #622Design loop queue LeetCode #641Design a loop double - ended queue LeetCode #1670Design before middle after queue LeetCode #933LeetCode # Interview questions1709The KTH number LeetCode #859The intimate string LeetCode #860Lemonade change LeetCode #969Sort pancakes by LeetCode #86Separate linked list LeetCode #138Linked lists with random PointersCopy the code