Java queue implementation principle
The word "queue" is what the British call "queue". "Ceiling in line" in the UK means standing in a row. In computer science, a queue is a data structure, which is a bit like a stack, except that the first data item inserted in the queue will be removed first, and in the stack, the last data item inserted is removed first. The queue works like the rows of people standing in front of the cinema: the first person entering the affiliated will arrive at the head of the team to buy tickets. The last person who queues up can buy tickets.
Queues are also used as tools for programmers, like stacks. It can also be used to simulate real-world environments, such as simulating people waiting in a bank, planes waiting to take off, or packets on the Internet are waiting to be transmitted.
In the computer operating system, various queues are working quietly. The print job is waiting for printing in the print queue. When typing on the keyboard, there is also a queue that stores the typing. Similarly, if a key is tapped using a word processor and the computer has to do something else temporarily, the tapped content will not be lost, and it will wait in the queue until the word processor has time to read it. The queue is used to ensure that the order of typing is not changed when processed.
Basic operations of queues
The two basic operations of a queue are inserting (inserting) a data item, that is, putting one data item into the tail of the queue, and the other is removing (removing) a data item, that is, removing the data item at the head of the team. This is similar to movie lovers queuing to the end of the line when they queue up to buy tickets, then arrive at the head of the line and then leave the queue.
The naming of methods for inserting and removing data items in the stack is very standard, called push and pop. The queue method has not been named standardized so far. "Insert" can be called put, add, or enque, while "delete" can be called delete, get, or deque. The end of the insertion data item can also be called back, tail or end. The head of the team that removes the data item can also be called head. Insert, remove, front and rear will be used below.
Insert insert the value into the tail of the queue, and the tail of the queue arrow is added to point to the new data item.
After the data item is removed, the head of the team is added by one. Usually when implementing a queue, the deleted data item will be saved in memory, but it cannot be accessed because the head of the queue has been moved to its next position.
Unlike the case in the stack, data items in the queue do not always start at the 0 subscript of the array. After removing some data items, the header pointer points to a higher subscript position.
The view operation returns the value of the header data item, but does not delete the data item from the team.
If you want to remove a data item from an empty queue or insert a data item into a full queue, the application will prompt an error message.
Loop queue
When a new data item is inserted into the queue, the Rear arrow at the head of the team moves upwards toward the large position of the array subscript. When removing data items, the tail of the queue Front pointer also moves upward. This design may be contrary to people's direct observation, because when people queue up for movie tickets, the queue always moves forward, and after the person in front of them buys the ticket and leaves the queue, the others move forward. After deleting a data item in the queue in the computer, you can also move all other data items forward, but this is very efficient. Instead, we keep all data items in the position of the same through the movement of the head and tail pointers of the queue.
The problem with this design is that the tail pointer will quickly move to the end of the array. Although there is an empty data item unit at the beginning of the array, which is the location of the removed data item, but since the tail pointer can no longer move backwards, new data items cannot be inserted. What should I do?
Wrap-up treatment
In order to avoid the problem of the queue being dissatisfied but not being able to insert new data items, the head and tail pointers can be wrapped back to the beginning of the array. This is the loop queue (sometimes also called a "buffer ring").
The process of pointer wrapping: Insert enough data items into the queue to make the tail pointer point to the late end of the array. Delete a few more data items on the front end of the array. Now insert a new data item. You will see that the tail pointer will be reversed from the end to the starting position. New data items will be inserted into this location.
Insert more data items. The tail pointer moves upward as expected. Note that after the tail pointer is rewinding, it is now below the head pointer, which reverses the initial position. This can be called a "broken sequence": the data items in the queue are present in two different sequences in the array.
After deleting enough data items, the head of the team also wraps around. At this time, the queue pointer returns to the position state at the initial runtime, and the head pointer is below the tail pointer. The data items are also restored to a single continuous sequence.
Java code for queues
The Queue.java program creates a Queue class, which has insert(), remove(), peek(), isEmpty() and size() methods.
package stack and queue;
class Queue{ private int maxSize; private long[] queArray; private int front; private int rear; private int nItems; public Queue(int s){ maxSize=s; queArray=new long[maxSize]; front=0; rear=-1; nItems=0; } public void insert(long j){ if(rear==maxSize-1) rear=-1; queArray[++rear]=j; nItems++; } public long remove(){ long temp=queArray[front++]; if(front==maxSize) front=0; nItems--; return temp; } public long peekFront(){ return queArray[front]; } public boolean isEmpty(){ return (nItems==0); } public boolean ifFull(){ return (nItems==maxSize); } public int size(){ return nItems; } }The Queue class implemented by the program not only has front (head) and rear (head of the team) fields, but also the number of current data items in the queue: nItems.
The prerequisite for the operation of the Insert() method is that the queue is unsatisfied. This method is not displayed in Main(), but the insert() method should usually be called first and then the isFull() method should be called after returning false. (A more general approach is to add a judgment to the insert() method to check whether the queue is full. If a data item is inserted into the full queue, an exception will be thrown.)
Generally speaking, the insertion operation is to add a rear (team tail pointer) and insert new data at the position pointed by the tail pointer. However, when the rear pointer points to the top of the array, i.e., the maxSize-1 position, it must be wound back to the bottom of the array before inserting the data item. The winding operation sets the rear to -1, so when the rear is added 1, it is equal to 0, which is the subscript value at the bottom of the array, and finally nItem is added one.
The prerequisite for the operation of the Remove() method is that the queue is not empty. Before calling this method, you should call the isEmpty() method to ensure that the queue is not empty, or add this error checking mechanism to the remove() method.
The remove operation always gets the value of the header data item from the front pointer, and then adds the front one. However, if you do so that the value of front exceeds the top of the array, front must go back to the position where the subscript of the array is 0. While doing this test, the return value is temporarily stored. Finally nItem is reduced by one.
The Peek() method is simple and easy to understand: it returns the value of the data item pointed by the front pointer. Some queue implementations also allow viewing the value of the queue-end data item; for example, these methods can be called peekFront(), peekRear(), or just front() and rear().
The implementation of isEmpty(), isFull() and size() methods all rely on the nItems field, which returns whether nItems is equal to 0, whether it is equal to maxSize, or return its own value.
Including data item counting fields nItems in the Queue class will add a little extra operation to the insert() and remove() methods, because the insert() and remove() methods must increment and decrement the value of this variable respectively. This may not be an extra overhead, but if you deal with a lot of insert and remove operations, this can affect performance.
Because, some queue implementations do not use the fields of data item counting, but use front and rear to calculate whether the queue is empty or full and the number of data items. If you do this, the isEmpty(), ifFull(), and size() routines will be quite complicated because as mentioned earlier, the sequence of data items is either collapsed into two segments, or a continuous segment.
And, a strange problem arose. When the queue is full, the front and rear pointers take a certain position, but when the queue is empty, the same position relationship may also appear. So at the same time, the queue may seem to be full or empty. The solution to this problem is: make the array capacity be one more than the maximum number of queue data items.
Thank you for reading, I hope it can help you. Thank you for your support for this site!