Queue

Queue is a container which follows FIFO order (First In First Out).

Elements are inserted at one end ( Rear ) and extracted from another end( Front )

Operations( Member functions )

Function	What it does ?	Complexity
push( )	Inserts an element in queue at one end(rear).	O(1)
pop( )	Deletes an element from another end if queue(front).	O(1)
front( )	Access the element on the front end of queue.	O(1)
empty( )	Checks if the queue is empty or not.	O(1)
size( )	returns the size of queue.	O(1)

Implementation

#include<iostream>
#include<cstdio>
#include<queue>           

using namespace std;

int main(){
        int  i ;
        queue <int> q ;                 // declaratation
        for ( i = 1 ; i < 4; i++ ){
                q.push(i*i);
        }
        printf("Size of queue %d \n ", q.size());
        while(!q.empty()){
                printf(" %d ",q.front());
                q.pop();
        }
        return 0 ;
}

Output

Size of queue 3
  1  4  9  

Problems

• codechef

Priority-Queue

A priority queue is a container that provides constant time extraction of the largest element .

In a priority queue, an element with high priority is served before an element with low priority.

All insertion / deletion operations takes place in Logarithmic time .

Operations( Member functions )

Function	What it does ?	Complexity
push( )	Inserts a new element in the priority queue.	O(logN)
pop( )	Removes the largest(Top) element from the priority queue .	O(LogN)
top( )	Returns a reference to the largest element in the priority queue.	O(1)
empty( )	Returns true if the priority queue is empty and false if the priority queue has at least one element	O(1)
size( )	Returns the number of element in the priority queue.	O(1)

Implementation

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    priority_queue<int> pq;             // declaratation
    pq.push(10);
    pq.push(20);
    pq.push(5);
    while(!pq.empty())
    {
        cout << pq.top() << endl;
        pq.pop();
    }
    return 0;
}

Output

20
10
5

Problems

• codechef

Note - Follow up deque as above