queue, C++ (gcc) - rextester

queue

#include "iostream"
#include "string"
#include "sstream"

template <typename T>
class queue
{
	struct Node
	{
		T value;
		size_t priority;
		Node *next, *prev;
	};
	Node *head, *tail;
public:
	queue()
	{
		head = tail = nullptr;
	}
	queue(const queue& l)
	{
		Node* e(l.tail);
		while (e) {
			push(e->value, e->priority);
			e = e->prev; 
		}
	}
	~queue()
	{
		Node* e(head);
		while (e) {
			Node* buf(e->next);
			delete e; e = buf;
		}
	}
	void push(T val, size_t p)
	{
		Node* e(new Node);
		e->value = val;
		e->priority = p;
		if (head) {
			Node* s(head);
			while (e->priority > s->priority) {
				s = s->next;
				if (!s) {
					e->next = nullptr;
					e->prev = tail;
					tail->next = e;
					tail = e;
					return;
				}
			}
			if (s == head) {
				e->next = head;
				e->prev = nullptr;
				head->prev = e;
				head = e;
				return;
			}
			e->next = s;
			e->prev = s->prev;
			s->prev->next = e;
			s->prev = e;
		}
		else {
			e->next = e->prev = nullptr;
			head = tail = e;
		}
	}
	T pop()
	{
		Node* e(tail);
		if (e != head) {
			e = e->prev;
		}
		T val = tail->value;
		delete tail;
		tail = e;
		e->next = nullptr;
		return val;
		
	}
	void print()
	{
		std::cout << toString() << std::endl;
	}
	void clear()
	{
		Node* e(head);
		while (e) {
			Node* buf(e->next);
			delete e; e = buf;
		}
		head = tail = nullptr;
	}
	std::string toString()
	{
		if (head) {
			Node* e(head);
			std::string s = "";
			if (e == tail) {
				std::stringstream out;
				out << e->value;
				s = "{ " + out.str() + " }";
				return s;
			}
			s = "{ ";
			while (e) {
				std::stringstream out;
				out << e->value;
				s += out.str() + ", ";
				e = e->next;
				if (e == tail) {
					std::stringstream out;
					out << e->value;
					s += out.str() + " }";
					return s;
				}
			}
		}
		else {
			return "{ empty }";
		}
	}
	queue& operator = (const queue& l)
	{
		clear();
		Node* e(l.tail);
		while (e) {
			push(e->value, e->priority);
			e = e->prev;
		}
		return *this;
	}
	friend queue operator+ (const queue& q1, const queue& q2) {
		queue newQ(q1);
		Node* e(q2.tail);
		while (e) {
			newQ.push(e->value, e->priority);
			e = e->prev;
		}
		return newQ;
	}
};

int main()
{
	queue<int> a, b, c;
	a.push(2, 0);
	a.push(4, 3);
	a.push(1, 0);
	a.push(3, 2);
	std::cout << "a: "; a.print();
	b.push(1, 4);
	std::cout << "b: "; b.print();
	c = a + b;
	std::cout << "a + b = "; c.print();
	std::cout << "a: "; a.print();
	std::cout << "b: "; b.print();
}


run \| edit \| history \| help	0