Skip to main content

Queue Data Structure

Queue is an data structure that is follow the properties of First In First Out(FIFO). queue is very similar to stack. there are difference of stack is follow the properties of FILO (First In Last Out). that means stack is remove the element of most recently added. queue are remove element of least recently added. That are perform the insertion and deletion operation of between two different ends

Queue Data Structure

Technically given the name of insertion element of queue is enqueue. and operation of remove element is called dequeue. and inserted position (location to insert new element) is called Tail (Rear). and deleted position is called front.

Real world example of queue

There are many examples for queue data structures. let take few examples of real time situation.

In most of banking system is organized of token system to withdraw the amount of account holder. That process is very helpful for account holder and bank staff. So account holder those are need to withdraw amount by bank that are first get token receipt by token machine. This receipt are have a unique token number. And back stack is work of that token number. So those people are gets first token their work are done by first. And other people is to a waiting for announce your token number. So that process is related to first come first out.

Queue Data Structure Implementation

Create queue data structure using of other data structure. for example array,stack and linked list are can be used to implement queue. in this section given three examples.

Implement of queue using array are suitable when there is predefined how many number of element is stored by the queue. because of array size are never modified during runtime.

C Program for queue implement using array

#include<stdio.h>
#include <stdlib.h>

//function prototype
void enqueue(int);
void dequeue();
int isEmpty();
int isFull();
void setSize(int);

//declare variables
int size,rear=-1,front=-1,*data=NULL;

void setSize(int element){
  size=element;
  data=(int*)malloc(sizeof(int)*element);
  if(data==NULL){
    printf("Memory overflow\n");
  }
}

//insert queue element
void enqueue(int element){
  if(isFull()){
      printf("Queue is overflow\n");
  }else{
    if(front==-1){
      front=0;
    }
    data[++rear]=element;
    printf("Element has been inserted %d \n", element);
  }
}
//remove queue element
void dequeue(){
  if(isEmpty()){
    printf("Empty Queue\n");
  }else{
    printf("Element has been removed %d \n",data[front]);
    front+=1;
  }
}
//check queue is empty or not
int isEmpty(){
    if(front==-1 || front>rear){
      /*Some case front and rear not -1 
        then set it initial value*/
      front=-1;
      rear=-1;
      return 1;
    }else{
      return 0;
    }
}
//check queue is full or not
int isFull(){
  if(rear+1==size){
    return 1;
  }else{
    return 0;
  }
}

int main(){
  setSize(5);//set size of queue
  
  enqueue(1);
  enqueue(2);
  enqueue(3);
  enqueue(4);
  enqueue(5);
  enqueue(6);

  dequeue();
  dequeue();
  dequeue();
  dequeue();
  dequeue();
  dequeue();
}

Output

Element has been inserted 1
Element has been inserted 2
Element has been inserted 3
Element has been inserted 4
Element has been inserted 5
Queue is overflow
Element has been removed 1
Element has been removed 2
Element has been removed 3
Element has been removed 4
Element has been removed 5
Empty Queue

C++ Program for queue implement using array

#include <iostream>
using namespace std;
class MyQueue{
  private:
  //data member
  int size,rear,front,*data;

  public :
  MyQueue(int);
  void enqueue(int);
  void dequeue();
  int isEmpty();
  int isFull();
  
};
//Set inital value of queue
MyQueue::MyQueue(int element){
  size=element;
  rear=-1;
  front=-1;
  data=new int[element];
   if(data==NULL){
    cout<<"Memory overflow"<<endl;
  }
}



