# Week 4. Stacks and Queues

## Algorithms and Data Structures

### 5 Week 4. Stacks and Queues

Reading 4 Goodrich, Tamassia, & Goldwasser: Chapter 6–7. Java specific sections are cursory only.

- 1.
- Stack
- 2.
- Queue

#### 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.