1. Sahni, Chapter 10, Question 15

  1. Write a singly-linked implementation of the double-ended queue (deque) ADT introduced in Practice Sheet 4.

  2. What is the complexity of each of the methods you have written?

  3. What are the advantages and disadvantages of the singly-linked implementation over the block implementation?
2. Based on Sahni, Chapter 10, Questions 8 and 9

  1. Write implementations of both the stack and queue ADTs by using the deque ADT.

  2. What are the advantages and disadvantages of this approach?
3. Sahni, Chapter 10, Questions 8 and 9

  1. Write implementations of both the stack and queue ADTs by sub-classing the deque ADT.

  2. What are the advantages and disadvantages of this approach?