Data structure learning – queues and circular queues
- What is a Queue?
- Implementation and time complexity analysis of queue based on dynamic array
- Optimization of the queue
- LoopQueue
What is a Queue?
A Queue, like a stack, is a linear data structure with limits. See Stack for data structures. The stack is LIFO(Last In First Out), and the queue is FIFO(First In First Out). In other words, the queue is a data structure that only allows the addition of elements at one end (the end of the queue) and the deletion of elements at the other end (the head of the queue). Therefore, the queue is a first-in, first-out data structure. The queue can be imagined as the queue mechanism of the bank counter. The person in front of the queue can handle the business first, and the person in the last queue can handle the business only after all the people in front of the queue have completed the transaction, as shown in the figure:
Implementation and time complexity analysis of queue based on dynamic array
Queues, like ArrayStack implementations, need to be based on dynamic arrays as the underlying implementation. Dynamic array implementation code, dynamic array implementation principle in design mode, the same as ArrayStack, design is Queue such an interface, and create ArrayQueue such a class implements this interface, Queue interface method and Stack Stack method roughly the same, It’s just that we design the push as enqueue and the pop as dequeue. The interface code is as follows:
public interface Queue<E>{
void enqueue(E e);
E dequeue();
E getFront();
int getSize();
boolean is Empty();
}
Copy the codeThe ArrayQueue code looks like this:
public class ArrayQueue<E> implements Queue<E>{
private Array<E> array;
public ArrayQueue(int capacity){
array = new Array<>(capacity);
}
public ArrayQueue(){
array = new Array<>();
}
@Override
public int getSize() {return array.getSize();
}
@Override
public boolean isEmpty() {return array.isEmpty();
}
public int getCapacity() {return array.getCapacity();
}
@Override
public void enqueue(E e){
array.addLast(e);
}
@Override
public E dequeue() {return array.removeFirst();
}
@Override
public E getFront() {if(array.isEmpty)
throw new IllegalArgumentException("ArrayQueue is Empty");
return array.get(0)
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append("Queue:\n");
sb.append("front:[");
for(int i=0; i<getSize(); i++){ sb.append(array.get(i));if(i! =getSize()-1){ sb.append(",");
}else{
sb.append("]tail"); }}returnsb.toString(); }}Copy the codeTime complexity analysis is as follows:
E getFront();
int getSize();
boolean is Empty();
Copy the codeIn the above method, the time complexity is O(1).
void enqueue(E e);
Copy the codeBecause enqueue is equivalent to adding elements to the end of a dynamic array, although there is an O(n) level algorithm such as resize(), enqueue is still an O(1) level algorithm in amortized time complexity analysis.
E dequeue();
Copy the codeThe dequeue() operation is the equivalent of removeFirst() on a dynamic array. It removes one element from the head of the array, and all elements after array[0] move forward one position, so dequeue is an O(n) algorithm. All operations of ArrayStack are O(1) level algorithms, but the performance of ArrayQueue based on dynamic array is still slightly inadequate in dequeue. LoopQueue optimizes the problem of ArrayQueue unqueuing.
Optimize the ArrayQueue
As we’ve already seen, the fly in the ointment with ArrayQueue is that an operation like DeQueue is an O(n) algorithm. The reason for this problem is that the dynamic array needs to move all the elements after array[0] forward by one unit each time a queue operation is performed, but it is not “economical” to think about this process, because when the number of queue elements reaches 10,000 or more, only one element is removed. We need to change everything completely. And bank counter business for the queue is different, the bank counter number one person to complete, all the people behind only need to step forward a small step, but for the computer, every data adjustment need computer hands-on experience. Is there any way to avoid such large-scale maneuvering? We can use two variables to maintain the head and tail of queues.
Example: enqueue element “D”
Example: to dequeue
public class MyQueue<E> implements Queue<E> {
private int front;
private int tail;
private E[]data;
public MyQueue(int capacity){
data = (E[])new Object[capacity+1];
}
public MyQueue(){
this(10);
}
@Override
public int getSize() {return tail-front;
}
@Override
public boolean isEmpty() {return front==tail;
}
@Override
public E getFront() {return data[front];
}
private void resize(int newCapacity){
E[]newData = (E[])new Object[newCapacity+1];
for(int i=0; i<(tail-front); i++){ newData[i] = data[front+i]; } data = newData; tail = tail - front; front = 0; } @Override public void enqueue(E e){if(tail == data.length-1)
resize((tail-front)*2);
data[tail] = e;
tail++;
}
@Override
public E dequeue(){
E ret = data[front];
// Loitering Object
data[front] = null;
front++;
if(((tail-front)==(data.length-1)/4) && (data.length-1)/2! =0) resize((data.length-1)/2);return ret;
}
@Override
public String toString(){
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(String.format("MyQueue size=%d,capacity=%d\n",tail-front,data.length-1));
stringBuilder.append("front:[");
for(int i=front; i<tail; i++){ stringBuilder.append(data[i]);if((i+1)! =tail){ stringBuilder.append(",");
}
}
stringBuilder.append("]tail");
returnstringBuilder.toString(); }}Copy the codeMyQueue is optimized for ArrayQueue. The original dequeue needs O(n) time complexity. After optimization, dequeue changes from O(n) time complexity to O(1) time complexity. Tail == data.length-1; tail == data.length-1; tail == data.length-1;
if(tail == data.length-1)
resize((tail-front)*2);
Copy the codeIn the example above, if we reisze, we are actually downsizing. Our design seems to have solved the problem, but it is still not flexible. We hope that the resize when joining the team only involves expansion, while the resize when leaving the team only involves reduction. Can we optimize such requirements?
LoopQueue
The idea of a circular queue is much the same as the ArrayQueue optimized MyQueue, but with a more ingenious loop mechanism.
public class LoopQueue<E> implements Queue<E> {
private E[]data;
private int front;
private int tail;
public LoopQueue(int capacity){
data = (E[])new Object[capacity+1];
}
public LoopQueue(){
this(10);
}
@Override
public int getSize() {if(tail<front)
return data.length-(front-tail);
else{
return tail-front;
}
}
public int getCapacity() {return data.length-1;
}
@Override
public boolean isEmpty() {return getSize()==0;
}
private void resize(int newCapacity){
E[]newData = (E[])new Object[newCapacity+1];
for(int i=0; i<getSize(); i++){ newData[i] = data[(i+front)%data.length]; } data = newData; tail = getSize(); front = 0; } @Override public void enqueue(E e){if(front==(tail+1)%data.length)
resize(2*getSize());
data[tail] = e;
tail = (tail+1)%data.length;
}
@Override
public E dequeue(){
E ret = data[front];
// Loitering Object
data[front] = null;
front = (front+1)%data.length;
if(getSize() == getCapacity()/4 && getCapacity()/2! =0){ resize(getCapacity()/2); }return ret;
}
@Override
public E getFront() {if(getSize()==0)
throw new IllegalArgumentException("LoopQueue is empty");
return data[front];
}
@Override
public String toString(){
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(String.format("LoopQueue size:%d,capacity:%d\n",getSize(),getCapacity()));
stringBuilder.append("front:[");
for(int i=front; i! =tail; i=(i+1)%data.length){ stringBuilder.append(data[i]);if((i+1)%data.length! =tail) stringBuilder.append(",");
}
stringBuilder.append("]tail");
returnstringBuilder.toString(); }}Copy the codeNow let’s test ArrayQueue,LoopQueue performance,
import java.util.Random;
public class Main {
private static double testQueue(Queue<Integer>q,int testCount){
long startTime = System.nanoTime();
Random random = new Random();
for(int i=0; i<testCount; i++) q.enqueue(random.nextInt(Integer.MAX_VALUE));for(int i=0; i<testCount; i++) q.dequeue(); long endTime = System.nanoTime();return(endTime - startTime) / 1000000000.0; } public static void main(String[]args){ inttestCount = 100000;
ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
LoopQueue<Integer> loopQueue = new LoopQueue<>();
double loopQueueTime = testQueue(loopQueue,testCount);
double arrayQueueTime = testQueue(arrayQueue,testCount);
System.out.println("LoopQueue:"+loopQueueTime);
System.out.println("ArrayQueue"+arrayQueueTime); }}Copy the codeThe test results in JDK1.8 environment are as follows:
