3. (a) (4 points) You are given an initially empty stack and perform the followi

Question

3. (a) (4 points) You are given an initially empty stack and perform the following operations on it: push(B), push(A), push(T), push(I), pop), pop0, push(Z), push(A), pop0, push(I), push(N), push(L), pop), push(G), push(A), push(R), push(F), pop0, pop). Show the contents of the stack after all operations have been performed and indicate where the top of the stack is. b) (6 points) Describe how to implement two stacks using one array. The total number of elements in both stacks is limited by the array length; all stack operations (push, pop, size) should run in O(1) time.

Explanation / Answer

Stack contents: ---------------- after push(B) -> [B] after push(A) -> [B, A] after push(T) -> [B, A, T] after push(I) -> [B, A, T, I] after pop() -> [B, A, T] after pop() -> [B, A] after push(Z) -> [B, A, Z] after push(A) -> [B, A, Z, A] after pop() -> [B, A, Z] after push(I) -> [B, A, Z, I] after push(N) -> [B, A, Z, I, N] after push(L) -> [B, A, Z, I, N, L] after pop() -> [B, A, Z, I, N] after push(G) -> [B, A, Z, I, N, G] after push(A) -> [B, A, Z, I, N, G, A] after push(R) -> [B, A, Z, I, N, G, A, R] after push(F) -> [B, A, Z, I, N, G, A, R, F] after pop() -> [B, A, Z, I, N, G, A, R] after pop() -> [B, A, Z, I, N, G, A] final stack is [B, A, Z, I, N, G, A] where A is the top of the stack

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.