If a first-in-first-out queue is implemented efficiently, how long does each operation take, to within a constant factor?
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?
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
isEmpty(d)
insertAtFront(d, x)
insertAtBack(d, x)
removeFromFront(d, 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.