1. you can defi ne ADT operations in a mathematically formal way by using axioms. Consider the following axioms for the ADT queue, where aQueue is an arbitrary queue and item is an arbitrary queue item:
(Queue()).isEmpty() = true
(Queue()).dequeue() = false
(Queue()).peekFront() = error
((Queue()).enqueue(item)).dequeue() = Queue()
((Queue()).enqueue(item)).peekFront() = item
(aQueue.enqueue(item)).isEmpty() = false
(aQueue.enqueue(item)).dequeue() = true
If aQueue is not empty,
(aQueue.enqueue(item)).dequeue() = (aQueue.dequeue()).enqueue(item)
and
(aQueue.enqueue(item)).peek Front() = aQueue.peek Front()
a. Note the recursive nature of the definition of peek Front . What is the base case? What is the recursive step? What is the significance of the is Empty test? Why is the queue operation peek Front recursive in nature while the stack operation peek for the ADT stack is not?
b. The representation of a stack as a sequence of push operations without any pop operations is called a canonical form.Is there a canonical form for the ADT queue? That is, can you represent a queue as a sequence of enqueue operations without any dequeue operations? Prove your answer.