Queues

Last-in-first-out (LIFO) sequence data structures, i.e, items are inserted at one end (rear) and deleted from the other end (front).

Abstractly, it can be defined by:

  1. a constructor to return an empty queue (make-queue)
  2. two selectors
    1. to test if queue is empty (empty-queue? <queue>)
    2. to return the object at the front of the queue without modification (front-queue <queue>)
  3. two mutators
    1. to insert an item at the rear of the queue (insert-queue! <queue> <item>)
    2. to remove the item at the front of the queue, and also delete it, returning the modified queue (delete-queue! <queue>)

Could be represented as a simple list, but much more efficient to just store a pointer to the end of the list as well as the beginning.


Links

Sources