Related series

• Data structure series (1) – Arrays
• Data structure series (2) – Linked lists
• Data structure series (3) – stack
• Data structure series (5) – Binary query tree
• Data structure series (6) – Heap

introduce

1. A queue is similar to a stack in that the first data inserted into the queue is the first data removed. It is a first-in, first-out (FIFO) data structure. It’s like waiting in line for tickets, first come, first served.

2. The basic operation of a queue is enque, insert a data at rear and deque, remove and return the data at the front.

3. Since the entry and exit positions are both +1 at the head and end of the queue, data items in the queue do not always start at the 0 index of the array

There is a problem

As shown in the figure below, every time new data is added, the rear of the queue moves back one bit. Soon, the rear of the queue reaches the boundary of the array and no more data can be added. At this point, some data may be out of the queue, but only a few data may exist in the queue. What should I do?

The solution

Wrap around: To avoid the problem of not being able to insert a new item when the queue is full, as soon as the front or rear reaches the edge of the array, the next time it goes back to the beginning of the array, this is a loop queue. As shown in the figure below, the end of the queue points to the boundary of the array F. Now we add data G, the end of the queue points to the head of the array, and the data is added at the subscript 0 of the array.

Broken sequence

As the data to add, of the (rear) after the wrap, will be A party in front of the team first, then the queue data item is an array of two different sequence, the following figure, A and B during the second half after array as A sequence, C, D, E in array the first half for another sequence, this kind of situation can be “broken sequence”.

Team (enque)

If the queue is full, if the current queue ends at the end of the array, the queue ends at the head of the array; otherwise, the queue ends at the array index +1, and then data is inserted at the new queue end, the time complexity is O(1).

The team (deque)

If the queue is not empty, it returns the element to which the current queue head points and points to the index of the array +1. If the current queue head points to the end of the array, it points to the head of the array in time O(1).

Complete implementation

public class Queue<E> {

    / * *

* capacity

* /

    private int maxSize;



    / * *

* The number of existing elements in the current queue

* /

    private int items;



    / * *

* team head

* /

    private int front;



    / * *

* of the

* /

    private int rear;



    / * *

* Data array

* /

    private Object[] array;



    public Queue(int maxSize) {

        this.maxSize = maxSize;

        this.array = new Object[maxSize];

        this.front = 0;

        this.rear = -1;

        this.items = 0;

    }



    / * *

* team

* Verify whether the file is full

* If the current queue ends at the end of the array, we need to loop through the array after deletion, pointing the queue end at the head of the array

     *

     * @paramThe data of data

* /

    public void enque(E data) {

        if (isFull()) {

            System.out.println("New" + data + "Failure: queue is full!!");

            return;

        }

        if (rear == maxSize - 1) {

            rear = -1;

        }

        array[++rear] = data;

        items++;

    }



    / * *

* the team

* Check whether the queue is empty

* If the current header points to the last digit of the array, we need to loop through the array and execute the header to the array header

     *

     * @returnTeam head data

* /

    @SuppressWarnings("unchecked")

    public E deque(a) {

        if (isEmpty()) {

            System.out.println("Delete failed: queue is empty!!");

            return null;

        }

        E frontData = (E) array[front++];

        if (front == maxSize) {

            front = 0;

        }

        items--;

        return frontData;

    }



    / * *

* View the team header element

     *

     * @return E

* /

    @SuppressWarnings("unchecked")

    public E peekFront(a) {

        return (E) array[front];

    }



    / * *

* Look at the end of the team element

     *

     * @return E

* /

    @SuppressWarnings("unchecked")

    public E peekRear(a) {

        return (E) array[rear];

    }



    public boolean isFull(a) {

        return this.items == this.maxSize;

    }



    public boolean isEmpty(a) {

        return this.items == 0;

    }



}

Copy the code

deque

Both the head and tail of a double-ended queue can insert and remove data. If the header insertion and header removal methods are disabled (or tail operations are disabled), it functions as a stack (portal: stack); If you disable the left insert and right remove methods (or the opposite pair), it functions like a queue. It is a versatile data structure that is sometimes used to provide both stack and queue functions.

Priority queue (array implementation)

In a priority queue, items are sorted by priority, so they do not meet the first-in, first-out rule. The data with the lowest priority is never moved and always points to the position with subscript 0 in the array. The higher the finite level, the larger the index of the array. It is usually implemented with a heap, an introduction to which will be covered in a future article.

The team

The data is inserted into the appropriate location in priority order when it is inserted, which is done here

1. Comparison: Compares the data with the highest priority to obtain the index position to be inserted
2. Displacement: The index of data with a higher priority than the inserted data will be +1

Two-step operation, so the insertion efficiency is lower than the ordinary queue, and the time complexity is O(N);

Out of the team

The data with the highest priority is always at the top of the array index, so there is no need to move other data after removal. The time complexity is O(1).

The complete code

/ * *

* Priority queue (array implementation)

* The highest priority is always at the head of the queue, at kitems-1

* The lowest priority is always at the end of the queue, where the array subscript is 0

* The argument specified here must be a class that implements the Comparable interface to compare priorities

* /

public class PriorityQueue<E extends Comparable<E>> {



    / * *

* Maximum queue capacity

* /

    private int maxSize;



    / * *

* The number of existing elements in the current queue

* /

    private int items;



    / * *

* An array that stores data

* /

    private Object[] array;



    public PriorityQueue(int maxSize) {

        this.maxSize = maxSize;

        this.array = new Object[maxSize];

        this.items = 0;

    }



    / * *

* team

* Verify whether the server is full

* From the top of the queue, the priority is greater than the inserted data, index position +1

* /

    @SuppressWarnings("unchecked")

    public void enque(E data) {

        if (isFull()) {

            System.out.println("New" + data + "Failure: queue is full!!");

            return;

        }

        // The index position to insert

        int index;

        for (index = items - 1; index >= 0; index--) {

            // Insert data with precedence over the current element, after the current element

            if (data.compareTo((E) array[index]) >= 0) {

                break;

            }

            // Data with a higher priority than the inserted element is moved one bit later

            array[index + 1] = array[index];

        }

        // Insert data

        array[index + 1] = data;

        items++;

    }



    / * *

* the team

* Verifies whether the queue is empty

* The highest priority is always at the top of the queue, items-1

* /

    @SuppressWarnings("unchecked")

    public E deque(a) {

        if (isEmpty()) {

            System.out.println("Delete failed: queue is empty!!");

            return null;

        }

        return (E) array[--items];

    }



    / * *

View the element with the highest priority

* /

    @SuppressWarnings("unchecked")

    public E peekFront(a) {

        return (E) array[items - 1];

    }



    public boolean isFull(a) {

        return this.items == this.maxSize;

    }



    public boolean isEmpty(a) {

        return this.items == 0;

    }

}

Copy the code

conclusion

• First in, first out (FIFO)
• Insert at one end, delete at the other
• Enque: Inserts an element in rear that points to position +1
• Deque: Removes and returns the element at the front of the queue, which points to position +1
• Loop queue: Loop the array so that the head and tail of the queue return to the beginning of the array
• Data items do not always start at the index 0 of the array
• The lower index of the tail of the queue is smaller than that of the head of the queue and is called a “broken sequence”

• A double-ended queue, in which both the head and tail of a queue can be inserted and deleted, contains stack and queue operations

• Priority queue
  • The data is sorted by priority
  • Do not follow FIFO
  • The highest priority is always at the head of the queue, with subscript (number of elements -1)
  • The lowest priority is always at the end of the queue, where the array subscript is 0
  • This is usually done with a heap

Daily for praise

Creation is not easy, if you feel helpful, please support