The Queue is a Data Structure, supports the insertion and deletion of elements in particular order, i.e, FIFO (First In First Out). Whenever an element is inserted it goes to the top of the queue and the element which is inserted at the last (element at the top of the queue) will be removed at first.
Note: Unlike stack in a queue, we maintain two pointers: head and rear.
1. head pointer point to the start of the queue.
2. rear pointer points to the last element of the queue.
Basic Queue Operation:
Enqueue: Enqueue operation inserts an element at the rear of the queue. Every time an element is inserted, the rear pointer is incremented.
Enqueue(var): If(rear == maxsize) print "queue is full" else queue[rear] = var rear++
Dequeue: Dequeue operation deletes an element from the front of the queue. Every time an element is deleted, the front pointer is incremented. If the front becomes equal to the rear, then the queue is empty.
Dequeue(): If(front == rear) print "queue is empty" else var = queue[front] queue[front] = 0 front --; return var;
Time Complexity Of Stack Operation
- Enqueue Operation: O(1)
- Dequeue Operation: O(1)
- Search an Element: O(N)
Implementation of Queue Data Structure in CPP
#include <bits/stdc++.h> using namespace std; int max_size = 7; int front=-1,rear=-1; vector<int> Queue_ds(max_size); int Enqueue(int element){ if(rear+1 == max_size) cout<<"Queue Overflow"<<endl; else{ rear++; Queue_ds[rear] = element; } return 0; } int Dequeue(){ int element; if(front == rear) cout<<"Queue Underflow"<<endl; else{ element = Queue_ds[front]; front++; } return element; } int display_Queue(){ if(front == rear) cout<<"Queue is empty"<<endl; else{ cout<<"Queue content is:"<<endl; for(int i=front+1;i<=rear;i++) cout<<Queue_ds[i]<<" "; cout<<endl; } return 0; } int main(){ Enqueue(1); Enqueue(5); Enqueue(7); Enqueue(9); Enqueue(10); Enqueue(12); display_Queue(); Dequeue(); Dequeue(); display_Queue(); Enqueue(15); display_Queue(); return 0; }
Output
Queue content is: 1 5 7 9 10 12 Queue content is: 7 9 10 12 Queue content is: 7 9 10 12 15
Pls add a list of exactly related easy to medium problems below the tutorial.