/*
 * lqueue.cpp
 *
 *  Created on: 07.11.2012
 *      Author: trifon
 */

#include "queue.h"

template <typename T=int>
class LQueue : public Queue<T>
{
public:
	template <typename U = int>
	struct elem {
		U inf;
		elem<U>* link;
	};
private:
	elem<T> *front, *back;

	// O(n)
	void copy(LQueue const& queue)
	{
		elem<T>* p = queue.front;
		front = back = NULL;
		while(p)
		{
			push(p->inf);
			p = p->link;
		}
	}

	// O(n)
	void erase()
	{
		T x;
		while(pop(x));
	}

public:

	LQueue() : front(NULL), back(NULL) {}

	// O(n)
	LQueue(LQueue const& queue)
	{
		copy(queue);
	}

	// O(n)
	LQueue& operator=(LQueue const& queue)
	{
		if (this != &queue)
		{
			erase();
			copy(queue);
		}
		return *this;
	}

	// O(n)
	~LQueue()
	{
		erase();
	}

	bool empty() const {
		return front == NULL;
	}

	bool push(T const& x) {
		elem<T>* p = new elem<T>;
		if (!p)
			return false;
		if (back)
			back->link = p;
		else
			front = p;
		p->inf = x;
		p->link = NULL;
		back = p;
		return true;
	}

	bool pop(T& x) {
		if (!front)
			return false;
		elem<T>* p = front;
		x = front->inf;
		front = front->link;
		if (!front)
			back = NULL;
		delete p;
		return true;
	}

	bool head(T& x) {
		if (!front)
			return false;
		x = front->inf;
		return true;
	}

        void print() const {
                elem<T>* p = front;
                while (p)
                {
                        cout << p->inf << " ";
                        p = p->link;
                }
        }

};