Implementing a Queue Using a Linked List in C++

client.cpp

#include <iostream>
#include <string>

#include "queue.h"

int main()
{
	Queue<std::string> orders;
	orders.enqueue("burger");
	orders.enqueue("fries");
	orders.enqueue("shake");

	while (!orders.is_empty())
	{
		std::cout << "Order up: " << orders.dequeue() << std::endl;
	}
}

queue.h

#pragma once

/**
 * A queue is a generic container that supports adding
 * and removing items. The queue operates on a
 * first-in, first-out policy.
 * Implemented as a singly linked list.
 */
template<typename T>
class Queue
{
	struct Node
	{
		T item_;
		Node* next_;

		Node(T item)
			: item_(item)
			, next_(nullptr)
		{
			
		}
	};

	class Iterator
	{
		Node* current_;
		
	public:

		Iterator()
			: current_(nullptr)
		{
			
		}
		
		Iterator(Node* first)
			: current_(first)
		{
			
		}

		void operator++()
		{
			current_ = current_->next_;
		}

		bool operator!=(const Iterator& Other)
		{
			return current_ != Other.current_;
		}

		T& operator*()
		{
			return current_->item_;
		}
	};
	
	Node* head_;
	Node* tail_;
	int n_;

public:

	Queue()
		: head_(nullptr)
		, tail_(nullptr)
		, n_(0)
	{
		
	}

	~Queue()
	{
		for (Node* current = head_; current != nullptr;)
		{
			Node* temp = current;
			current = current->next_;
			delete temp;
		}
	}

	void enqueue(T item)
	{
		Node* old_tail = tail_;
		tail_ = new Node(item);

		if (old_tail)
		{
			old_tail->next_ = tail_;
		}

		else
		{
			head_ = tail_;
		}
		
		++n_;
	}

	T dequeue()
	{
		T item = head_->item_;
		Node* old_head = head_;
		head_ = head_->next_;
		delete old_head;
		
		if (head_ == nullptr)
		{
			tail_ = head_;
		}
		
		--n_;
		return item;
	}

	bool is_empty() const
	{
		return head_ == nullptr;
	}

	int size() const
	{
		return n_;
	}

	Iterator begin()
	{
		return Iterator(head_);
	}

	Iterator end()
	{
		return Iterator();
	}
};