home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / b_queue.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  1.5 KB  |  54 lines
  1. {\magonebf 3.6 Bounded Queues (b\_queue) }
  2.  
  3. An instance $Q$ of the data type $b\_queue$ is a queue (see section 2.4) 
  4. of bounded size. 
  5.  
  6. \bigskip
  7. {\bf 1. Declaration  of a bounded queue type}
  8.  
  9. \decl b\_queue E
  10.  
  11. introduces a new data type with name \name\ consisting all bounded queue with
  12. element type $E$.
  13.  
  14.  
  15. \bigskip
  16. {\bf 2. Creation of a bounded queue}
  17.  
  18. \create Q (n)   
  19.  
  20. creates an instance \var\ of type \name\ that can hold up to $n$ elements.
  21. \var\ is initialized with the empty queue.
  22.  
  23.  
  24. \bigskip
  25. {\bf 3. \operations}
  26. \+\cleartabs & \hskip 2truecm & \hskip 4truecm &\cr
  27. \+\op E     top    {}       
  28.                             { returns the front element of \var}
  29. \+\nop                      { \precond $Q$ is not empty.}
  30. \smallskip
  31. \+\op E     pop    {}       
  32.                             { deletes and returns the front element of \var}
  33. \+\nop                      { \precond $Q$ is not empty.}
  34. \smallskip
  35. \+\op E     append {E\ x}   
  36.                             { appends $x$ to the rear end of \var}
  37. \+\nop                      { \precond $Q$.size()$ < n$.}
  38. \smallskip
  39. \+\op void  clear  {}       
  40.                             { makes \var\ the empty queue.}
  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 Queues are implemented by circular arrays. All operations take 
  52. time $O(1)$. The space requirement is $O(n)$.
  53.  
  54.