Wednesday, May 6, 2015

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.

No comments:

Post a Comment