/*******************************************************************************
+
+  LEDA 3.5
+
+  queue.h
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/
#ifndef LEDA_QUEUE_H
#define LEDA_QUEUE_H

#if !defined(LEDA_ROOT_INCL_ID)
#define LEDA_ROOT_INCL_ID 350104
#include <LEDA/REDEFINE_NAMES.h>
#endif


//------------------------------------------------------------------------------
// queue                                                                
//------------------------------------------------------------------------------

#include <LEDA/basic.h>
#include <LEDA/impl/slist.h>


/*{\Manpage {queue} {E} {Queues}}*/

template<class E>

class queue : private SLIST {

/*{\Mdefinition
An instance $Q$ of the parameterized data type |\Mname| is
a sequence of elements of data type $E$, called the element
type of $Q$. Elements are inserted at one end (the rear) and deleted at the
other end (the front) of $Q$. The size of $Q$ is the length of the sequence;
a queue of size zero is called the empty queue.}*/

  void copy_el(GenPtr& x)  const { LEDA_COPY(E,x); }
  void clear_el(GenPtr& x) const { LEDA_CLEAR(E,x); }

public:

/*{\Mcreation Q }*/ 

  queue() {}
/*{\Mcreate creates an instance |\Mvar| of type |\Mname|. |\Mvar| is 
            initialized with the empty queue.}*/

  queue(const queue<E>& Q) : SLIST(Q) {}
 ~queue() { clear(); }
  queue<E>& operator=(const queue<E>& Q) 
  { SLIST::operator=(Q); return *this; }


/*{\Moperations 2 4 }*/

E top() const { return LEDA_ACCESS(E,SLIST::head()); }
/*{\Mop       returns the front element of |\Mvar|.\\
              \precond $Q$ is not empty.}*/


E pop() { E x = top(); SLIST::pop(); return x; }
/*{\Mop       deletes and returns the front element of |\Mvar|.\\
	      \precond $Q$ is not empty.}*/

void append(const E& x) { SLIST::append(leda_copy(x)); }
/*{\Mop       appends $x$ to the rear end of |\Mvar|.}*/

int  size() const { return SLIST::length(); }
/*{\Mop       returns the size of |\Mvar|.}*/

bool  empty() const { return SLIST::empty(); }
/*{\Mop       returns true if |\Mvar| is empty, false otherwise.}*/

void clear() { SLIST::clear(); }
/*{\Mop       makes |\Mvar| the empty queue.}*/

};

/*{\Mimplementation
Queues are implemented by singly linked linear lists. All operations take time 
$O(1)$, except clear which takes time $O(n)$, where $n$ is the size of the 
queue.}*/


#if LEDA_ROOT_INCL_ID == 350104
#undef LEDA_ROOT_INCL_ID
#include <LEDA/UNDEFINE_NAMES.h>
#endif

#endif
