COS 226 Exercises on Stacks and Queues

NAME:

LOGIN:

PRECEPT:

COLLABORATORS:

COS 226 Exercises on Stacks and Queues

1. [Exercise 4.7.2] A letter means enqueue and an asterisk means dequeue in the sequence E A S * Y * Q U E * * * S T * * * I O * N * * * Give the sequence of values returned by the dequeue operations when this sequence of operations is performed on an initially empty FIFO queue.

2. Describe how to implement a queue using two stacks. All queue operations (enqueue and dequeue) should take constant amortized time. That is, starting from an initially empty queue, any sequence of N enqueue and dequeue operations should take time proportional to N.