Welcome back,
This is our third module of Data Structures and Algorithms. In our previous module we discussed Stack ADT, Array implementation of stack, Linked List implementation of stack, Reversing a string or Linked List using stack, Infix, Postfix, Prefix – Evaluate Postfix expression, Infix to Postfix, Infix to Postfix with Paranthesis.
In this module, we will discuss the following:
3. Queue
3.1 Array implementation of Queue
3.2 Circular Array implementation of Queue
3.3 Linked list implementation of Queue
3. QUEUE ADT:
A list of collection with the restriction that insertion can be performed at one end(REAR/ tail) and deletion can be performed at other end(FRONT / head).
QUEUE OPERATION:
Time complexity: O(1) or Constant time
Enqueue(x) Or Push(x)
- adds element to the tail/ rear
syntax: void Enqueue(int x)
Dequeue( ) Or Pop( )
- removes front element and may return the element
syntax: int Dequeue()
front( ) Or Peek( )
- returns the front element, doesn’t remove it
Isempty( )
- may be boolean
QUEUE APPLICATION:
- Handle request for Shared resouces
- Printer Queue
- Process Scheduling
- Simulating wait
3.1 Array implementation of Queue
Pseudocode for Array implementation of Queue
/* pseudocode- Array implementation of Queue */
int A[10] //create an array
front <- -1 //empty array points NULL
rear <- -1 //empty array
IsEmpty(){
if((front==-1) && (rear==-1))
return true
else return false
}
IsFull(){
if(rear == (sizeof(A)-1))
print "Queue is full"
return
}
Enqueue(x){
if(IsFull())
return
elseif IsEmpty(){
front <- rear <- 0 //points to first element
}
else{
rear <- rear+1
}
A[rear] <- x
}
Dequeue(){
if(IsEmpty())
return
elseif(front == rear){
front <- rear <- -1
}
else{
front <- front+1
}
}
3.2 Circular Array implementation of Queue
Pseudocode for Circular Array implementation of Queue
/*Pseudocode -Circular Array implementation of Queue*/
current position=i
next position = (i+1) % N
prev position = (i+N-1) % N */
int A[5]
//Enqueue ftn
Enqueue(x){
if(rear+1)%N == front //Q is full
return
elseif IsEmpty(){
front <- rear <- 0 //point to first element
}
else{
rear <- (rear+1) % N //point to next position
}
A[rear] <- x
}
//Dequeue ftn
Dequeue(){
if(IsEmpty())
return
elseif(front == rear){ //since only one element
front <- rear <- -1 //make them point NULL
}
else{
front <- (front+1)%N /*from front one element is deleted, so pint to next element*/
}
}
//Front ftn
front(){
return A[front]
}
3.3 Linked list implementation of Queue
Runnable SourceCode_3.3-Linked list implementation of Queue
/*Queue - Linked List implementation*/
#include<iostream>
using namespace std;
struct Node{
int data;
Node* next;
};
Node* frnt=NULL;
Node* rear=NULL;
//Enqueue ftn
void Enqueue(int x){
Node* temp=new Node;
temp->data=x;
temp->next=NULL;
if(frnt==NULL && rear==NULL){ //if empty
frnt=rear=temp; /*making the node as first element*/
}
else{
rear->next=temp; //since in Q, we add in end
rear=temp;
}
}
//Dequeue ftn
void Dequeue(){
Node* temp=frnt; //since in Q, we delete from front
if(frnt==NULL) return; //empty list
if(frnt==rear){ //only one element
frnt=rear=NULL; //make it empty
}
else{
frnt=frnt->next;
delete temp; //important..!!!dealloc temp
}
}
void Print(){
Node* temp=frnt;
while(temp!=NULL){
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<endl;
}
int main()
{
Enqueue(1);
Enqueue(2);
Enqueue(3);
Print(); // 1 2 3
Dequeue();
Print(); //2 3
return 0;
}
We covered Queue ADT, Queue Operations and Applications, Array implementation of Queue, Circular Array implementation of Queue, Linked list implementation of Queue concepts. In our next module we will discuss about Tree ADT.
Please follow the blog to stay updated with the upcoming modules.
love,
<R.S>
For Complete Sourcecode visit my Github repo: Link provided in the final module
RS-codes
RS-codes 
3 thoughts on “Data Structures & Algorithms – Queue”