//insert queue element
void MyQueue:: enqueue(int element){
  if(this->isFull()){
      cout<<"Queue is overflow"<<endl;
  }else{
    if(front==-1){
      front=0;
    }
    data[++rear]=element;
    cout<<"Element has been inserted "<<element<<endl;
  }
}
//remove queue element
void MyQueue:: dequeue(){
  if(isEmpty()){
    cout<<"Empty Queue"<<endl;
  }else{
    cout<<"Element has been removed "<<data[front]<<endl;
    front+=1;
  }
}
//check queue is empty or not
int MyQueue:: isEmpty(){
    if(front==-1 || front>rear){
      /*Some case front and rear not -1 
        then set it initial value*/
      front=-1;
      rear=-1;
      return 1;
    }else{
      return 0;
    }
}
//check queue is full or not
int MyQueue:: isFull(){
  if(rear+1==size){
    return 1;
  }else{
    return 0;
  }
}

int main(){
  MyQueue info(5);
  info.enqueue(1);
  info.enqueue(2);
  info.enqueue(3);
  info.enqueue(4);
  info.enqueue(5);
  info.enqueue(6);

  info.dequeue();
  info.dequeue();
  info.dequeue();
  info.dequeue();
  info.dequeue();
  info.dequeue();
}
C++ Queue Using Array

Output

Element has been inserted 1
Element has been inserted 2
Element has been inserted 3
Element has been inserted 4
Element has been inserted 5
Queue is overflow
Element has been removed 1
Element has been removed 2
Element has been removed 3
Element has been removed 4
Element has been removed 5
Empty Queue

In this example there are given 4 type of different operation on queue. enqueue() that are inserted element of queue accept one integer value. dequeue() that are remove front element of queue (logically remove). isEmpty() are checked queue is empty or not. and isFull() are checked queue is full or not.

In this c and c++ program there are two limitation. it will work on fixed number of element and rear are equal to size of queue then it will not insert new element. Until there are not deleted other element.

Linked list is avoid this situation, there are no need to initial size of required in linked list. every time are creating dynamic queue node. and also possible to remove that created node.

//implement queue using linked list
#include<stdio.h>
#include <stdlib.h> //for malloc function


//function prototype
void enqueue(int);
void dequeue();
void display();

//create structure
struct Queue{
  int data;
  struct Queue*next;
}*front,*rear;


//insert queue element
void enqueue(int value){
    //Create dynamic node
    struct Queue*node=(struct Queue*)malloc(sizeof(struct Queue));
    if(node==NULL){
      printf("Memory overflow\n");

    }else{

      //assign value to queue node
      node->next=NULL;
      node->data=value;
      if(front==NULL){
          front=node;
      }
      if(rear!=NULL){
        rear->next=node;
      }
      rear=node;
      printf("\nAdded new element is %d\n",value );
      display();//display all element
    }
}
//remove queue element
void dequeue(){
  if(front!=NULL){
    //remove single element
    if(front==rear){
      rear=NULL;
    }

    printf("\nRemoved element is %d\n",front->data);
    struct Queue*temp=front;
    front=front->next;
    free(temp);
    temp=NULL;
    display();//display remaining element

  }else{
    printf("Queue is Empty\n");
  }
}
//display element of queue
void display(){
  struct Queue*auxiliary=front;
  if(auxiliary!=NULL){
    printf("Queue Elements is : ");
  }
  while(auxiliary!=NULL){
    printf("%d  ",auxiliary->data);
    auxiliary=auxiliary->next;
  }
}
int main(){
  enqueue(10);
  enqueue(20);
  enqueue(30);
  enqueue(40);
  enqueue(50);
  dequeue();
  dequeue();  
}

Output

Added new element is 10
Queue Elements is : 10
Added new element is 20
Queue Elements is : 10  20
Added new element is 30
Queue Elements is : 10  20  30
Added new element is 40
Queue Elements is : 10  20  30  40
Added new element is 50
Queue Elements is : 10  20  30  40  50
Removed element is 10
Queue Elements is : 20  30  40  50
Removed element is 20
Queue Elements is : 30  40  50
//implement queue using linked list in c++
#include<iostream>
using namespace std;

//function prototype
void enqueue(int);
void dequeue();
void display();

//create structure
struct Queue{
  int data;
  struct Queue*next;
}*front,*rear;


