Java queue implementation principle and simple implementation code

Java queue implementation principle

The word "queue" is British for "platoon". In the UK, 'queuing' means to stand in the middle of a row. In computer science, a queue is a data structure, kind of like a stack, except that the first inserted item in the queue is also the first to be removed, and the last inserted item in the stack is the first to be removed. The queue works like a queue in front of a cinema: the first person to enter the annex is the first to arrive at the head of the queue to buy a ticket. The last person in line is the last to get a ticket.

Queues and stacks 1 are also used as tools for programmers. It can also be used to simulate real-world situations, such as people waiting in line at Banks, planes waiting to take off, or packets of data waiting to be sent over the Internet.

In a computer operating system, there are queues working quietly. The print job waits in the print queue for printing. There is also a queue that stores what you type when you type on the keyboard. Similarly, if a word processor is used to hit a key and the computer temporarily has to do something else, the content of the stroke is not lost and it waits in a queue until the word processor has time to read it. Queues ensure that the order of typing does not change during processing.

Basic operations for queues

The two basic operations of the queue are inserting(insert)1 item, that is, put 1 item at the end of the queue, and removing(remove)1 item, that is, remove the item at the head of the queue. It's similar to how movie lovers queue up to get tickets to the back of the line, then arrive at the front and leave.

The methods for inserting and removing data items in a stack are typically named push and pop. There is no standardized naming of the queue's methods. "Insert" can be called put, add, or enque, while "delete" can be called delete, get, or deque. The tail of the inserted data item can also be called back, tail, or end. The header that removes the data item can also be called head. insert, remove, front, and rear are used below.

Insert inserts the value into the end of the queue, while adding 1 to the end arrow to point to the new data item.

After the data item is removed, the header pointer is increased by 1. Usually when implementing a queue, the deleted data item is still stored in memory, but it cannot be accessed because the header pointer has moved to its next location.

Unlike in a stack, data items in a queue do not always start at the 0 index 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 from the queue, but does not delete the data item from the queue.

If you want to remove an item from an empty queue or insert an item into an already full queue, the application prompts for an error message.

Circular queue

When a new data item is inserted into the queue, the Rear arrow of the queue head moves up to the position where the array index is large. When the data item is removed, the Front pointer at the end of the queue also moves up. This design may be the opposite of what people intuitively perceive, because when people are in line to buy a movie ticket, the line always moves forward, and when the person in front leaves the line after buying the ticket, everyone else moves forward. When you delete one item in a queue, you can move all the other items forward, but this is inefficient. Instead, we maintain the position of all data items through the movement of the squadron head and the tail pointer in the queue.

The problem with this design is that the pointer to the end of the array will quickly move to the end of the array. What if there is an empty item unit at the beginning of the array, which is where the removed item is, but since the pointer at the end of the queue cannot be moved any further back, no new items can be inserted?

Surround processing

To avoid the problem of unsatisfied queues not being able to insert new data items, you can have the head and tail of the queue pointer loop back to the beginning of the array. This is known as a circular queue (sometimes called a "buffer ring").

Pointer winding: inserting enough data items into the queue so that the pointer at the end of the queue points to the end of the array. Delete a few more items from the front end of the array. Now insert a new data item. You will see that the tail pointer has never been rewound to its starting position. The new data item will be inserted into this location.

Insert more data items. The tail pointer moved up as expected. Note that after the tail pointer has been rewound, it is now below the head pointer, which reverses the original position. This can be called a "broken sequence" : the items in the queue are stored in two different sequences in the array.

When enough data items are deleted, the header pointer is wound back. At this point, the queue pointer returns to its original running position, with the queue head pointer below the queue tail pointer. The data items are also restored to a continuous sequence of single ones.

The Java code for the queue

The Queue.java program creates an Queue class, which has insert(), remove(), peek(), isEmpty(), and size() methods.

  package stacks and queues;

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 has not only the front(queue head) and rear(queue tail) fields, but also the number of current data items in the queue: nItems.

The Insert() method runs only if the queue is not satisfied. This method is not shown in Main(), but you should usually call isFull() first and return false before calling insert(). (a more common approach is to include a check to see if the queue is full in the insert() method, and throw an exception if an item is inserted into the full queue.)  

In general, the insertion operation is to insert new data at the position indicated by the tail pointer after adding 1 to rear (tail pointer). However, when the rear pointer points to the top of the array, at the maxSize-1 position, it must loop to the bottom of the array before inserting the data item. The wrap operation sets rear to -1, so when rear is added 1, it equals 0, which is the lower label at the bottom of the array, and finally nItem plus 1.

The Remove() method runs on the condition that the queue is not empty, either by calling the isEmpty() method to make sure the queue is not empty, or by adding this error-checking mechanism to the remove() method.

The remove (remove) operation always gets the value of the header data item from the front pointer, and then front plus 1. However, if this causes the value of front to exceed the top of the array, front will have to loop back to the array subscript 0. While doing this check, the return value is stored temporarily. And then finally nItem minus 1.

The Peek() method is straightforward: it returns the value of the data item referred to by the front pointer. Some queue implementations also allow you to view the value of the data item at the end of the queue; For example, these methods can be called peekFront(), peekRear(), or just front() and rear().

The implementation of the isEmpty(), isFull(), and size() methods all depend on the nItems field, which returns whether nItems is equal to 0, maxSize, or its own value, respectively.

Including the data item count field nItems in the Queue class adds 1 extra operation to the insert() and remove() methods, because the insert() and remove() methods must increment and decrement the value of the variable, respectively. This may not be an extra overhead, but if you're dealing with a large number of inserts and removals, it can affect performance.

This is because some queue implementations do not use item count fields, but instead use front and rear to calculate whether the queue is empty or full and the number of items. If you do this, the isEmpty(), ifFull(), and size() routines are quite complex, because, as mentioned earlier, the sequence of data items is either folded into two segments, or one consecutive segment.

And, a strange question arises. When the queue is full, the front and rear Pointers take a definite position of 1, but when the queue is empty, the same positional relationship may be present. So at the same time, the queue seems to be either full or empty. The solution to this problem is to make the array size 1 more than the maximum number of items in the queue.

Thank you for reading, I hope to help you, thank you for your support of this site!