queue
A usage scenario of queue
Cases of Bank Queuing:
Queue introduction
- Queue is a sequential list, which can be implemented by array or linked list.
- Follow the principle of first in, first out. That is, the data stored in the queue should be taken out first. After the deposit, it shall be taken out
- Schematic: (use array to simulate queue schematic)
Array emulation queue
Array simulation queue: train of thought diagram
- The queue itself has a sequence table. If the array structure is used to store the data of the queue, the declaration of the queue array is shown in the figure below, where maxSize is the maximum capacity of the queue.
- Because the output and input of the queue are processed from the front and rear ends respectively, two variables front and rear are required to record the subscripts at the front and rear ends of the queue respectively. The front will change with the data output, while the rear will change with the data input, as shown in the figure
New ideas
When we store data in the queue, it is called "addQueue". The processing of addQueue needs two steps: train of thought analysis
- Move the tail pointer backward: rear+1, when front == rear [empty]
- If the tail pointer rear is less than the maximum subscript maxSize-1 of the queue, the data will be stored in the array element referred to by rear, otherwise the data cannot be stored. rear == maxSize - 1 [queue full]
According to the queue idea, array simulation queue is realized
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.Queue
* @className: ArrayQueueDemo
* @author: Cold Huanyuan doorwatcher
* @description: TODO
* @date: 2021/12/16 14:24
* @version: 1.0
*/
public class ArrayQueueDemo {
public static void main(String[] args) {
//Create a queue
ArrayQueue queue = new ArrayQueue(3);
char key = ' '; //Receive user input
Scanner scanner = new Scanner(System.in);//
boolean loop = true;
//Output a menu
while (loop) {
System.out.println("s(show): Show queue");
System.out.println("e(exit): Exit program");
System.out.println("a(add): Add data to queue");
System.out.println("g(get): Fetch data from queue");
System.out.println("h(head): View data of queue header");
key = scanner.next().charAt(0);//Receive a character
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("Output a number");
int value = scanner.nextInt();
queue.addQueue(value);
break;
case 'g': //Fetch data
try {
int res = queue.getQueue();
System.out.printf("The extracted data is%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'h': //View data of queue header
try {
int res = queue.headQueue();
System.out.printf("The data in the queue header is%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e': //sign out
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("Program exit~~");
}
}
/* A queue implemented according to an array*/
class ArrayQueue {
//Maximum queue limit
private int MaxSize;
//Queue tail
private int rear;
//Queue header
private int front;
//Array to hold queue data
private int[] ArrayQueue;
/**
* @author Cold Huanyuan doorwatcher
* @context: Initialize the construction queue, and initialize the queue and the head and tail values
* @date: 2021/12/16 14:30
* @param maxSize
* @return:
*/
public ArrayQueue(int maxSize) {
// Get maximum
this.MaxSize = maxSize;
//Initialize queue
ArrayQueue = new int[MaxSize];
//Set maximum and minimum values
rear = -1;
front = -1;
}
/**
* @author Cold Huanyuan doorwatcher
* @context: Determine whether the queue has reached the upper storage limit
* @date: 2021/12/16 14:30
* @param
* @return: boolean
*/
public boolean isfull() {
return rear == MaxSize - 1;
}
/**
* @author Cold Huanyuan doorwatcher
* @context: Determine whether the queue is empty
* @date: 2021/12/16 14:32
* @param
* @return: boolean
*/
public boolean isemity() {
return rear == front;
}
/**
* @author Cold Huanyuan doorwatcher
* @context: Insert a piece of data into the queue
* @date: 2021/12/16 14:34
* @param value
* @return: void
*/
public void addQueue(int value) {
if (isfull()) {
System.out.println("The queue is full. No more data can be added");
return;
}
//++Is post assignment, which means that after executing the current assignment, rear moves backward by one bit
rear++;
ArrayQueue[rear] = value;
}
/**
* @author Cold Huanyuan doorwatcher
* @context:Gets the value of the queue
* @date: 2021/12/16 14:37
* @param
* @return: void
*/
public int getQueue() {
if (isemity()) {
throw new RuntimeException("The queue is empty and cannot get content");
}
front++;
return ArrayQueue[front];
}
/**
* @author Cold Huanyuan doorwatcher
* @context:Traverse the queue output. Note that traversal does not change the direction of the queue
* @date: 2021/12/16 14:42
* @param
* @return: void
*/
public void showQueue() {
if (isemity()) {
System.out.println("The queue has no value to traverse");
}
for (int i = 0; i < ArrayQueue.length; i++) {
System.out.printf("arrQueue[%d]: %d\n", i, ArrayQueue[i]);
}
}
/**
* @author Cold Huanyuan doorwatcher
* @context:Here, like the previous traversal method, we just show the data, not get out the data
* @date: 2021/12/16 14:45
* @param
* @return: void
*/
public int headQueue() {
if (isemity()) {
throw new RuntimeException("No header data");
}
return ArrayQueue[front + 1];
}
}Problem analysis and optimization
- At present, the array cannot be used once, which does not achieve the effect of reuse
- Use the algorithm to improve this array into a ring queue module
Array simulation ring queue
The previous array simulation queue optimization, make full use of the array So think of the array as a ring. (it can be realized by taking mold)
Analysis description:
- When the next index of the tail index is the header index, it indicates that the queue is full, that is, one queue capacity is vacated as the contract. When judging that the queue is full, you should pay attention to (rear + 1)% maxsize = = front full]
- rear == front [empty]
According to the idea, array simulation ring queue is realized
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.Queue
* @className: CircleArrayQueueDemo
* @author: Cold Huanyuan doorwatcher
* @description: TODO
* @date: 2021/12/16 16:28
* @version: 1.0
*/
public class CircleArrayQueueDemo {
public static void main(String[] args) {
System.out.println("Test ring queue");
//Create a queue where the space is 4 and the maximum effective space is 3. Set aside a space as a convention
CircleArrayQueue queue = new CircleArrayQueue(4);
char key = ' '; //Receive user input
Scanner scanner = new Scanner(System.in);//
boolean loop = true;
//Output a menu
while (loop) {
System.out.println("s(show): Show queue");
System.out.println("e(exit): Exit program");
System.out.println("a(add): Add data to queue");
System.out.println("g(get): Fetch data from queue");
System.out.println("h(head): View data of queue header");
key = scanner.next().charAt(0);//Receive a character
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("Output a number");
int value = scanner.nextInt();
queue.addQueue(value);
break;
case 'g': //Fetch data
try {
int res = queue.getQueue();
System.out.printf("The extracted data is%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'h': //View data of queue header
try {
int res = queue.headQueue();
System.out.printf("The data in the queue header is%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e': //sign out
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("Program exit~~");
}
}
/** Ring queue
* Change of thinking:
* What questions did the previous queue ask
* Problem analysis and optimization
*1) At present, the array cannot be used once, which does not achieve the effect of reuse
*2) Use the algorithm to improve this array into a ring queue module
* The idea is as follows:
* 1.front Adjust the meaning of the variable: front points to the first element of the queue, that is, arr(front] is the first element of the queue
* front Initial value of
* 2.rear Adjust the meaning of the variable: rear points to the next position of the last element of the queue Because I want to make a space as an agreement
* rear Initial value of = 0
* 3.When the queue is full, the condition is (rear+1)%maxSize=front [Full]
* 4.For the condition that the queue is empty, rear==front is empty
* 5.When we analyze this way, the number of valid data in the queue (rear + maxsize front)% maxsize / / rear = 1front = 0
* 6.We can modify the original queue to get a ring queue
*
* */
class CircleArrayQueue {
//Maximum queue limit
private int MaxSize;
//The train of thought at the end of the queue changes. This time, our end of the queue value changes to 0, pointing to the previous bit of the last bit in the queue
private int rear;
//The thought change of the queue head points to the first place of the queue head, that is, the subscript is 0
private int front;
//Array to hold queue data
private int[] ArrayQueue;
/**
* @author Cold Huanyuan doorwatcher
* @context: Initialize the construction queue, and initialize the queue and the head and tail values
* Why not initialize the head and tail of the team here, because the default = 0
* @date: 2021/12/16 14:30
* @param maxSize
* @return:
*/
public CircleArrayQueue(int maxSize) {
// Get maximum
this.MaxSize = maxSize;
//Initialize queue
ArrayQueue = new int[MaxSize];
}
/**
* @author Cold Huanyuan doorwatcher
* @context:
* The idea here changes because we want to make a ring queue. Here, we have a location that changes dynamically, so we need to update the method to calculate whether the queue is full
* @date: 2021/12/16 14:30
* @param
* @return: boolean
*/
public boolean isfull() {
return (rear + 1) % MaxSize == front;
}
/**
* @author Cold Huanyuan doorwatcher
* @context: Determine whether the queue is empty
* @date: 2021/12/16 14:32
* @param
* @return: boolean
*/
public boolean isemity() {
return rear == front;
}
/**
* @author Cold Huanyuan doorwatcher
* @context:
* Adding data, we also need to change. Here we use a ring
* rear The backward shift of is no longer the last bit, and there may be cross-border problems
* (rear+1)%maxSize
* @date: 2021/12/16 14:34
* @param value
* @return: void
*/
public void addQueue(int value) {
if (isfull()) {
System.out.println("The queue is full. No more data can be added");
return;
}
//assignment
ArrayQueue[rear] = value;
//Consider taking a mold to move the rear
rear = (rear + 1) % MaxSize;
}
/**
* @author Cold Huanyuan doorwatcher
* @context:
* Why not use + + because we are a ring, we will cross the boundary. Here, we consider taking the module to dynamically calculate the backward position
* @date: 2021/12/16 14:37
* @param
* @return: void
*/
public int getQueue() {
if (isemity()) {
throw new RuntimeException("The queue is empty and cannot get content");
}
/*
* 1，Our idea this time is that front represents the first subscript of the queue
* 2. Use temporary variables to get the current value
* 3.Move back front return value
* */
int value = ArrayQueue[front];
front = (front + 1) % MaxSize;
return value;
}
/**
* @author Cold Huanyuan doorwatcher
* @context:
* Traverse the ring queue output. Here we no longer traverse the array length
* We need to find the effective quantity
* @date: 2021/12/16 14:42
* @param
* @return: void
*/
public void showQueue() {
if (isemity()) {
System.out.println("The queue has no value to traverse");
}
//Here we should start from the front
for (int i = front; i < front + Size(); i++) {
//Here, we choose that the module should be ring, and there will be out of bounds, so we use the module operation
System.out.printf("arrQueue[%d]: %d\n", i % MaxSize, ArrayQueue[i % MaxSize]);
}
}
/*Write a method to calculate the effective data quantity of the queue*/
public int Size() {
/* Application of mold taking ideas
* 1. rear = 1
* 2. front = 0
* 3. maxSize = 3
* (1+3-0)%3 = 1 It should be calculated as a subscript, so we have two valid data 0 and 1
* */
return (rear + MaxSize - front) % MaxSize;
}
/**
* @author Cold Huanyuan doorwatcher
* @context:Here, like the previous traversal method, we just show the data, not get out the data
* Here is no longer front-1. It should be front. At this time, the default is 0
* @date: 2021/12/16 14:45
* @param
* @return: void
*/
public int headQueue() {
if (isemity()) {
throw new RuntimeException("No header data");
}
return ArrayQueue[front];
}
}Code execution effect
