/*******************************************************************************
+
+  LEDA 3.5
+
+  stack.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_STACK_H
#define LEDA_STACK_H

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


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

//------------------------------------------------------------------------------
// stacks                                                                
//------------------------------------------------------------------------------


/*{\Manpage {stack} {E} {Stacks}}*/ 

template<class E>

class stack : private SLIST {

/*{\Mdefinition
An instance $S$ of the parameterized data type |\Mname| is
a sequence of elements of data type $E$, called the element
type of $S$. Insertions or deletions of elements take place only at one end of
the sequence, called the top of $S$. The size of $S$ is the length of the
sequence, a stack of size zero is called the empty stack.}*/

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

public:


/*{\Mcreation S }*/ 

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

 stack(const stack<E>& S) : SLIST(S) {}
~stack() { clear(); }
 stack<E>& operator=(const stack<E>& S) 
                     { return (stack<E>&)SLIST::operator=(S); }


/*{\Moperations 2 4}*/

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

void push(const E& x) { SLIST::push(leda_copy(x)); }
/*{\Mop      adds $x$ as new top element to |\Mvar|.}*/


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


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 stack.}*/

};

/*{\Mimplementation
Stacks 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 stack.}*/


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

#endif


