Questions: Stack ADT: Array and Linked-List Implementations

Question 1

An array-based stack doubles its capacity when full. A sequence of 1024 pushes is performed starting from capacity 1. Approximately how many total element-copy operations occur across all resize events?

• A. 1024 copies — each push copies one element
• B. About 2048 copies total — each element is copied on average about twice, giving amortized O(1) per push
• C. About 524,288 copies — each resize copies all elements and there are log₂(1024) resizes
• D. Zero copies — modern arrays don't need to copy on resize

Answer: (B)

With doubling, resizes occur at sizes 1, 2, 4, 8, ..., 512, copying 1 + 2 + 4 + ... + 512 = 1023 elements total. Adding the 1024 pushes themselves, roughly 2047 operations total for 1024 pushes — under 2 operations per push on average. This is the amortized O(1) argument: even though the final resize alone copies 512 elements, that cost is 'paid for' by the preceding 512 cheap pushes. Option C overcounts by treating all resizes as if each one copied n elements.

Question 2

You need a stack for a recursive depth-first search where the maximum depth is unpredictable. Which implementation concern is most relevant?

• A. An array stack is preferred because it is cache-friendly and DFS typically reuses recently accessed elements
• B. A linked-list stack eliminates capacity overflow risk, since each node is individually allocated — important when maximum depth is unknown
• C. Both implementations are equivalent since both guarantee O(1) push and pop
• D. A linked-list stack is always preferred over an array stack for correctness

Answer: (B)

When maximum stack depth is unpredictable, the array's capacity limit becomes a real concern — if the DFS reaches a depth exceeding the array's capacity (even with doubling, very deep recursion can require many doublings or hit memory limits in unexpected ways). A linked-list stack never needs a resize because each node is allocated independently; it naturally grows as long as heap memory is available. Both are O(1) amortized (B is more precise: O(1) worst-case for the linked list), but the unpredictability of depth makes the linked list's lack of capacity overhead more attractive.

Question 3

The stack Abstract Data Type (ADT) defines the behavior — LIFO ordering, push, and pop — independently of how the data is actually stored in memory.

• T. True
• F. False

Answer: True

True. This is the defining idea of an ADT: the interface (what operations are available and how they behave) is separated from the implementation (how the data is stored). A stack implemented with an array and a stack implemented with a linked list are both correct stacks as long as they both enforce LIFO ordering and provide O(1) push and pop. Users of the stack don't need to know — and shouldn't need to know — which internal representation is used.

Question 4

In a linked-list stack, push is expected to traverse to the end of the list to insert the new element, making it an O(n) operation.

• T. True
• F. False

Answer: False

False. Push inserts at the HEAD of the linked list, not the tail. Creating a new node, setting its 'next' pointer to the current head, and updating the head pointer takes exactly three operations regardless of list length — O(1). Similarly, pop reads the head's value, advances the head to head.next, and returns the value — also O(1). Only operations like searching for a specific value or inserting at the tail require O(n) traversal.

Question 5

Explain why an array-based stack that doubles its capacity when full achieves amortized O(1) push, even though individual resize operations cost O(n).

Model answer: When the array doubles, say from size n to 2n, the resize copies n elements. But this resize only occurs after n pushes have been performed since the last resize — all of which were O(1). Spreading the O(n) resize cost across those n pushes gives O(n)/n = O(1) per push. More concretely: after k doublings the array holds 2^k elements, and the total copy work across all doublings is 1 + 2 + 4 + ... + 2^(k−1) = 2^k − 1 < 2^k — less than the total number of pushes. So amortized over all pushes, each push costs less than 2 operations on average.

The key is the doubling factor: doubling ensures that the number of cheap pushes between resizes always equals the cost of the resize itself. If you grew by only 1 each time, the resize at size n would cost O(n), but resizes would happen after every single push — giving O(n) amortized per push, not O(1). Doubling makes resizes rare enough to be 'paid for' by the intervening cheap operations.