Five tasks.

---

1. (*History) Peek() (Item, bool)

Returns the top without removing it.

Why is that a separate operation rather than a Pop followed by a Push? How does your History differ between the two?

---

2. Balanced brackets

Balanced(s string) bool — checks that (), [] and {} are matched.

The classic stack problem. How much memory does it need in the worst case? Express it in terms of the input length.

---

3. A growing ring

Ours returns false when full. Change it to double its capacity instead.

Count the elements copied for 100,000 items. Compare with lesson 2's append measurement — is it the same number? Explain.

---

4. A queue from two stacks

Implement Queue using only two History values.

Count the elements moved per removal. The worst case is O(n) — but amortized it is O(1). Measure both and show the difference.

---

5. Where the counter fools you again

Step 3 showed that an operation count cannot see memory.

Find a second thing it cannot see. Measure it some other way and show the count lying.

(Hint: two implementations can do the same number of comparisons and still differ in speed. Lesson 4 does not mention this. Lesson 6 does.)