Hi everyone, I am DHL. ByteCode, focus on the latest technology to share original articles, involving Kotlin, Jetpack, algorithm animation, data structure, system source code, LeetCode/point Offer/multithreading/domestic and foreign large factory algorithm problems and so on.

After reading this article, head over to LeetCode

  • Problem No. 622: Design a loop queue

I’ve unknowingly written three articles on stacks and queues so far, so click on the link below to check them out.

  • | algorithm animation diagrams are “abandoned” Java stack, why still use
    • Why not use the Java stack? Why do so many people still use it?
    • Why recommendedDequeInterface to replace Java stack?
    • What’s the difference between Stack and ArrayDeque?
    • Stack time complexity?
  • Why not recommend ArrayDeque instead of Stack
    • JDK recommended useArrayDequeInstead ofStackIs it really reasonable?
    • How to implement a true stack?
  • Diagram ArrayDeque is faster than LinkedList
    • ArrayDeque 和 LinkedListData structure characteristics?
    • whyArrayDeque 比 LinkedListFast?

This article, part 4, will focus on how to design a loop queue. Before learning how to design a loop queue, let’s take a look at how the JDK source code is designed.

In this article you will learn the following:

  • What is the definition of a queue?
  • How does the JDK source code design queues?
  • Why is the queue size set to an integer power of 2?
  • How much faster is bitwise operation than non-bitwise operation?
  • What is the difference between ArrayDeque’s integer power of 2 calculation logic and HashMap?
  • How do I design a loop queue?

Definition of queues

Before we start looking at how the JDK source code designs circular queues, we need to understand the basics of queues.

A queue is a special linear first-in, first-out (FIFO) table. In Java, there are two forms of queues, AbstractQueue and Deque. The effect of a one-way queue is shown below.

A Deque is a linear data structure of a two-ended queue that can be inserted and deleted at both ends, as shown below.

The subclasses of Deque are ArrayDeque and LinkedList respectively. ArrayDeque is based on the dual-ended queue implemented by array, while LinkedList is based on the dual-ended queue implemented by bidirectional LinkedList. Their inheritance relationship is shown in the figure below.

Circular queue

A circular queue is a linear data structure that connects the tail of the queue to the head, forming a ring, whereas ArrayDeque in Java is a two-ended array based queue and LinkedList is a chained queue.

For more on the pros and cons of ArrayDeque and LinkedList, when they are used, and who is faster, head over to the diagram ArrayDeque is Faster than LinkedList

The characteristics of ArrayDeque and LinkedList data structures are as follows:

Collection types The data structure Initialization and capacity expansion Insert/delete time complexity Query time Complexity Thread safe or not
ArrqyDeque Circular array Initialization: 16

Capacity expansion: 2 times		 0(n) O (1) no
LinkedList Two-way linked list There is no O (1) 0(n) no

In the last article, ArrayDeque was illustrated that ArrayDeque was faster than LinkedList. The performance of ArrayDeque was better than LinkedList from both speed and memory, and the results were verified in combination with actual cases, as shown in the figure below.

ArrayDeque source code analysis

The purpose of this article is mainly to analyze the circular queue, we first look at the JDK source code is based on the form of an array to achieve a double-ended queue, ArrayDeque inheritance relationship as shown in the following figure.

Interface Deque and Queue provides two sets of apis, there are two forms, an exception is thrown, respectively, and is not an exception is thrown, return a special value null or Boolean value (true | false).

Operation type An exception is thrown Return special value
insert addXXX(e) offerXXX(e)
remove removeXXX() pollXXX()
To find the element() peekXXX()

Analysis of member variables

ArrayDeque contains four variables: elements, head pointer, tail pointer, and MIN_INITIAL_CAPACITY

// The length of the array is always an integer power of 2. // a header pointer, indicating a transient int head; // Transient int tail; Private static final int MIN_INITIAL_CAPACITY = 8; private static final int MIN_INITIAL_CAPACITY = 8; private static final int MIN_INITIAL_CAPACITY = 8;Copy the code

