September 6, 2011
A normal linked list can be accessed only at its head. A double-ended queue, or deque (pronounced “deck”), can be accessed at either end. Like a normal list, a deque can be null. New elements can be added at either end, the element at either end of a non-null deque can be fetched, and the element at either end of a non-null deque can be deleted. Deques are a combination of stacks and queues.
Your task is to write a function library that implements deques; you should be sure that all operations are performed in constant time. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Pages: 1 2