/*
 * Queue Class
 * Written by Aaron J. Miller (20110911)
 */
#include <cstdio>
#include <cassert>

//==============================================================================
// Queue Class
//==============================================================================
template<typename T> class CQueue {
protected:
	struct item_s {
		T obj;
		struct item_s *next;
	} *m_head, *m_tail;

public:
	inline CQueue(): m_head((item_s *)0), m_tail((item_s *)0) {
	}
	inline ~CQueue() {
		while(!IsEmpty())
			Pop();
	}

	inline bool IsEmpty() {
		return m_head!=(item_s *)0?false:true;
	}
	inline void Push(const T &obj) {
		item_s *p;

		p = new item_s();
		p->obj = obj;
		p->next = (struct item_s *)0;

		if (m_tail)
			m_tail->next = p;
		else
			m_head = p;
		m_tail = p;
	}
	inline T Pop() {
		item_s *next;
		T obj;

		assert(!IsEmpty());

		next = m_head->next;

		obj = m_head->obj;
		delete m_head;

		if (!(m_head = next))
			m_tail = (item_s *)0;

		return obj;
	}
	inline void Sort() {
		item_s *prev, *before, *current;
		bool try_again;

		if (m_head==m_tail)
			return;

L_do_sort:
		try_again = false;
		prev = (item_s *)0;

		for
		(
			before=m_head,current=m_head->next;
			current;
			prev=before,before=current,current=current->next
		) {
			if (current->obj < before->obj) {
				try_again = true;
				if (!(before->next = current->next))
					m_tail = before;
				current->next = before;
				if (prev)
					prev->next = current;
				else
					m_head = current;
			}
		}

		if (try_again)
			goto L_do_sort;
	}
};

//==============================================================================
// Test Code
//==============================================================================
int main() {
  CQueue<int> int_queue;

  int_queue.Push(42);
  int_queue.Push(23);
  int_queue.Push(17);
  int_queue.Push(47);
  int_queue.Push(1);
  int_queue.Push(2);
  int_queue.Push(3);

  int_queue.Sort();

  while(!int_queue.IsEmpty())
    printf("%d\n", int_queue.Pop());

  return 0;
}

1
2
3
17
23
42
47