Analysis of construction method

Constructors have parameter constructors and no parameter constructors respectively. Here we mainly focus on the calculation logic of the integer power of 2.

Public ArrayDeque() {elements = new Object[16]; public ArrayDeque() {elements = new Object[16]; } public ArrayDeque(int numElements) { allocateElements(numElements); } // Calculate the size of the array, The return value is the nearest power of 2. Private void allocateElements(int numElements) {// the minimum initialCapacity is 8 (JDK 8) int initialCapacity = MIN_INITIAL_CAPACITY; If (numElements >= initialCapacity) {// If (numElements >= initialCapacity) {// If (numElements >= initialCapacity) {// If (numElements >= initialCapacity) {// If (numElements >= initialCapacity) {// If (numElements >= initialCapacity) {// If (numElements >= initialCapacity) {// If (numElements >= initialCapacity); initialCapacity |= (initialCapacity >>> 1); initialCapacity |= (initialCapacity >>> 2); initialCapacity |= (initialCapacity >>> 4); initialCapacity |= (initialCapacity >>> 8); initialCapacity |= (initialCapacity >>> 16); initialCapacity++; If (initialCapacity < 0) initialCapacity >>>= 1; if (initialCapacity < 0) initialCapacity >>>= 1; } elements = new Object[initialCapacity]; }Copy the code
  • Constructor with no arguments (default) that directly initializes an array of size 16
  • The parameterized constructor initializes an array of the size closest to the power of 2. whileallocateElements(numElements)Method returns the nearest integer power of 2

Why is it an integer power of 2

The sum of any number and 2^n-1 ensures that the head index and tail index fall within the range of the queue. A positive number x and 2^n-1 are summed as follows.

For example, 2^n-1 = 16 int len = 16; int x1 = 6 & (len -1); System.out.println("x1 = " + x1); // x1 = 6 x1 = 20 & (len -1); System.out.println("x1 = " + x1); // x1 = 4Copy the code

And a negative number x and 2 to the n minus 1, the result is as follows.

For example, 2^n-1 = 16 int len = 16; int x1 = -10 & (len - 1); System.out.println("x1 = " + x1); // x1 = 6 x1 = 0 & (len - 1); System.out.println("x1 = " + x1); // x1 = 0 x1 = -20 & (len - 1); System.out.println("x1 = " + x1); // x1 = 12Copy the code

Note:

ArrayDeque’s integer power of 2 calculation logic is a little different from that of HashMap, as shown in the figure below.

ArrayDeque does not. The difference is that if you pass in 8, which is exactly a power of 2, ArrayDeque calculates 16. The result of a HashMap is itself 8. The purpose of doing this is to save memory.

Element team analysis

Insert elements into the queue either through the add(e) or offer(e) methods. You end up calling addLast(E E).

. public void addLast(E e) { if (e == null) throw new NullPointerException(); elements[tail] = e; if ( (tail = (tail + 1) & (elements.length - 1)) == head) doubleCapacity(); // Double the size of the array.Copy the code

In the above code, the implementation of the loop queue, the core is the following sentence.

(tail = (tail + 1) & (elements.length - 1)) == head
Copy the code
  • Recalculate the next position to which tail’s index points
  • Checks whether the queue is full and executes if it isdoubleCapacity()Method to expand capacity

Check whether the queue is empty by using the following method.

public boolean isEmpty() {
    return head == tail;
}
Copy the code

If the index of the head pointer is the same as that of the tail pointer, the current queue is empty.

Element team analysis

Either the add(e) or offer(e) methods remove elements from the queue. You end up calling the pollFirst() method.

public E pollFirst() { int h = head; @SuppressWarnings("unchecked") E result = (E) elements[h]; If (result == null) return null; elements[h] = null; Head = (h + 1) & (elements. Length-1); // recalculate the next position to which head points return result; }Copy the code

The most important algorithm of ArrayDeque is to ensure that the index of the head pointer and the index of the tail pointer fall within the range of the queue by performing an and operation on any number x and 2^n-1.

The JDK does this to improve the efficiency of programs, so let’s use an example to verify the efficiency of bit-based and non-bit-based operations.

Design loop queue

For reasons of space, this article demonstrates only one language. For more language implementations, go to see design loop queues

The title comes from Question 622 in LeetCode: Designing a circular queue. In Medium.

  • English address: https://leetcode.com/problems/design-circular-queue
  • Chinese address: https://leetcode-cn.com/problems/design-circular-queue

Topic describes

Design your loop queue implementation. A circular queue is a linear data structure that operates on a FIFO (first-in, first-out) basis and the tail of the queue is connected behind the head of the queue to form a loop. It is also known as a “ring buffer”.

One of the nice things about a circular queue is that we can use the space that the queue has previously used. In a normal queue, once a queue is full, we cannot insert the next element, even though there is still space in front of the queue. But with circular queues, we can use that space to store new values.

Your implementation should support the following:

  • MyCircularQueue(k): constructor that sets the queue length to K.
  • Front: Retrieves elements from the team leader. If the queue is empty, -1 is returned.
  • Rear: Gets the last element of the team. If the queue is empty, -1 is returned.
  • EnQueue (value): Inserts an element into the loop queue. Return true on successful insertion.
  • DeQueue (): Removes an element from the loop queue. Return true if deleted successfully.
  • IsEmpty (): checks if the loop queue isEmpty.
  • IsFull (): checks if the loop queue isFull.

Example:

MyCircularQueue circularQueue = new MyCircularQueue(3); Circularqueue.enqueue (1); // Set the length to 3 circularqueue.enqueue (1); Circularqueue.enqueue (2); Circularqueue.enqueue (3); Circularqueue.enqueue (4); // Return false, the queue is full circularqueue.rear (); Circularqueue.isfull (); Circularqueue.dequeue (); Circularqueue.enqueue (4); // Return true circularqueue.rear (); / / return 4Copy the code

Tip:

  • All values are in the range 0 to 1000
  • The operands will be in the range 1 to 1000
  • Do not use the built-in queue library

Method one: bit operation

Meanings of parameters:

  • data: represents a fixed array used as a circular queue whose length is the nearest power of 2
  • allocateElements(): calculates the size of the queue and returns the nearest integer power of 2
  • head: represents the header pointer index of the queue
  • tail: indicates the tail pointer index of the queue
  • count: indicates the number of elements in the queue
  • size: indicates the maximum number of elements a queue can hold

Checks whether the queue is full

((tail + 1) & (data.length - 1)) == head || (count >= size)
Copy the code
  • Any sum of numbers2^n-1Do the and operation to ensure the head pointerheadAnd the tail pointertailIndex, all fall within the range of the queue
  • The length of the queue is the nearest power of 2, which is greater than the actual queue size, so you need variablescountCount the number of elements in the current queue ifcount >= sizeIndicates that the queue is full

Checks whether the queue is empty

head == tail
Copy the code

Complexity analysis:

  • Time complexity: O(1), array storage is stored in order, with the characteristics of random access
  • Space complexity: O(N) where N is the length of the array

Code implementation:

class MyCircularQueue { private int size; private int head; private int tail; private int[] data; private int count; public MyCircularQueue(int k) { size = k; data = new int[allocateElements(k)]; } // Calculate the size of the queue and return the nearest power of 2 int allocateElements(int numElements) {int initialCapacity = numElements; / / adjust to the nearest integer power of 2, such as 9 - > 16 initialCapacity | = (initialCapacity > > > 1); initialCapacity |= (initialCapacity >>> 2); initialCapacity |= (initialCapacity >>> 4); initialCapacity |= (initialCapacity >>> 8); initialCapacity |= (initialCapacity >>> 16); initialCapacity++; If (initialCapacity < 0) initialCapacity >>>= 1; if (initialCapacity < 0) initialCapacity >>>= 1; return initialCapacity; } public boolean enQueue(int value) { if (isFull()) { return false; } data[tail] = value; tail = (tail + 1) & (data.length - 1); count++; return true; } public boolean deQueue() { if (isEmpty()) { return false; } head = (head + 1) & (data.length - 1); count--; return true; } public int Front() { if (isEmpty()) { return -1; } return data[head]; } public int Rear() { if (isEmpty()) { return -1; Return data[(tail - 1) & (data.length-1)]; return data[(tail - 1) & (data.length-1)]; } public boolean isEmpty() { return head == tail; } public boolean isFull() { return ((tail + 1) & (data.length - 1)) == head || (count >= size); }}Copy the code

Method two: non – bit operation

Meanings of parameters:

  • data: represents a fixed array that is used as a loop queue
  • head: represents the header pointer to the queue
  • tail: indicates the tail pointer of the queue

Checks whether the queue is full

(tail + 1) % size == head
Copy the code

Checks whether the queue is empty

head == tail
Copy the code

Complexity analysis:

  • Time complexity: O(1), array storage is stored in order, with the characteristics of random access
  • Space complexity: O(N) where N is the length of the array

Code implementation

class MyCircularQueue { int[] data; int head; int tail; int size; Public MyCircularQueue(int k) {// k + 1 for two reasons // 1. To avoid collisions, there must be at least one place in the loop array that does not hold a valid element at any one time. When k = 4, the subscript starts at 0, assuming that head is not moved, and k is not +1, the fourth element will never fit in size = k +1; data = new int[size]; head = 0; tail = 0; } public boolean enQueue(int value) { if (isFull()) return false; data[tail] = value; tail = (tail + 1) % size; return true; } public boolean deQueue() { if (isEmpty()) return false; head = (head + 1) % size; return true; } public int Front() { if (isEmpty()) return -1; return data[head]; } public int Rear() { if (isEmpty()) return -1; // There must be at least one valid element in the array at any given time, so tail-1 takes the most recently stored element. // If tail = 0, tail -1 becomes a negative number, and the subscript is out of bounds. Tail - 1 + size) % size return data[(tail - 1 + size) % size]; } public boolean isEmpty() { return head == tail; } public boolean isFull() { return (tail + 1) % size == head; }}Copy the code

Comparison of the performance efficiency of bitwise and non-bitwise operations.

It is obvious that the efficiency of bit operation is much higher than that of non-bit operation, and the larger the amount of data is, the bigger the gap will be. In the test process, I submitted by bit operation, and beat 100% of the users in Java submission.


A “like” would be the biggest encouragement if it helps

More code, more articles

Welcome to the public account: ByteCode, continue to share the latest technology


Finally, recommend long-term update and maintenance projects:

  • Personal blog, will all articles classification, welcome to check hi-dhl.com

  • KtKit compact and practical, written in Kotlin language tool library, welcome to check KtKit

  • Androidx-jetpack-practice androidX-Jetpack-practice androidX-Jetpack-practice androidX-Jetpack-Practice androidX-Jetpack-Practice

  • LeetCode/multiple thread solution, language Java and Kotlin, including a variety of solutions, problem solving ideas, time complexity, spatial complexity analysis

    • Job interview with major companies at home and abroad
    • LeetCode: Read online

Must-read articles these days

  • Diagram ArrayDeque is faster than LinkedList
  • Why not recommend ArrayDeque instead of Stack
  • | algorithm animation diagrams are “abandoned” Java stack, why still use
  • Kotlin code affecting Performance (1)
  • Jetpack Splashscreen parsing | power generation IT migrant workers get twice the result with half the effort
  • Kotlin’s Technique and Analysis (3)
  • Kotlin’s Technique and Principle Analysis that few people know (II)
  • Kotlin’s Technique and Principle Analysis that few people know (1)
  • Uncover the == and === in Kotlin
  • The Kotlin hermetic class evolved
  • The sealed class in Kotlin is superior to the tagged class
  • What is Kotlin Sealed? Why does Google use it all
  • Android 12 behavior changes that affect applications
  • AndroidStudio
  • Kotlin StateFlow search features practice DB + NetWork
  • The end of the Kotlin plugin and the rise of ViewBinding