The queue
Features: First in, first out
- Save elements: Store them from the last position until they are full (rear)
- Fetch element: Fetch element from the first position (front)
Illustration:
Baidu encyclopedia
The circular queue
Features: The same features as queue first in first out, can be infinite reuse
- Save elements: Store from the last position (rear)
- If it is full, the queue is prompted to be full
- If the memory is not full (the queue element was taken out), the queue is reused
- Fetch element: Fetch element from the first position (front)
Analysis:
To make the queue a ring queue, all you need is one point, and when the queue is full, it goes to the first element of the queue
Note: the first element in the queue does not overwrite the original element
Illustration:
- Red: Indicates that elements are stored
Suppose the queue is now full:
At this point, new elements need to be queued, but the queue is full and cannot be added
When can you add elements using rings?
As emphasized above, the queue is first in, first out, and the data is fetched from the first element
Analysis:
It is also very easy to satisfy the ring queue, and when the element is full, just put the element in position 0
if(index++ == size){
index = 0;
}
Copy the codeBut this method is very stupid, next to introduce you to % operation, understand the friend directly skip!
% operation
The % operation is also the remainder
A direct example should make sense:
public static void initRemainder(a) {
int index = 3;
int size = 10; System.out.println(index % size); } the result is:3
Copy the codepublic static void initRemainder(a) {
int index = 10;
int size = 10; System.out.println(index % size); } the result is:0
Copy the codepublic static void initRemainder(a) {
int index = 14;
int size = 10; System.out.println(index % size); } the result is:4
Copy the codeBaidu encyclopedia
Array simulates ring queue analysis
-
Int front records the starting position of the element
-
Int rear records the last position of the element
-
Int maxSize Total size
-
Int [] array Array of elements
The queue is empty:
Rear == front(first element == last element)
The queue with:
(rear + 1) % mMaxSize == front;
Rear +1 means that the queue always reserves a place to prevent subscripts from crossing the boundary
Add data:
array[rear] = value
Fetching data:
int value = array[front]
Complete code:
public class ArrayQueue {
// Array length
private final int mMaxSize;
// Queue header (the first element of the queue)
private int front;
// End of column (last element of queue)
private int rear;
private final int[] array;
public ArrayQueue(int mMaxSize) {
this.mMaxSize = mMaxSize;
// Initialize the queue length
array = new int[this.mMaxSize];
}
// Whether the queue is full
public boolean isFull(a) {
/* * the queue always reserves a place, so you need rear + 1 */
return (rear + 1) % mMaxSize == front;
}
// Whether the queue is empty
public boolean isEmpty(a) {
/* * When rear = front, the queue has no data */
return rear == front;
}
// Add data
public void addQueue(int n) {
if (isFull()) {
System.out.println("Can't add, queue full");
return;
}
array[rear] = n;
Rear + 1 indicates that a position is reserved by default to prevent subscripts from crossing the boundary
rear = (rear + 1) % mMaxSize;
}
// Retrieve data
public int getQueue(a) {
if (isEmpty()) {
throw new RuntimeException("Can't fetch data, queue empty");
}
// front points to the first element in the queue
// 1. Reserve the value of front to a temporary variable
// 2. Move the front back to take the mold
// 3. Return the temporarily saved variable
int temp = array[front];
front = (front + 1) % mMaxSize;
return temp;
}
// Print all data
public void showQueue(a) {
if (isEmpty()) {
System.out.println("Can't print, queue is empty");
return;
}
for (int i = front; i < front + EffectiveSize(); i++) {
System.out.printf("arr[%d] = %d \n", i % mMaxSize, array[i % mMaxSize]);
}
System.out.println();
}
// Current number of valid data
public int EffectiveSize(a) {
//(Max - Min + Total) % Total = Current valid number
return (rear + mMaxSize - front) % mMaxSize;
}
/ / header element
public int headQueue(a) {
if (isEmpty()) {
throw new RuntimeException("Header element has no data");
}
returnarray[front]; }}Copy the codeUse:
public class Client {
public static void main(String[] args) {
initRemainder();
ArrayQueue arrayQueue = new ArrayQueue(4);
/ / input
Scanner scanner = new Scanner(System.in);
//true loop false not loop
boolean isWhile = true;
while (isWhile) {
showLog();
char key = scanner.next().charAt(0);
switch (key) {
case 'a':
// Add data
System.out.println("Please enter a number :");
int value = scanner.nextInt();
arrayQueue.addQueue(value);
break;
case 'g':
System.out.println("Get data is: + arrayQueue.getQueue());
break;
case 's':
arrayQueue.showQueue();
break;
case 'h':
System.out.println("The first data is :" + arrayQueue.headQueue());
break;
case 'e':
System.out.println("The valid number of queues is :" + arrayQueue.EffectiveSize());
break;
case 'r':
isWhile = false;
System.out.println("Exit successful ~");
break;
default:
throw new IllegalStateException("Unexpected value: "+ key); }}}public static void showLog(a) {
System.out.println("A (add) adds elements");
System.out.println("G (get) gets the element");
System.out.println("H (head) retrieves the queue header element");
System.out.println("S (show) displays queue elements");
System.out.println("E (effectiveSize) Specifies the valid element length of the queue");
}
public static void initRemainder(a) {
int index = 3;
int size = 10; System.out.println(index % size); }}Copy the codeThe complete code
What do you like?
Data structures and algorithms directory
Refer to the video
Blogger page
Original is not easy, your praise is my biggest support ~