Subject to introduce

Force button 622: leetcode-cn.com/problems/de…

Method one: arrays

According to the problem description, the data structure used in this problem should be a ring connected end to end.

There is no ring structure in any data structure, but you can use one-dimensional array simulation to build a virtual ring by manipulating the index of the array. Many complex data structures can be implemented using arrays.

TailIndex = (headIndex + count − 1) mod Capacity for a fixed size array, any position can be the head of the queue. If you know the length of the queue, you can calculate the tail position by using the following formula: tailIndex = (headIndex + count − 1) mod Capacity

Capacity is the array length, count is the queue length, headIndex and tailIndex are the index of the head and tail of the queue respectively. The following figure shows an example of a loop queue using an array.

Based on the above principles, list each attribute of the loop queue and explain its meaning.

• Queue: A fixed-size array that holds the elements of a circular queue.

• HeadIndex: an integer that holds the index of the head of the queue.

• Count: The current length of the loop queue, i.e. the number of elements in the loop queue. Use hadIndex and count to calculate the index of the end-of-queue element, so end-of-queue attributes are not required.

• Capacity: Indicates the capacity of the circular queue, that is, the maximum number of elements that can be held in the queue. This property is not required because the queue capacity can be obtained through the array property, but because it is often used, we choose to keep it. This way you don’t have to fetch the capacity every time len(queue) is called in Python. But in Java, it’s more efficient to get the capacity through queue.length. For consistency, this property is retained in both scenarios.

The code is as follows:

class MyCircularQueue {
    private int[] queue;// Store queue elements
    private int headIndex;/ / head index
    private int count;// Number of current queue nodes
    private int capacity;// The size of the current queue

    /** Initialize your data structure here. Set the size of the queue to be k. */
    public MyCircularQueue(int k) {
        this.capacity = k;
        this.queue = new int[k];
        this.headIndex = 0;
        this.count = 0;
    }

    /** * queue */
    public boolean enQueue(int value) {
        // The queue is full
        if (this.count == this.capacity)
            return false;
        // Computes the next index of the trailing index
        this.queue[(this.headIndex + this.count) % this.capacity] = value;
        this.count += 1;
        return true;
    }

    /** ** queue */
    public boolean deQueue(a) {
        // The queue element is empty
        if (this.count == 0)
            return false;
        // Adjust the header index
        this.headIndex = (this.headIndex + 1) % this.capacity;
        // The number of queue elements is reduced by one
        this.count -= 1;
        return true;
    }

    /** * gets the header element, the element corresponding to the header index */
    public int Front(a) {
        if (this.count == 0)
            return -1;
        return this.queue[this.headIndex];
    }

    /** * gets the trailing element, the element corresponding to the trailing index */
    public int Rear(a) {
        if (this.count == 0)
            return -1;
        int tailIndex = (this.headIndex + this.count - 1) % this.capacity;
        return this.queue[tailIndex];
    }

    /** * Check whether the queue is empty */
    public boolean isEmpty(a) {
        return (this.count == 0);
    }

    /** * Check whether the queue is full */
    public boolean isFull(a) {
        return (this.count == this.capacity); }}Copy the code

We can also use double Pointers, one to the head element and one to the tail element, as follows:

public class MyCircularQueue {
    private int[] data; // The length of the loop queue is fixed
    private int head;
    private int tail;
    private int size;

    public MyCircularQueue(int k) { // constructor
        data = new int[k];
        head = -1;
        tail = -1;
        size = k;
    }

    /** Inserts the element into the loop queue. Returns true */ if the operation succeeds
    public boolean enQueue(int value) {
        // If the queue is full, new elements cannot be added successfully, return false
        if (isFull()) {
            return false;
        }
        if (isEmpty()) {
            head = 0;
        }
        tail = (tail + 1) % size; // Calculate the value of the next tail
        data[tail] = value;
        return true;
    }

    /** Removes an element from the loop queue. Returns true */ if the operation succeeds
    public boolean deQueue(a) {
        // If the queue is empty, the element cannot be deleted successfully, return false
        if (isEmpty()) {
            return false;
        }
        if (head == tail) { // There is only one element
            head = -1;
            tail = -1;
        } else {
            head = (head + 1) % size; // head moves by 1
        }
        return true;
    }

    /** Retrieve elements from the head of the team. If the queue is empty, -1 */ is returned
    public int Front(a) {
        if (isEmpty()) {
            return -1;
        }
        return data[head];
    }

    /** Get the last element of the queue. If the queue is empty, -1 */ is returned
    public int Rear(a) {
        if (isEmpty()) {
            return -1;
        }
        return data[tail];
    }

    /** Check if the loop queue is empty */
    public boolean isEmpty(a) {
        return head == -1;
    }

    /** Check if the loop queue is full */
    public boolean isFull(a) {
        return (tail + 1) % size == head; }}Copy the code

Complexity analysis

• Time complexity: O(1). In this data structure, all methods have constant time complexity.

• Space complexity: O(N), where N is the pre-allocated capacity of the queue. This pre-allocated space is held for the entire life of the circular queue.