2.4 Queues

• A queue is a special kind of a list in which all items are inserted at one end (called the rear or the back or the tail) and deleted at the other end (called the front or the head)
• useful in
  • simulation
  • breadth-first search in graphs
  • tree and graph algorithms
• The Queue ADT is a special case of the List ADT, with the following typical operations

  1.

  makenull (Q)

  2.

  front (Q) $\equiv$ retrieve (first (Q), Q)

  3.

  enqueue (x, Q) $\equiv$ insert (x, end(Q), Q)

  4.

  dequeue (Q) $\equiv$ delete (first (Q), Q)

  5.

  empty (Q)

• Implementation : Pointers, Circular array, Circular linked list