Hot Topics
Data Structure
Introduction to Queue
Queue is a linear data structure that is open on both ends and follows First In First Out(FIFO) principle i.e the element inserted in queue at first will be the element removed or popped out of queue at first.For example when we stand in a queue to buy tickets in a railway station the first person in queue gets the ticket and goes out of queue.Here also it follows the same principle.
Operations in Queue
To perform any operations on queue we need to take an array and two variable front and rear and initialize it with 0 which tells us the queue is empty.
1. push():To push an element in queue we must check that rear shouldn’t reach to the last position of an array if it does then the queue is full.If the rear didn’t reach the last position of array then we can insert element at arr[rear] and increase rear by 1.
void push(int data)
{
if (rear == size)
cout << endl
<<”Queue is full and
no element can be
inserted”
<< endl;
else
{
arr[rear] = data;
rear++;
}
}
2. pop(): To remove element from queue we must check whether the queue is empty which can be got when both front and rear variables are at same index.If the front and rear variables are not at same index then we can remove element from queue.
void pop()
{
if (qfront == rear)
return -1;
else
{
int ans = arr[qfront];
arr[qfront] = -1;
qfront++;
if (qfront == rear)
front = rear = 0;
return ans;
}
}
3. front(): Get the element at the front of queue.
int front()
{
if (qfront == rear)
return -1;
else
return arr[front];
}
4. display():Print all the elements until both front and rear variables point to same location.
void display()
{
if (qfront == rear)
{
cout <<”Queue is empty” < endl;
return;
}
else
{
for (int i = front; i < rear; i++)
cout << arr[i] <<” “;
return;
}
}
Application of Queue
Use to transfer data sequentially across multiple devices
Applied to add songs or videos at the end and remove from end.
Problems in Linear Queue
The problem with linear queue is that if we leave some cells empty in the queue we can’t fill it back later as a result those places will be unutilised.To deal with this problem we use circular queue which is a normal queue and follows FIFO principle.It just connects the last position of queue to first position of queue so that we can insert new elements at the beginning of queue using circular queue.
Advantages of Queue
Large amount of data can be managed easily and efficiently.
It can be used to implement other data structures
Insertion and deletion in queue can be performed easily
It can be used when a particular service is used by multiple consumers
Disadvantages of Queue
Limited space
To insert and delete something to or from middle takes alot of time
Searching an element in queue takes O(N) time.
Automata Fixing