Imagine waiting in those long ‘queues’ at your favourite eatery. The person at the very beginning of the ‘queue’ gets served first and that person gets out of the queue first right? Well, that’s basically what a Queue data structure is. A printer also works on the same principle: it prints pages on the basis of their order in the queue.
In technical language- A Queue is a data structure used for storing data. It is an ordered list in which insertions take are done at one end (rear) and deletions are done at other end (front). The first element to be inserted isAlso The first person in queue get the first to be deleted. Hence. it follows the FIFO principle (First In First Out) or the LILO principle (Last In Last Out).
Main operations of Queue:
1. void enqueue (insert element at the end of queue)
2. int dequeue (Removes and returns the element at the front of the queue)
Implementations of Queue
1. Simple Array based implementation
2. Linked List Implementation
Note: The following coding exercises have been uploaded in JAVA.
Coding Exercise 1: Array Implementation of Queue
package queue;
import queue.Program001queue_linked_list_implementation.queue;
//Array implementation
public class Program002 {
static class queue {
int front = -1, rear = -1, Max = 5;
int[] data = new int[Max];
public void enqueue(int element) {
if (rear - front < Max - 1) {
if (front == -1) {
front++;
rear++;
data[front] = element;
}
else {
rear++;
data[rear] = element;
}
}
else
System.out.println("Queue is full");
}
public Integer dequeue(){
if(front==-1){
System.out.println("Queue is empty");
return null;
}
int r=data[front];
front++;
if(front>rear){
rear=-1;
front=-1;
}
return r;
}
public void show_queue(){
for(int i=front; i<=rear; i++){
System.out.print(data[i]+ " ");
}
System.out.println();
}
public static void main (String args[])
{
queue obj= new queue();
obj.enqueue(1);
obj.show_queue();
obj.enqueue(2);
obj.enqueue(3);
obj.enqueue(4);
obj.enqueue(5);
obj.enqueue(6);
obj.show_queue();
obj.dequeue();
obj.show_queue();
obj.dequeue();
obj.dequeue();
obj.dequeue();
obj.dequeue();
obj.dequeue();
}
}
}
Coding Exercide 2: Linked List Implementation
package queue;
//Linked List implementation
public class Program001 {
static class Linked_List{
Node head = null;
class Node{
int data;
Node next;
Node (int d)
{
data=d;
next= null;
}
}
public void insert_at_end (int new_data){
Node new_node= new Node(new_data);
if(head==null){
head= new_node;
return;
}
Node n=head;
while(n.next!=null){
n=n.next;
}
n.next=new_node;
}
public Integer remove_from_beginning (){
int r= head.data;
head=head.next;
return r;
}
public void display (){
Node n= head;
while(n!=null){
System.out.print(n.data+ " ");
n = n.next;
}
System.out.println();
}
}
static class queue{
int front=-1, rear=-1, Max=5;
Linked_List q= new Linked_List();
public void enqueue (int new_data){
if((rear-front)<Max-1){
if (front == -1) {
front = 0;
}
rear++;
q.insert_at_end(new_data);
}
else
System.out.println("Queue is full");
}
public Integer dequeue(){
if(front==-1){
System.out.println("Queue is Empty");
return null;
}
int r= q.remove_from_beginning();
front++;
if (front > rear) {
front = -1;
rear = -1;
}
return r;
}
public void show_queue(){
q.display();
}
}
public static void main ( String args[])
{
queue obj= new queue();
obj.enqueue(1);
obj.show_queue();
obj.enqueue(2);
obj.enqueue(3);
obj.enqueue(4);
obj.enqueue(5);
obj.enqueue(6);
obj.show_queue();
obj.dequeue();
obj.show_queue();
obj.dequeue();
obj.dequeue();
obj.dequeue();
obj.dequeue();
obj.dequeue();
}
}