Overview:
Queue is a data structure where elements is inserted at the front of the list and any element is deleted from the rear of list. So it is called FIFO(First in First out) data structure.
Insert operation on a queue is often called enque and delete operation is often called deque.
If we insert an element to queue the rear is increment. Similarly If we delete an element from queue the front is increment.
The following picture front is an indicator that indicates the front element of the queue and rear is also an indicator that indicates the last element of the queue.
Real life applications of stack:
Queues abound in everyday life. In our daily life, when we stand on line to get into bus , we make queue. The man who stands first will get into bus first and the man who stand last will get into the bus last.
Operation :
The following operation are performed in the stack.
1.Enque : To add an element to queue.
2.Deque : To remove an element from the queue.
3.Peek : To get the topmost element in queue.
Implementation :
Queue can be implemented two ways. using array and using linked list.Here we discuss queue implementation using array . It uses front variable to print the top most element and rear variable to print the bottom most element in the linear array.
- Initially front=rear=0
- In Enqueue operation rear is increased by one and pushed item to queue[rear]
- In Deque operation front is increased by one. i.e queue[front++]
- In Peek operation check that the front is not equal to rear and return queue[front]
Algorithm : Enqueue(que, n, item)
Step 1: Start
Step 2: if(rear==n) print overflow
else que[rear++]=item.
Step 3: End
C++ implementation :
void Enque(int que[],int n, int item)
{
if(rear==n) cout<<"Overflow"<<endl;
else que[rear++] = item;
}
Algorithm : Deque(que)
Step 1: Start
Step 2: if(front==rear) print Underflow;
else que[front++];
Step 3: End
C++ implementation :
void Deque(int que[])
{
if(front==rear) cout<<"UnderFlow"<<endl;
else que[front++] ;
}
Algorithm : Peek(que)
Step 1: Start
Step 2: if(front==rear) print Empty;
else return que[front];
Step 3: End
C++ implementation :
int Peek(int que[])
{
if(front==rear) cout<<"Queue is empty"<<endl;
else return que[front];
}
Spoj Problem: ADAQUEUE
Hackerrank Problem :Queue using Two Stacks