//insert queue element
void enqueue(int value){
    //Create dynamic node
     Queue*node= new Queue;
    if(node==NULL){
      cout<<"Memory overflow\n";

    }else{

      //assign value to queue node
      node->next=NULL;
      node->data=value;
      if(front==NULL){
          front=node;
      }
      if(rear!=NULL){
        rear->next=node;
      }
      rear=node;
      cout<<"\nAdded new element is "<<value<<endl;
      display();//display all element
    }
}
//remove queue element
void dequeue(){
  if(front!=NULL){
    //remove single element
    if(front==rear){
      rear=NULL;
    }

    cout<<"\nRemoved element is "<<front->data<<endl;
    struct Queue*temp=front;
    front=front->next;
    delete temp;
    temp=NULL;
    display();//display remaining element

  }else{
    cout<<"Queue is Empty\n";
  }
}
//display element of queue
void display(){
  struct Queue*auxiliary=front;
  if(auxiliary!=NULL){
    cout<<"Queue Elements is : ";
  }
  while(auxiliary!=NULL){
    cout<<auxiliary->data<<" ";
    auxiliary=auxiliary->next;
  }
}
int main(){
  enqueue(10);
  enqueue(20);
  enqueue(30);
  enqueue(40);
  enqueue(50);
  dequeue();
  dequeue();  
}
C++ Queue implement using linked list
Output
Added new element is 10
Queue Elements is : 10
Added new element is 20
Queue Elements is : 10 20
Added new element is 30
Queue Elements is : 10 20 30
Added new element is 40
Queue Elements is : 10 20 30 40
Added new element is 50
Queue Elements is : 10 20 30 40 50
Removed element is 10
Queue Elements is : 20 30 40 50
Removed element is 20
Queue Elements is : 30 40 50
//Java implement Queue using Linked list

public class MyQueue{

  static class Node{
    int data;
    Node next;
  }
  static Node front,rear;
  //Class constructors
  MyQueue(){
    front=null;
    rear=null;
  } 
  //insert Queue element
  static void enqueue(int value){
    //Create Queue node
    Node node=new Node();
    node.data=value;
    node.next=null;
    if(rear==null) rear=node;
    if(front==null) front=node;
    else{
      front.next=node;
      front=node;
    } 
    System.out.println("\nEn-Queue Node "+value);
    display();
  }
  //Delete Queue Element
  static void dequeue(){
    if(rear!=null){
      Node temp=rear;
      rear=temp.next;
      System.out.println("\nDe-Queue Node "+temp.data);
      temp=null;
      display();
    }else{
      System.out.println("Empty Queue");
    }
  }
  //display all Queue elements
  static void display(){
    if(rear!=null){
      System.out.print("Queue Element :");
      Node temp=rear;
      while(temp!=null){
        System.out.print("  "+temp.data);
        temp=temp.next;
      }
    }else{
      System.out.println("Empty Queue"); 
    }
  }

  public static void main(String[] args) {
    
    MyQueue obj=new MyQueue();
    obj.enqueue(0);
    obj.enqueue(1);
    obj.enqueue(2);
    obj.enqueue(3);
    obj.enqueue(4);
    obj.enqueue(5);
    
    obj.dequeue();
    obj.dequeue();
    obj.dequeue();
  }
}
java Queue implement using linked list

Output

En-Queue Node 0
Queue Element :  0
En-Queue Node 1
Queue Element :  0  1
En-Queue Node 2
Queue Element :  0  1  2
En-Queue Node 3
Queue Element :  0  1  2  3
En-Queue Node 4
Queue Element :  0  1  2  3  4
En-Queue Node 5
Queue Element :  0  1  2  3  4  5
De-Queue Node 0
Queue Element :  1  2  3  4  5
De-Queue Node 1
Queue Element :  2  3  4  5
De-Queue Node 2
Queue Element :  3  4  5
#Implement queue data Structure using linked list

#create class Element
class Element:
  def __init__(self,data):
    self.data=data
    self.next=None

