Algorithms and Data Structures 2020

Week 4. Stacks and Queues

Exercises

5.1 Exercises

5.1.1 Group Work Wednesday

Problem 5.1 Give a simple adapter that implements the stack ADT using an instance of a double-ended queue.

Problem 5.2 Give a simple adapter that implements the queue ADT using an instance of a double-ended queue.

Problem 5.3 Describe how you can implement the stack ADT using a single queue as an instance variable and only constant additional local memory within the operations push(), pop(), and peek()/top(). What is the running time of the operations in your design?

Problem 5.4 Goodrich et al C-6.16.

5.1.2 Compulsory Projects

Problem 5.5 Goodrich et al P-6.31. Present your solution as pseudo-code and diagrams. If you implement it in Java, this is in addition to a human-readable design description. It is not necessary to implement, and if you do, please reflect on why and whether you find that exercise useful.

Problem 5.6 (freely based on Goodrich et al C-7.48) Consider a message transmitted over the network. It is broken into n data packets which typically arrive at the receiver out of order.

Describe an efficient scheme for the receiver to assemble the packets in the correct order as they arrive. Discuss any assumptions you make. What is the running time?

5.1.3 Practice Problems

Problem 5.7 Goodrich et al C-6.26.

Problem 5.8 Describe an implementation of the stack ADT using an array or array list for storage.

Problem 5.9 Describe an implementation of the deque ADT using an array or array list for storage.