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