#create class Queue   
class Queue:
  def __init__(self):
    #Assign default value
    self.front=None
    self.rear=None
  #insert new node to queue 
  def enqueue(self,data):
    node=Element(data)
    if self.front==None:
      self.front=node
    if self.rear==None:
      self.rear=node
    else:
      self.rear.next=node

    self.rear=node
    print("Add Element ",data)
    self.display()  #display queue elements
  def dequeue(self):
    if(self.front!=None):
      auxiliary=self.front
      self.front=self.front.next
      print("Delete Queue Elements : ",auxiliary.data)
      auxiliary=None
      self.display() #display queue elements
    else:
      print("\nEmpty Queue\n")

  def display(self):
      temp=self.front
      print("Queue Elements : "),
      while(temp!=None):
          print(temp.data),
          temp=temp.next
        
      print("\n")
#Create Object of class Queue
queue=Queue()
#Perform queue operation
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
queue.enqueue(40)
queue.enqueue(50)
queue.dequeue();
queue.dequeue();
queue.dequeue();
python Queue implement using linked list

Output

('Add Element ', 10)
Queue Elements :  10

('Add Element ', 20)
Queue Elements :  10 20

('Add Element ', 30)
Queue Elements :  10 20 30

('Add Element ', 40)
Queue Elements :  10 20 30 40

('Add Element ', 50)
Queue Elements :  10 20 30 40 50

('Delete Queue Elements : ', 10)
Queue Elements :  20 30 40 50

('Delete Queue Elements : ', 20)
Queue Elements :  30 40 50

('Delete Queue Elements : ', 30)
Queue Elements :  40 50
//C# Program to implement Queue using linked list
using System;
//Create a Node class
public class Node{
  public Node next;
  public Object data;
}
//Create a Queue class
public class Queue{
  private Node front,rear;
  //Constructor of class Queue
  public Queue(){
    front=null; 
    rear=null;
  }
  //display all Queue elements
  public void display(){
    if(rear!=null){
      Console.WriteLine("Queue Elements");
      Node temp=rear;
      while(temp!=null){
        Console.Write(temp.data+" ");
        temp=temp.next;
      }
    }else{
      Console.WriteLine("Empty Queue");
    }
  }

  //Insert Queue element
  public void enqueue(Object value){
    Node node=new Node();
    node.data=value;
    node.next=null;
    if(rear==null) rear=node;
    if(front==null) front=node;
    else{
      front.next=node;
      front=node;
    }
    

    Console.WriteLine("\nEnqueue Data {0}",value);
    display();
  }
  //Delete Queue elements
  public void dequeue(){
    if(rear!=null){
      Node temp=rear;
      rear=temp.next;
      Console.WriteLine("\nDequeue Data {0}",temp.data);
      temp=null;
      display();
    }else{
      Console.WriteLine("Empty Queue");
    }
  }
}
class Program{
  static void Main(string[] args){
    Queue obj=new Queue();
    //Insert Queue Elements
    obj.enqueue(1);
    obj.enqueue(2);
    obj.enqueue(3);
    obj.enqueue(4);
    obj.enqueue(5);

    //Delete Queue Elements
    obj.dequeue();
    obj.dequeue();
    obj.dequeue();
  }
}

Output

Enqueue Data 1
Queue Elements
1
Enqueue Data 2
Queue Elements
1 2
Enqueue Data 3
Queue Elements
1 2 3
Enqueue Data 4
Queue Elements
1 2 3 4
Enqueue Data 5
Queue Elements
1 2 3 4 5
Dequeue Data 1
Queue Elements
2 3 4 5
Dequeue Data 2
Queue Elements
3 4 5
Dequeue Data 3
Queue Elements
4 5

In this approach there are no need to fixed queue element. inserted and delete node are work efficiently. But note that we create new node of linked list there are need one extra field. This field are used to hold the reference(address) of other linked list note.

Complexity Overview

Complexity is major part of this algorithm. here include operation time complexity and required storage space in given table.

Operation Complexity
Insertion O(1)
Deletion O(1)
Searching O(n)
Space O(n)
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment