A queue is an abstract data structure that is open on both ends. One end is used to
insert or enqueue an element while the other end used to remove or dequeue the element.
there are various techniques to implement a Queue such as Linked List based queue or an
array-based queue. Queue is a FIFO – First In Last Out data structure.
We can use a fixed array or dynamic array to implement a Queue. Queue is a famous
Linear Data Structure that is used in variety of applications. It is mainly used
to manage Data Flow and Tasks within an application. It is also used in Event based
simulations such as Bank Queue, Ticket Queue, Landing Queue or any other Queue simulation.
It is also used in Graph based algorithm for local storage and other intermediate processing. While implementing the queue based on an underlying array, we can insert the
the new elements at the end of the array and and pop from the front of the array.
Queue Complexity
- Queue Complexity
- Insertion is O(1) as we are inserting at the end of the Array.
- Deletion is O(1) in the best case (Single element in the queue), otherwise it is O(N) because we have to shift the elements towards the left.
- Peek: O(1)
- Search is O(1) in best case and O(N) in average and worst cases.
- Fixed Memory container due to Array, Can be written with dynamic memory by increasing the size of the array.
Example
Create Queue : Queue is Empty
Enqueue 5:
Queue is: 5
Enqueue 7:
Queue is: 5 7
Enqueue 1:
Queue is: 5 7 1
Dequeue: 5
Queue is: 7 1
Enqueue 8:
Queue is: 7 1 8
Enqueue 3:
Queue is: 7 1 8 3
Dequeue: 7
Queue is: 1 8 3
Dequeue: 1
Queue is: 8 3
Code
Queue.java
/**
* Implementation of Array Based Queue
*
* @author CodingHelpLine
*/
public class Queue {
// Maximum Size of array
private final int MAX_SIZE = 100;
// Array
private int queue [];
// Number of Elements
private int count;
/**
* Constructor to setup the Empty Queue and memory allocation.
*/
public Queue() {
this.queue = new int[MAX_SIZE];
this.count = 0;
}
/**
* Function to add new Element into the Queue and return true if successful.
*
* @param value to add to the queue
* @return indicate success or failure of adding element
*/
public boolean enqueue(int value) {
// full or not
if(this.isFull()) {
return false;
}
this.queue[count++] = value;
return true;
}
/**
* Function to remove an element from the front of the Queue.
*
* @return indicate a successful or failed operation
*/
public boolean dequeue() {
if(this.isEmpty()) {
return false;
}
// Shift all the element 1 position left
for(int i=0; i<count-1; i++) {
this.queue[i] = this.queue[i+1];
}
count--;
return true;
}
/**
* Function to peek front value of this queue.
*
* @return front value.
*/
public int peek() {
return queue[0];
}
/**
* Size of the Queue - number of elements.
*
* @return number of elements
*/
public int size() {
return count;
}
/**
* Check whether this queue is full or not.
*
* @return indicate if the queue is full
*/
public boolean isFull() {
return count == MAX_SIZE;
}
/**
* Check whether this queue is empty or not.
*
* @return indicate queue is empty.
*/
public boolean isEmpty() {
return count == 0;
}
/**
* Print Function to print the Queue.
*/
public void print() {
System.out.print("[");
if(!this.isEmpty()) {
System.out.printf("%d", queue[0]);
}
for(int i=1; i<count; i++) {
System.out.printf(", %d", queue[i]);
}
System.out.println("]");
}
}
ArrayQueueAppTest
import java.util.Random;
/**
* Tester for the Queue Class
* @author CodingHelpLine
*/
public class ArrayQueueAppTest {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// Create Queue Object
Queue queue = new Queue();
// Random Number generator
Random random = new Random();
// Insert few elements and view the state
for(int i = 0; i < 5; i++) {
// generate number
int x = random.nextInt(100);
// display
System.out.printf("Adding %d to the Queue%n", x);
// enqueue
System.out.printf("Element %d added: %s%n", x, queue.enqueue(x));
// Queue State
System.out.printf("Size of Queue: %d%n", queue.size());
// Print Queue
queue.print();
}
// Insert few elements and view the state
for(int i = 0; i < 5; i++) {
int x = queue.peek();
// display
System.out.printf("Front Element %d of the Queue%n", x);
// dequeue
System.out.printf("Element %d removed: %s%n", x, queue.dequeue());
// Queue State
System.out.printf("Size of Queue: %d%n", queue.size());
// Print Queue
queue.print();
}
}
}
Views: 1