/*  simple, dynamically-allocated queue type
      includes nearly constant-time enq's and deq's
        by enq-ing at end, deq-ing at beg
      clrq takes time proportional to N

    written by   Warren M Myers   16 Mar 04
    update history:
    16 Mar 04    initial version    implementation based off work in CS2 course at HVCC
*/

#ifndef _QUEUE_H_
#define _QUEUE_H_

template <class T>
class queue{
 public:
    class node{
    public:
	T d;
	node *n;
	node() {n = NULL;}
    };
    //convenience items
    typedef node* np;
    typedef T* dp;
 private:
    T mt;
    np cur;
 public:
    queue(){
	start = new node;
	tail = new node;
	start->n = tail;
    }
    ~queue(){
	clrq();
	delete tail;
	delete start;
    }

    bool enq(T obj){
	if((tail->n = new node) == NULL)
	    return false;        // out of memory error
	tail->n->d = obj;
	tail = tail->n;
	return true;
    }

    bool deq(T &obj=mt){
	cur = start->n;
	if(NULL == cur->n)
	    return false;        // nothing to remove
	obj = cur->d;
	start->n = cur->n;
	delete cur;
	return true;
    }

    void clrq(){
	while(deq());
    }
};

#endif