Stack (resizing array)

Cost and properties

push / pop	O(1) amortised
worst-case push	O(n) — the doubling
space	8n to 32n bytes
rule	double when full, halve at ¼

Reference: Sedgewick & Wayne, §1.3.

Stack (resizing array) in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

class ResizingArrayStack:
    def __init__(self):
        self.a = [None]                   # capacity 1
        self.n = 0                        # items in a[0..n-1]

    def _resize(self, capacity):          # this is the expensive part
        self.a = self.a[:self.n] + [None] * (capacity - self.n)

    def push(self, item):
        if self.n == len(self.a):
            self._resize(2 * len(self.a))  # DOUBLE when full
        self.a[self.n] = item
        self.n += 1

    def pop(self):
        if self.n == 0:
            raise IndexError('stack underflow')
        self.n -= 1
        item = self.a[self.n]
        self.a[self.n] = None             # avoid loitering
        if self.n > 0 and self.n == len(self.a) // 4:
            self._resize(len(self.a) // 2)  # HALVE at one quarter full
        return item

Why it works

Amortised, not worst case

Growing from 1 to n costs 1 + 2 + 4 + … + n < 2n copies in total, spread over n pushes: about 3 array accesses per push on average. Any single push can still cost n. The distinction is the point — amortised analysis is a claim about a sequence of operations, never about one.

Why halve at a quarter, not a half

Halving at half-full would thrash: push (double), pop (halve), push (double) … each operation copying the whole array. Shrinking only at one quarter leaves the array between 25% and 100% full, so after a resize you need Θ(n) operations before the next one. Slack is what buys the amortised bound.

Compare the two stacks

• Linked list: constant worst case, more memory, pointer chasing.
• Resizing array: less memory, better locality (much faster in practice), occasional slow operation.

Same API. This is the first place the course makes you choose an implementation by which cost you care about, not by which is “better”.

Loitering again

self.a[self.n] = None is not tidiness — without it the array holds a reference to a popped object forever, and the garbage collector cannot reclaim it. A memory leak that no test will catch.

What to try in the animation

A word pushes it; a - pops. The default is the course's tobe.txt test string.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• tobe.txt (course) — to be or not to - be - - that - - - is
• watch it double — a b c d e f g h i
• push/pop at the boundary — a b c d - - d - d - d -

Open Stack (resizing array) in the player →

The rest of Stacks and queues

• Stack (linked list) Push and pop at the front of a singly linked list.
• Queue (linked list) Enqueue at the back, dequeue from the front.