Shulou(Shulou.com)06/01 Report--

Editor to share with you how to achieve LeetCode circular queue, I believe that most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's go to know it!

The queue is a typical first-in, first-out (FIFO) structure, insert is also called enqueue, and new elements are inserted from the end of the queue. Delete, also known as dequeue, is removed from the head of the team

Queue

Queues can be implemented using arrays in Python, including the following functions:

Enqueue: join the team

Dequeue: out of the team

IsEmpty: determines whether it is empty or not

Size: queue length (number of elements)

Circular queue

The cyclic queue is also a linear structure, which is also based on the FIFO principle, except that the end of the queue is connected to the head of the queue to form a loop, also known as the "ring buffer".

One of the advantages of circular queues is that you can take advantage of the previously used space of the queue.

The circular queue is to set the total length and capacity.

The functions contained in the circular queue:

MyCircularQueue (k): construct a circular queue of length k

Front: get the first element of the team

Rear: get the end-of-line element

Enqueue (value): inserts an element into the circular queue and returns True if successful

Dequeue (): removes an element from the circular queue and returns True if successful

IsFull (): check whether the circular queue is full

IsEmpty (): determines whether the circular queue is empty

Example:

Realization idea

First, the loop queue is a "ring", which uses python's array simulation to build a virtual ring by manipulating the index of the array. For a circular queue, the total length is fixed (that is, the capacity of the array is fixed), and any position can be the head of the queue. Using the head index, the tail index can be derived from the following formula:

Tail_index = (head_index + count-1)% capacity

Parameters in the formula:

Tail_index: end-of-queue index

Head_index: queue leader index

Count: queue length (that is, the actual number of elements)

Capacity: array capacity

Circular queue summary

1. The tail-end index is obtained from the head-of-line index formula.

Tail_index = (head_index + count-1)% capacity2. Set the array capacity capacity3. Queue length count (actual number of elements) 4. The key to the realization of "loop":% capacity5. "insert" is the end of the line, and "delete" is the head of the line.

These are all the contents of the article "how to implement circular queues in LeetCode". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.