1 Stack and Queue Consider Stack and Queue data structures discussed in the lectures. For the following pseudocode, please describe program out- put. 1.1 Stack operations Stack s; s.push(1); write s.pop(); s.push(2); s.push(3); write s.pop(); s.push(4); s.push(5); write s.pop(); write s.pop(); write s.pop();

1.2 Queue operations Queue q; q.enqueue(1); write s.dequeue(); q.enqueue(2); q.enqueue(3); write s.dequeue(); q.enqueue(4); q.enqueue(5); write s.dequeue(); write s.dequeue(); write s.dequeue();

2 Signature operations

Except for constructor, destructor, and emptiness test, both Stacks and Queues have other two crucial operations in their interface (di erent for each). For both structures discussed, please de- ne these two operations and describe their behavior.

3 Simulating an Array Arrays let us access an element on an ar- bitrary index (within its range) using the subscript operator [ ]. With this syntax, we can easily get or set the value of a spe- ci c index (random access). Imagine that on some platform, the Ar- ray data structure is not available. Alter- natively, you can consider that you have to perform some Array-like operation in an implementation that uses di erent data structures. Using strictly the abovementioned inter- face of Stacks and Queues, please describe how you could implement the subscript op- erator, i.e. get and set an element on a certain index, using: 3.1 A Queue 3.2 Two Stacks