home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / queue.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  2.0 KB  |  71 lines
  1. {\magonebf 3.4 Queues (queue)  }
  2.  
  3. An instance $Q$ of the data type $queue$ is 
  4. a sequence of elements of a data type $E$, called the element 
  5. type of $Q$. Elements are inserted at one end (the rear) and deleted at the 
  6. other end (the front) of $Q$. The size of $Q$ is the length of the sequence, 
  7. a queue of size zero is called the empty queue.
  8.  
  9.  
  10. \bigskip
  11. {\bf 1. Declaration of a queue type}
  12.  
  13. \decl  queue E 
  14.  
  15. introduces a new data type with name \name\ consisting all all queues with
  16. element type $E$.
  17.  
  18.  
  19. \bigskip
  20. {\bf 2. Creation of a queue }
  21.  
  22. \create Q {}
  23.  
  24. creates an instance \var\ of type \name. \var\ is initialized with the empty 
  25. queue.
  26.  
  27.  
  28.  
  29. \bigskip
  30. {\bf 3. \operations}
  31. \+\cleartabs & \hskip 2truecm & \hskip 4truecm &\cr
  32. \+\op E     top    {}       
  33.                             { returns the front element of \var}
  34. \+\nop                      { \precond $Q$ is not empty.}
  35. \smallskip
  36. \+\op E     pop    {}       
  37.                             { deletes and returns the front element of \var}
  38. \+\nop                      { \precond $Q$ is not empty.}
  39. \smallskip
  40. \+\op E     append {E\ x}   
  41.                             { appends $x$ to the rear end of \var.}
  42. \smallskip
  43. \+\op void  clear  {}       
  44.                             { makes \var\ the empty queue.}
  45. \smallskip
  46. \+\op int   size   {}       
  47.                             { returns the size of \var.}
  48. \smallskip
  49. \+\op bool  empty  {}       
  50.                             { returns true if \var\ is empty, false otherwise.}
  51.  
  52. \bigskip
  53. {\bf 4. Implementation}
  54.  
  55. Queues are implemented by singly linked linear lists. All operations take time 
  56. $O(1)$, except clear which takes time $O(n)$, where $n$ is the size of the 
  57. queue.
  58.  
  59.  
  60. %\bigskip
  61. %{\bf 5. Bounded Queues}
  62. %
  63. %Bounded queues (b\_queues) are queues of bounded size. 
  64. %\medskip
  65. %\+\cleartabs
  66. %  Declaration: &{\bf declare}($b\_queue,E$) \cr
  67. %\+Creation:    &$b\_queue(E)$ $Q(n)$; \cr
  68. %\+             &creates an instance $Q$ of type $b\_queue(E)$ that can hold up to $n$ elements.\cr
  69. %\+Operations:  &see queue\cr
  70. %
  71.