Queue

Queue is also an abstract data type in which the elements are inserted from one end called REAR/BACK, and the deletion of existing elements takes place from the other end called as FRONT/HEAD. This makes queue as FIFO data structure, which means that element inserted first will also be removed first.

Enqueue():

Adding the element into the back of the queue.

Dequeue():

Removing the element from the front of the queue.

Following image will explain these operations better:

Implementation:

template<class T>

class Queue

{

public:

Queue<T>(){}

void enque(T elem);

void deque();

T front();

bool empty();

~Queue(){}

private:

std::list<T> m_list;

};

template<class T>

void Queue<T>::enque(T elem)

{

m_list.push_back(elem);

}

template<class T>

void Queue<T>::deque()

{

m_list.pop_front();

}

template<class T>

T Queue<T>::front()

{

return m_list.front();

}

template<class T>

bool Queue<T>::empty()

{

return m_list.empty();

}

Complexity: O(1) for all of the above operations.