home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / b_stack.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  1.5 KB  |  54 lines
  1.  
  2. {\magonebf 3.5 Bounded Stacks (b\_stack) }
  3.  
  4. An instance $S$ of the data type $b\_stack$ is a stack (see section 2.3) 
  5. of bounded size. 
  6.  
  7. \bigskip
  8. {\bf 1. Declaration  of a bounded stack type}
  9.  
  10. \decl b\_stack E
  11.  
  12. introduces a new data type with name \name\ consisting all bounded stacks with
  13. element type $E$.
  14.  
  15.  
  16. \bigskip
  17. {\bf 2. Creation of a bounded stack}
  18.  
  19. \create S (n)   
  20.  
  21. creates an instance \var\ of type \name\ that can hold up to $n$ elements.
  22. \var\ is initialized with the empty stack.
  23.  
  24.  
  25. {\bf 3. \operations}
  26. \+\cleartabs & \hskip 2truecm & \hskip 4truecm &\cr
  27. \+\op E       top   {}        
  28.                               {returns the top element of \var}
  29. \+\nop                        {\precond $S$ is not empty.}
  30. \smallskip
  31. \+\op E       pop   {}        
  32.                               {deletes and returns the top element of \var}
  33. \+\nop                        {\precond $S$ is not empty.}
  34. \smallskip
  35. \+\op E       push  {E\ x}    
  36.                               {adds $x$ as new top element to \var}
  37. \+\nop                        {\precond $S$.size() $< n$.}
  38. \smallskip
  39. \+\op void    clear {}        
  40.                               {makes \var\ the empty stack.}
  41. \smallskip
  42. \+\op int     size  {}        
  43.                               {returns the size of \var.}
  44. \smallskip
  45. \+\op bool    empty {}        
  46.                               {returns true if \var\ is empty, false otherwise.}
  47.  
  48. \bigskip
  49. {\bf 4. Implementation}
  50.  
  51. Bounded Stacks are implemented by \CC vectors. All operations take 
  52. time $O(1)$. The space requirement is $O(n)$.
  53.  
  54.