CSCI 3300
Fall 2009
Exercises for Quiz 12

1. If a first-in-first-out queue is implemented efficiently, how long does each operation take, to within a constant factor?

   Answer

2. Does a queue have to be implemented in a destructive way, or does it make sense to have a nondestructive implementation of the concept of a queue?

   Answer

3. A quasi-deque is similar to a queue in that it holds, at any given time, a sequence of values. But there are four operations, plus one constructor. This is a destructive data structure, so operations typically change what it is holding.

   QDeque

   When a quasi-deque is created, it is initially empty.

   isEmpty(d)

   This is true if d is empty

   insertAtFront(d, x)

   This inserts x at the front of d

   insertAtBack(d, x)

   This inserts x at the back of d

   removeFromFront(d, x)

   This removes the front value from quasi-deque d, and stores it into variable x. Notice that x must be call-by-reference, since it is an out parameter. An attempt to remove a value from an empty quasi-deque does nothing, and does not store anything into x.

   Using a linked list to represent the members of the quasi-deque, write an implementation of type QDeque, including a type, a constructor and all of the functions. Assume that the members of a quasi-deque have type QDequeMemberType. For now, define QDequeMemberType to be int, but make it so that the type can be changed by changing only one line of the program.

   Answer