Mastering Algorithms with C

Questions and Answers

Q: If Stack and Queue are not made typedefs of List, what are the implications for the stack and queue abstract datatypes?

A: Making Stack and Queue both typedefs of List has some nice benefits, but alternative approaches could be chosen to implement these data structures. For example, Stack and Queue could be made their own unique structures consisting of the same members as List. However, this would not allow the use of linked list operations in the implementation. Another approach would be to implement stacks and queues as structures that each contain a linked list member. This would allow the use of linked list operations in the implementation, but it does not model very nicely what stacks and queues really are. That is, stacks and queues do not have linked lists as part of them; they are linked lists.

Q: Why is there no stack_next macro for stacks and no queue_next macro for queues? These operations would have provided a way to traverse the members of a stack or queue, respectively.

A: By implementing the Stack and Queue data structures as typedefs of List, there is no need for these operations because we can call list_next. This is good because traversing the members of a stack or queue is not generally part of the normal behavior of these abstract datatypes. By making a developer use operations of a linked list when a stack or queue needs to act like one, we maintain a pure interface to the stack and queue.

Q: Sometimes we need to remove an element from ...