C++: Queue Data Structure

A queue exhibits a FIFO (First In, First Out) behavior. Queues are used in many areas of software development, from operating systems, video games, web-sites to computer simulations and more.

A stack has the opposite behavior (LIFO) and is used in combination with queues to solve problems.

A queue written in C++ using templates.

#include <iostream>
#include <string>
using namespace std;

template <class TData> class Node
{
private:
	Node() {}
public:
	TData data;
	Node<TData> *pnext;
	Node(const TData &dataToQueue);
};

template <class TData> class Queue
{
private:
	Node<TData> *phead, **pplast;

public:
	Queue();
	Queue(const Queue<TData> &obj);
	~Queue();
	const Queue<TData> &operator=(const Queue<TData> &obj);
	bool IsEmpty() const;
	void Add(const TData &data);
	bool Pop(TData &output);
	void Clear();
};

template <class TData> Node<TData>::Node(const TData &dataToQueue)
{
	pnext = nullptr;
	data = dataToQueue;
}

template <class TData> Queue<TData>::Queue(const Queue<TData> &obj)
{
	phead = nullptr;
	pplast = &phead;
	this->operator=(obj);
}

template <class TData> const Queue<TData> &Queue<TData>::operator=(const Queue<TData> &obj)
{
	if (this != &obj)
	{
		Clear();
		for (Node<TData> *node = obj.phead; node; node = node->pnext)
		{
			(*pplast) = new Node<TData>(node->data);
			pplast = &(*pplast)->pnext;
		}
	}
	return (*this);
}

template <class TData> bool Queue<TData>::IsEmpty() const
{
	return(phead == nullptr);
}

template <class TData> void Queue<TData>::Add(const TData &data)
{
	(*pplast) = new Node<TData>(data);
	pplast = &(*pplast)->pnext;
}

template <class TData> bool Queue<TData>::Pop(TData &output)
{
	if (phead)
	{
		output = phead->data;
		if (pplast == &phead->pnext)
			pplast = &phead;
		Node<TData> *p = phead;
		phead = phead->pnext;
		p->pnext = nullptr;
		delete p;
		return true;
	}
	return false;
}

template <class TData> void Queue<TData>::Clear()
{
	while (phead)
	{
		Node<TData> *p = phead;
		phead = phead->pnext;
		p->pnext = nullptr;
		delete p;
	}
	pplast = &phead;
}

template <class TData> Queue<TData>::Queue()
{
	phead = nullptr;
	pplast = &phead;
}

template <class TData> Queue<TData>::~Queue()
{
	Clear();
}

int main()
{
	{
		Queue<int> q;
		int n;
		for (int i = 0; i < 20; i++)
		{
			n = i;
			cout << n << endl;
			q.Add(n);
		}
		cout << endl;
		do
		{
			int data;
			if (q.Pop(data))
				cout << data << endl;
		} while (!q.IsEmpty());
	}
	cout << endl;
	{
		Queue<string> q;
		string s;
		for (int i = 0; i < 26; i++)
		{
			char c[4] = { 0,0,0,0 };
			c[0] = c[1] = c[2] = ((i % 26) + 97);
			s = c;
			cout << s << endl;
			q.Add(s);
		}
		cout << endl;
		do
		{
			string data;
			if (q.Pop(data))
				cout << data << endl;
		} while (!q.IsEmpty());
	}
	return 0;
}

Comment