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:
- a constructor to return an empty queue
(make-queue) - two selectors
- to test if queue is empty
(empty-queue? <queue>) - to return the object at the front of the queue without modification
(front-queue <queue>)
- to test if queue is empty
- two mutators
- to insert an item at the rear of the queue
(insert-queue! <queue> <item>) - to remove the item at the front of the queue, and also delete it, returning the modified queue
(delete-queue! <queue>)
- to insert an item at the rear of the 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