Queue
Queue data structure behaves similar to group of people standing in a line (queue) buying tickets turn by turn. Queue is also referred as FIFO (First In First Out) data structure. The element which enters the queue is the first one to leave the queue.
We have access to front of the queue with the only operation being allowed as deletion and to the rear of the queue with the only operation being allowed as insertion.
In most of the common implementations of queue we have the following operations:
dequeue() - removes the front element of the queue if it exists --- O(1)
enqueue() - inserts an element to rear of the queue given the stack doesn't overflow --- O(1)
front() - returns the value of element at the front of the queue --- O(1)
size() - returns the number of elements present in the queue --- O(n) ( depends on implementation )
empty() - returns true if the queue is empty else returns false --- O(1)