formationis a data structure often used in our development, it is similar to thea wooden or bamboo pen for sheep or cattleThe structure of the stack is similar. However, stacks are LIFO, while queues are FIFO, to put it more professionallyFIFO. You can find queues everywhere in life, the most common is queuing, eating queue, on the subway queue, the other will not be too many examples.
Modeling of queues
In data structures, the one most similar to a scenario like queuing is thearraysup, so we'll use arrays to implement our queue. The two basic actions in the queue are thejoin a teamcap (a poem)go out of boundsIn the case of a queue, queue entry is the insertion of an element from the end of the queue, while queue exit is the removal of an element from the head of the queue. The basic model we can draw a sketch of:
Looking at the model above, it's easy to think of using arrays to implement a queue that
- Start by defining an array and determining the length of the array, we tentatively decided that the length of the array is 5, which is the same as in the figure above;
- Define two more array subscripts thatfrontcap (a poem)tailThe front is the subscript of the head of the queue, for each queue operation, we directly take the element under the front subscript. tail is the subscript of the tail of the queue, for each queue operation, we directly insert an element into the position of the tail subscript.
Let's look at the exact process. The initial state is an empty queue.
The head subscript and the tail subscript both point to the 0th element in the array, now we insert the first element "a", as shown in the figure:
The 0th element of the array is assigned the value "a", tail subscript +1, from pointing to the 0th element to point to the first element. These changes we have to remember ah, the subsequent implementation of the process of programming, every detail can not be ignored. Then we do a queue operation:
The 0th element "a" is removed from the array and the front subscript +1 points to the 1st element.
This doesn't seem too hard to accomplish, isn't it just assigning a value to an array element and then adding the subscript +1? But let's think about the extreme case, where we assign a value to the last element of the array, and then what happens to the subscript?
If the tail is +1, it exceeds the length of the array, which is obvious.cross-borderout of bounds. Similarly front will cross the line if it takes the last element in the array and then +1s it. What can be done about this?
recurring array
The first method we thought of is to expand the array when the tail subscript reaches the last element of the array, and the length of the array changes from 5 to 10. Is this method feasible? If we keep queuing, the array will expand indefinitely and fill up disk space, which we don't want to see.
Another way to do this, when front or tail points to the last element of the array and then performs a +1 operation, we point the subscript to the beginning of the queue, which is the 0th element, forming a loop, which is calledrecurring array. So here again the question arises, how do we calculate our subscripts?
- The length of the array is 5;
- The current subscript of tail is 4, the last element of the array;
- How does tail change from the last subscript of the array, 4, to the first subscript of the array, 0, after we assign a value to the last element?
Here we can use thetake a moldto resolve:tail = (tail + 1) % mod, mod (mod) is the length of our array 5, we can try, the current value of the tail is 4, into the formula to calculate the 0, in line with our needs. Let's look at other cases of compliance, assuming that the current value of tail is 1, set into the formula to calculate the 2, is also equivalent to the +1 operation, no problem. Only when the tail +1 = 5, it will become 0, which is consistent with our conditions. Then we realize the queue method on the choice of circular arrays, and arrays of subscripts of the calculation method has also been resolved.
Empty and full queues
Empty and full queue on the queue and out of the operation has an impact, when the queue is full of state, we can not carry out the queue operation, to wait until the queue has a vacant position can be into the queue. Similarly, when the queue is empty, we can not be out of the queue operation, because at this time there is no element in the queue, until there are elements in the queue, can be out of the queue operation. So how do we determine the queue is empty and full?
Let's look at the state of the queue when it is empty and full:
The state when empty is the initial state of the queue, and the values of front and tail are equal.
The state when full is also front == tail, we get the conclusion that when front == tail, the queue is either empty or full, so is it empty or full? Here we have to see what operation is caused by the front == tail, if it is into the queue caused by the front == tail, then it is full; if it is out of the queue caused by the front == tail, then it is empty.
Hand-jerked code
Well, with the model of the queue and the basic problem solved, we can hand-jerk the code, I'll post the code first, and then I'll explain it to you.
public class MyQueue<T> {
//recurring array
private T[] data;
//Array length
private int size;
//outflank and underline
private int front =0;
//go into formation and subscript
private int tail = 0;
//lead tofront==tailunderlying causes，0：go out of bounds；1：join a team
private int flag = 0;
//constructor method，Define the length of the queue
public MyQueue(int size) {
= size;
data = (T[])new Object[size];
}
/**
* Determine if the pair queue is full
* @return
*/
public boolean isFull() {
return front == tail && flag == 1;
}
/**
* Determine if the queue is empty
* @return
*/
public boolean isEmpty() {
return front == tail && flag == 0;
}
/**
* join a team操作
* @param e
* @return
*/
public boolean add(T e) {
if (isFull()) {
throw new RuntimeException("The queue is full.");
}
data[tail] = e;
tail = (tail + 1) % size;
if (tail == front) {
flag = 1;
}
return true;
}
/**
* go out of bounds操作
* @return
*/
public T poll() {
if (isEmpty()) {
throw new RuntimeException("No elements in the queue");
}
T rtnData = data[front];
front = (front + 1) % size;
if (front == tail) {
flag = 0;
}
return rtnData;
}
}
At the beginning of the class, we define, respectively, the circular array, the length of the array, the in-queue subscript, the out-queue subscript, and a very important variableflagIt represents the cause of front == tail, with 0 being out of the queue and 1 being in. Here we initialize to 0 because the queue is empty when it is initialized and front == tail, so that we determine thatisEmpty()The time is also correct.
Next is the constructor method, in which we define the entry parametersize, which is the length of the queue, is actually the length of our circular array and initializes the circular array.
Then the following is to determine the queue empty and full method, the implementation is also very simple, is in accordance with thePrevious subsectionThe principle of the
Then it is into the queue operation, into the queue operation to first determine whether the queue is full, if full, we report errors, do not carry out the operation into the queue. Some students may say, here should wait, wait for the queue has an empty space before going to execute. This statement is very correct, we first write the most basic queue, the back will be perfect, we do not rush. The following is a circular array of tail element is assigned, after the assignment, the use of our formula to move the tail subscript, tail to reach the last element, calculated by the formula, you can go back to the 0th element. Finally, we can determine whether this queuing operation leads to the front == tail, if it leads to the flag set to 1.
The out-of-queue operation is similar to the in-queue operation, except that it is the step of taking the value, which will not be explained to you in detail here.
Let's do a simple test.
public static void main(String[] args) {
MyQueue<String> myQueue = new MyQueue<>(5);
("isFull:"+()+" isEmpty:"+());
("a");
("isFull:"+()+" isEmpty:"+());
("b");
("c");
("d");
("e");
("isFull:"+()+" isEmpty:"+());
("f");
}
We define a queue of length 5 and add each of thea b c d e f6 elements and look at the empty and full states.
Print the log as follows:
isFull:false isEmpty:true
isFull:false isEmpty:false
isFull:true isEmpty:false
Exception in thread "main" : The queue is full.
at (:29)
at (:82)
Empty and full states are correct, and when inserting the f element again, the error "queue is full" is reported, which is not a problem. Out of the queue of the test here will not do, left to the partners to do it.
Concurrency and Waiting
The basic code for the queue has been implemented, let's see if there are any other problems. By the way, the first problem is theerupt simultaneouslyIf we have multiple threads in or out of the queue at the same time, it will cause problems, so what to do? Well, it's pretty simple.synchronizedThe keyword will work as follows:
/**
* Join the team operation
* @param e
* @return
*/
public synchronized boolean add(T e) {
if (isFull()) {
throw new RuntimeException("The queue is full.");
}
data[tail] = e;
tail = (tail + 1) % size;
if (tail == front) {
flag = 1;
}
return true;
}
/**
* out-of-queue operation
* @return
*/
public synchronized T poll() {
if (isEmpty()) {
throw new RuntimeException("No elements in the queue");
}
T rtnData = data[front];
front = (front + 1) % size;
if (front == tail) {
flag = 0;
}
return rtnData;
}
So that there will be no concurrency in the queue out of the operation. Here we go to solve the problem raised by the above partner, is to enter the queue, the queue is full to wait, out of the queue, the queue is empty to wait, this is how to solve it? Here to use thewait()cap (a poem)notifyAll()up, let's clear our minds before we code again.
- The current length of the queue is 5 and it is full;
- Now you want to insert the 6th element into the queue, and when you do so, determine that the queue is full, and wait for the
wait(); - At this point there is an out of queue operation, the queue has empty space, at this point you should wake up the previously waiting thread and insert the element;
On the contrary, when out of the queue, the queue is empty, also wait, when the queue has an element, wake up the waiting thread, and perform the out of the queue operation. Well, jacking the code.
/**
* Join the team operation
* @param e
* @return
*/
public synchronized boolean add(T e) throws InterruptedException {
if (isFull()) {
wait();
}
data[tail] = e;
tail = (tail + 1) % size;
if (tail == front) {
flag = 1;
}
notifyAll();
return true;
}
/**
* out-of-queue operation
* @return
*/
public synchronized T poll() throws InterruptedException {
if (isEmpty()) {
wait();
}
T rtnData = data[front];
front = (front + 1) % size;
if (front == tail) {
flag = 0;
}
notifyAll();
return rtnData;
}
Where we previously threw exceptions, we've unified them into thewait()and the method is executed until the end of thenotifyAll()that evokes the waiting thread. Let's perform a simple test that
public static void main(String[] args) throws InterruptedException {
MyQueue<String> myQueue = new MyQueue<>(5);
new Thread(() -> {
try {
(());
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}).start();
("a");
}
The test result is no problem, you can print "a" normally. Here only out of the queue waiting test, into the queue of the test, partners to complete their own it.
if or while
Here, we hand-jerked the message queue is not bad, the basic functions are implemented, but there is no problem? Let's look at the following test program.
public static void main(String[] args) throws InterruptedException {
MyQueue<String> myQueue = new MyQueue<>(5);
new Thread(() -> {
try {
(());
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}).start();
new Thread(() -> {
try {
(());
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}).start();
(5000);
("a");
}
We start two consumer threads, at the same time from the queue to get data, at this time, the queue is empty, both threads are waiting, after 5 seconds, we insert the element "a", to see how the results.
a
null
As a result, both consumers print out logs, one gets null and the other gets "a", what is the reason for this? Remember how we determine empty and full? That's right, using theif, let's run through the overall process.
- Two consumer threads simultaneously fetch data from the queue, which is empty, and both consumers pass the
ifJudgment, go to wait; - After 5 seconds, insert the element "a" into the queue and wake up all waiting threads;
- The two consumer threads are raised in turn, one fetches the value and one does not. The one that didn't get it was caused by the thread that did get it adding 1 to front. Why do we say that the waiting threads are evoked sequentially? Because
notifyAll()Not all waiting threads are evoked at the same time, they are evoked sequentially and in an indeterminate order.
The desired result is that one consuming thread gets the element "a" and the other consuming thread continues to wait. How do we accomplish this? That's right, it's a combination of the judgment used inifchange intowhile, as follows:
/**
* Join the team operation
* @param e
* @return
*/
public synchronized boolean add(T e) throws InterruptedException {
while (isFull()) {
wait();
}
data[tail] = e;
tail = (tail + 1) % size;
if (tail == front) {
flag = 1;
}
notifyAll();
return true;
}
/**
* out-of-queue operation
* @return
*/
public synchronized T poll() throws InterruptedException {
while (isEmpty()) {
wait();
}
T rtnData = data[front];
front = (front + 1) % size;
if (front == tail) {
flag = 0;
}
notifyAll();
return rtnData;
}
When determining whether it is empty or full, we use thewhileTo judge, when the two consumer threads are evoked in turn, will also be empty and full of judgment, then, the first consumer thread judgment queue has elements, will be acquired, the second consumer thread is evoked, judgment queue has no elements, will again enter the waiting. Let's write some code to test this.
public static void main(String[] args) throws InterruptedException {
MyQueue<String> myQueue = new MyQueue<>(5);
new Thread(() -> {
try {
(());
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}).start();
new Thread(() -> {
try {
(());
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}).start();
(5000);
("a");
(5000);
("b");
}
Again, there are two consumer threads that go to the queue to get the data, at this point the queue is empty, and then, every 5 seconds, we insert an element, and see how that turns out, the
a
b
After 10 seconds have passed, the two inserted elements print normally, indicating that there is no problem with our queue. The test of entering the queue, you can carry out by yourself.
summarize
Okay, we're done with the hand-jobbed message queue, so let's see what the focus is on the
- Loop arrays;
- Array subscripts are computed by taking a modulus;
- Determination of whether the queue is empty or full, note the flags;
- Concurrency;
- Note the use of the evoke thread
while；