preface
- The content of this article is the summary and supplement of the scattered notes I made when learning the data structure. It is inevitable that there are defects in the sorting process. If you find any errors, please point them out in time. Thank you!
Part I - > Basic concepts and understanding
Part II ---- > algorithm
Part III - > Algorithm overview supplement
Part IV - > Data structure overview supplement
Part V - > Detailed implementation of Java linear table
Part VI - > Detailed implementation of Java stack
Part VII ---- > Detailed implementation of Java queue
Queue
4.1 scenario
- When using the computer, the machine is sometimes in a suspected crash state, and there is no response to the mouse click. When he loses patience and plans to shut down and restart, he suddenly wakes up and executes all the operations just clicked in sequence. This is because multiple programs of the operating system need to output through one channel and wait in sequence.
- There are also some customer service personnel in the system. The customer service personnel are limited. When the number of consultants is greater than the total number of customer service personnel, they need to queue up. When which customer service personnel is free, they will arrange the first person to queue up.
4.2 what is queue structure
-
The queue structure is linear in logic and can be divided into two types in storage structure
- Sequential queue: uses a set of memory units with consecutive addresses to store the data in the queue in turn. You can define an array of structures of a specified size as a queue.
- Chained queue: save the values of each element in the queue in the form of linked list.
-
Queue structure is a first in first out (FIFO) linear table that allows insertion at one end
-
Common methods of queue
- initQueue
- Initialize the operation and create an empty queue
- destroyQueue
- If the queue exists, destroy it
- clearQueue
- Empty queue
- queueEmpty
- Determine whether the queue is empty
- getHead
- Get queue header element
- enQueue
- If queue exists, insert element into queue
- deQueue
- Delete the queue header element and return the value
- queueLength
- Get the actual number of elements in the queue
- initQueue
-
Sequential queue
-
Java
package com.fc.queue; /** * @ClassName SequentialQueue Sequential queue * @Description Keep the queue head always at the position with index 0 * @Author Fclever * @Date 2021/7/2 15:59 **/ public class SequentialQueue<T> { /** * The default queue length is 10 */ private static final int MAXLEN = 10; /** * Storage data array */ Object[] queueData; /** * Tail index * The queue is empty, pointing to - 1, otherwise it always points to the end of the queue element n */ int tail; public SequentialQueue() { } /** * 1. Initialize queue */ public void initQueue() { // Initialize storage array this.queueData = new Object[MAXLEN]; // Set queue tail this.tail = -1; } /** * 2. Destroy queue */ // public void destroyQueue() { // // } /** * 3. Empty queue */ public void clearQueue() { for (int i = 0; i<=this.tail;i++){ this.queueData[i] = null; } this.tail = -1; } /** * 4. Determine whether the queue is empty * @return */ public boolean queueEmpty() { return this.tail == -1; } /** * 5. Get queue header element * @return */ public T getHead() { return (T) this.queueData[0]; } /** * 6. Join the team * @param data Team element */ public void enQueue(T data) { // Determine whether the queue is full if (this.tail + 1 == this.MAXLEN) { throw new OutOfMemoryError(); } // Insert element this.queueData[++this.tail] = data; } /** * 7. Out of the team * @return Returns the queue header element */ public T deQueue() { if (this.queueEmpty()) { return null; } // Return value T data = (T) this.queueData[0]; // Others move forward System.arraycopy(this.queueData, 1, this.queueData, 0, this.tail); this.queueData[this.tail--] = null; return data; } /** * 8. Get the actual number of elements in the queue * @return */ public int queueLength() { return this.tail+1; } /** * 9. Traversal element */ public void getAll() { for (int i=0;i<=this.tail;i++){ System.out.printf("The first%d The elements are:%s\n",i,this.queueData[i]); } } } -
test
package com.fc.queue; import org.junit.Test; import static org.junit.Assert.*; /** * @ClassName SequentialQueueTest * @Description * @Author Fclever * @Date 2021/7/5 13:20 **/ public class SequentialQueueTest { @Test public void testSequentialQueueTest() { SequentialQueue<String> sequentialQueue = new SequentialQueue<>(); sequentialQueue.initQueue(); sequentialQueue.enQueue("1"); sequentialQueue.enQueue("2"); sequentialQueue.enQueue("3"); sequentialQueue.enQueue("4"); sequentialQueue.enQueue("5"); System.out.println(sequentialQueue.queueLength()); sequentialQueue.deQueue(); sequentialQueue.deQueue(); sequentialQueue.getAll(); } }
-
4.3 cyclic queue
4.3.1 inadequacies of sequential storage
- Suppose a queue has n elements, and the end of the array subscript 0 is the head of the queue. For the queue entry operation, it is to add elements at the end of the queue without moving the elements, and the time complexity is O(1); However, during the out of queue operation, the queue head element (subscript 0) will be removed, the following elements will move forward, and the event complexity is O(n)
- However, this outgoing method will reduce the performance of the outgoing queue. If there is no restriction that the elements of the queue must be stored in the first n units of the array, the outgoing performance can be optimized, that is, the queue head can not be set at the position with subscript 0.
- Two pointers are introduced. The front pointer points to the queue head element, and the rear pointer points to the next position of the queue tail element. In the case of empty queue, both pointers point to the position with subscript 0
4.3.2 false overflow
- A queue that uses an array with a length of 5 to save data. The initial situation is front=rear=0. There are three elements in the queue, front=0, rear=3, another element out of the queue, front=1, rear=3, and two elements in the queue, front=1, rear=5? The maximum subscript of the array is 4, and the rear cannot be 5, which will cause the array out of bounds. However, if you look at the array at this time, there is still a position that is empty and the subscript is 0. This situation can be called false overflow.
4.3.3 definition of circular queue
- To solve the false overflow, you can start from the beginning when the array is full. This sequential storage structure of queue head to tail is called circular queue.
- According to the above false overflow problem, using the circular queue, you can insert the new queue element into the position with subscript 0. At this time, rear=1
4.3.4 conditions for empty and full judgment of circular queue
- When the queue is empty, front=rear. When the queue is full, the condition becomes front=rear according to the above situation. How to distinguish between empty and full?
- Method 1: set the flag variable flag. When front = rear & & Flag = 0, the queue is empty, and when front = rear & & Flag = 1, the queue is full. (custom flag value)
- Method 2: when the queue is empty, front=rear; When the queue is full, the Convention array reserves the position of one element and is not used. There is also a free unit in the array. The following figure shows that the queue is full
- Mode 2 is more commonly used, but needs to be analyzed
- There are many situations where front and rear differ by one position: rear may be greater than front, and rear may also be less than front.
- Assuming that the maximum capacity of the queue is MAXLEN, the condition for the queue to be full is: (rear+1)%MAXLEN==front.
- Here, let's analyze how to calculate the actual number of data in the circular queue
- When rear > front, the queue length is rear front
- When rear < = front, the queue length is rear front + Maxle
- You can also derive the formula for calculating the actual number of data in the queue: (rear front + maxlen)% maxlen
4.3.5 sequential cyclic queue
-
code
package com.fc.queue; /** * @ClassName CircularQueue Circular queue * @Description * @Author Fclever * @Date 2021/7/13 11:29 **/ public class CircularQueue<T> { private final int MAXLEN = 10; Object[] queueData; private int front; private int rear; public CircularQueue() { } /** * 1. Initialize queue */ public void initQueue() { queueData = new Object[this.MAXLEN]; this.front = 0; this.rear = 0; } /** * 2. Empty queue */ public void clearQueue() { while (this.front != this.rear) { this.queueData[this.front] = null; // The queue head pointer moves back this.front = (this.front + 1) % this.MAXLEN; } // Reset pointing this.front = this.rear = 0; } /** * 3. Determine whether the queue is empty * @return true Null, false, not null */ public boolean queueEmpty() { return this.front == this.rear; } /** * 4. Get queue header element * @return Team head element */ public T getHead() { return (T) this.queueData[this.front]; } /** * 5. Join the team * @param data Elements to be joined */ public void enQueue(T data) { // Judge whether the stack is full (rear+1)%maxlen == front if ((this.rear + 1)%this.MAXLEN == this.front) { throw new OutOfMemoryError(); } this.queueData[this.rear] = data; // rear shift back this.rear = (this.rear + 1) % this.MAXLEN; } /** * 6. Out of the team * @return Return out of queue element */ public T deQueue(){ if (this.queueEmpty()) { return null; } T data = (T) this.queueData[this.front]; // The original team head element is empty this.queueData[this.front] = null; // The queue head pointer moves back this.front = (this.front + 1) % this.MAXLEN; // Return out of queue element return data; } /** * 7. Get the actual number of data stored in the queue * @return */ public int queueLength() { return (this.rear - this.front + this.MAXLEN) % this.MAXLEN; } /** * 8. ergodic */ public void getAll() { int index = this.front; while (index != this.rear) { System.out.println(this.queueData[index]); // The queue head pointer moves back index = (index+ 1) % this.MAXLEN; } } } -
test
package com.fc.queue; import org.junit.Test; import static org.junit.Assert.*; /** * @ClassName CircularQueueTest * @Description * @Author Fclever * @Date 2021/7/13 15:35 **/ public class CircularQueueTest { @Test public void test() { // Create circular queue CircularQueue<String> circularQueue = new CircularQueue<>(); // initialization circularQueue.initQueue(); // Join the team circularQueue.enQueue("1"); circularQueue.enQueue("2"); circularQueue.enQueue("3"); circularQueue.enQueue("4"); circularQueue.enQueue("5"); circularQueue.deQueue(); circularQueue.deQueue(); circularQueue.enQueue("88"); System.out.println(circularQueue.queueEmpty()); String head = circularQueue.getHead(); System.out.println(head); System.out.println(circularQueue.queueLength()); circularQueue.getAll(); circularQueue.clearQueue(); } } -
Circular queues have better time performance than ordinary sequential queues, but they face the problem of array overflow (because the array length is fixed)
4.3.6 chain loop queue
-
The chain storage mode of queue adopts single chain list, tail in and head out, which is called chain queue for short. Set the queue head pointer to the head node and the queue tail pointer to the terminal node.
-
Java code
package com.fc.queue; /** * @ClassName ChainQueue Chain queue * @Description * @Author Fclever * @Date 2021/7/13 16:42 **/ public class ChainQueue<T> { // Queue head pointer private Node<T> front; // Tail pointer private Node<T> rear; // Actual number of elements private int length; public ChainQueue() { } /** * 1. initialization */ public void initQueue() { // The head and tail of the team point to the same direction this.front = this.rear = new Node<>(); this.length = 0; } /** * 2. Empty queue */ // public void clearQueue() { // Node<T> p = this.front; // Node<T> q = this.front.next; // while (q != null) { // p = q; // q = q.next; // p = null; // } // q = null; // } /** * 3. Determine whether the queue is empty * @return Empty flag */ public boolean queueEmpty() { return this.front == this.rear; } /** * 4. Get queue header element * @return Team leader */ public Node<T> getHead(){ return this.front.next; } /** * 5. Join the team * @param data */ public void enQueue(T data) { // Build node Node<T> node = new Node<>(data, null); /** * When the queue is empty, front=rear points to the head node, and only needs to be changed * rear You can point to the next of, and the front changes accordingly */ // Insert directly at the end of the team this.rear.next = node; this.rear = node; this.length++; } /** * 6. Out of the team * @return */ public Node<T> deQueue(){ // If the queue is empty, return directly if (this.queueEmpty()){ return null; } // Team head element Node<T> node = this.front.next; // Determine whether the team head element is the team tail** if (this.rear == node) { // Point the end of the queue to the head node this.rear = this.front; } this.front.next = node.next; this.length--; return node; } /** * 7. Gets the actual length of the queue * @return */ public int queueLength() { return this.length; } /** * 8. ergodic */ public void getAll() { if (!this.queueEmpty()) { Node<T> p = this.front.next; while (p != null) { System.out.println(p.data); p = p.next; } } } } -
test
package com.fc.queue; import org.junit.Test; import javax.print.DocFlavor; import static org.junit.Assert.*; /** * @ClassName ChainQueueTest * @Description * @Author Fclever * @Date 2021/7/14 10:03 **/ public class ChainQueueTest { @Test public void test() { // establish ChainQueue<String> chainQueue = new ChainQueue<>(); // initialization chainQueue.initQueue(); // Join the team chainQueue.enQueue("1"); chainQueue.enQueue("2"); chainQueue.enQueue("3"); chainQueue.enQueue("4"); chainQueue.enQueue("5"); // System.out.println(chainQueue.getHead().data); System.out.println(chainQueue.queueLength()); chainQueue.deQueue(); chainQueue.deQueue(); chainQueue.deQueue(); System.out.println(chainQueue.queueEmpty()); chainQueue.getAll(); } }
4.3.7 sequential queue and chain queue
- In terms of time, the basic operations are O(1). The circular queue is to apply for a good space and will not be released during use; Chain queue, which applies for and releases nodes every time it is needed.
- In terms of space, the length of circular queue is fixed, which has the problems of the number of storage elements and space waste; The chain queue does not have this problem. Although the pointer field is required, it will incur a certain space overhead.
- The queue length is fixed, and the sequential cyclic queue is used; The queue length cannot be estimated. Use chain queue.
.enQueue("5");
//
System.out.println(chainQueue.getHead().data);
System.out.println(chainQueue.queueLength());
chainQueue.deQueue();
chainQueue.deQueue();
chainQueue.deQueue();
System.out.println(chainQueue.queueEmpty());
chainQueue.getAll();
}
}
###### 4.3.7 sequential queue and chain queue - In terms of time, the basic operations are O(1)，Circular queue is used to apply for a good space, which is not released during use; Chain queue, which applies for and releases nodes every time it is needed. - In terms of space, the length of circular queue is fixed, which has the problems of the number of storage elements and space waste; The chain queue does not have this problem. Although the pointer field is required, it will incur a certain space overhead. - <font color=red>The queue length is fixed, and the sequential cyclic queue is used; The queue length cannot be estimated. Use chain queue.</font>