//
//	p.302
//
#include <iostream>
using namespace std;

struct NodeType
{	
	int info;
	NodeType* next;
};

class QueType
{
	NodeType* front;
	NodeType* rear;
public:
	QueType()	// p.303
	{	front = NULL;
		rear = NULL;
	}
	void MakeEmpty()
	{
		NodeType* temp = front;

		while(temp!=NULL)
		{
			front = front->next;
			delete temp;
			temp = front;
		}
		rear = NULL;
	}
	~QueType()
	{
		MakeEmpty();
	}
	void Enqueue(int newItem)	// p.304
	{
		NodeType* newNode = new NodeType;
		newNode->info = newItem;
		newNode->next = NULL;

		if( rear == NULL )	// empty
			front = newNode;
		else	// at least one node
			rear->next = newNode;
		rear = newNode;
	}
	void Dequeue(int& item)
	{	NodeType* temp = front;
		item = temp->info;
		front = front->next;
		if( front==NULL ) rear = NULL;
		delete temp;
	}
	void Print() const
	{
		NodeType* temp = front;
		while(temp != NULL)
		{
			cout << temp->info << " ";
			temp = temp->next;
		}
		cout << "\n";

	}
};

int main()
{
	QueType q;
	int item;

	cout << "Input the item to enqueue: ";
	cin >> item;

	while(cin)
	{
		q.Enqueue(item);

		cout << "Input the item to enqueue: ";
		cin >> item;
	}
	cout << "\n\nThe queue is: ";
	q.Print();
	q.Dequeue( item );
	cout << "\n" << item << " was dequeued.\n";
	cout << "\nThe new queue is: ";
	q.Print();

	cout << "\n\nDone.\n\n";
	return 0;
}