Use a two-list functional queue. Its representation (front, rear) denotes the abstract sequence front @ rev rear; the front is nonempty unless the whole FIFO queue is empty. Normalize only when the front runs out:
sml
datatype 'a queue = Q of 'a list * 'a list;
exception EmptyQueue;

fun check ([], rear) = Q (rev rear, [])
  | check (front, rear) = Q (front, rear);

fun empty () = Q ([], []);
fun isEmpty (Q (front, _)) = null front;
fun enqueue x (Q (front, rear)) = check (front, x :: rear);

fun peek (Q ([], _)) = raise EmptyQueue
  | peek (Q (x :: _, _)) = x;

fun dequeue (Q ([], _)) = raise EmptyQueue
  | dequeue (Q (x :: front, rear)) = (x, check (front, rear));
Enqueue prepends to the reversed rear list. Removing the head either leaves a nonempty front or reverses the accumulated rear to restore the invariant. The result pair from dequeue contains the removed element and the new FIFO queue. The constructor should be hidden behind an abstract interface so clients cannot construct an unnormalized representation that invalidates isEmpty.

Ancestors (12)

  1. ii
  2. a
  3. 5
  4. Paper 5
  5. ia
  6. 2006
  7. Past exam of the mathematics course of the University of Cambridge
  8. Mathematics course of the University of Cambridge
  9. Course of the University of Cambridge
  10. University of Cambridge
  11. List of universities
  12. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version