List as Stack — Use list as a stack (append/pop) and explain amortized behavior (conceptual) - Python

SECTION 1

Historical Context & Motivation

The idea of a stack is one of the oldest and most important concepts in computer science. A stack is a collection of items where you can only add or remove from the top — much like a stack of cafeteria trays. This simple rule, called Last-In, First-Out (LIFO), powers everything from the "undo" button in your text editor to how your computer tracks function calls while running a program.

1946 • Alan Turing's Stack Concept

Alan Turing described the concept of "burying" and "unburying" return addresses during subroutine calls, which is essentially stack behavior.

1957 • Formal Stack Definition

Friedrich Bauer and Klaus Samelson formally proposed the stack as a data structure and received a patent for their design, establishing it as a core computing concept.

1991 • Python Is Born

Guido van Rossum released Python 0.9.0, which included the list type. Python lists used dynamic arrays, making them natural candidates for stack operations.

2000s • Amortized Analysis Popularized

Textbooks and courses began emphasizing amortized analysis to explain why dynamic array operations — like Python's append — are efficient on average even though individual operations occasionally take longer.

Today, when you use a Python list and call append() and pop(), you're using a stack without even realizing it. But a natural question arises: if the list sometimes needs to resize itself in memory, how can we say these operations are fast? The answer lies in a clever idea called amortized analysis, which looks at the average cost over many operations rather than the worst case of a single one.

SECTION 2

Core Principles & Definitions

Before diving into code, let's nail down the foundational ideas. A stack enforces a strict access pattern: you only interact with the top element. Python's built-in list type is implemented as a dynamic array, meaning it stores elements in a contiguous block of memory that can grow when needed. This design makes the end of the list the natural "top" of our stack.

LIFO — Last-In, First-Out

The most recently added item is the first one removed. Think of stacking books: you grab the top one first.

append() — Push Operation

Calling my_list.append(item) adds an element to the end (top) of the stack in O(1) amortized time.

pop() — Pop Operation

Calling my_list.pop() removes and returns the last element (top) in O(1) time, since no shifting is needed.

Dynamic Array Resizing

When the internal array is full, Python allocates a bigger block (roughly 1.125× the old size) and copies all elements over. This is the occasional expensive step.

Amortized O(1)

Although resizing is costly, it happens so infrequently that the average cost per append, spread across many operations, is still constant time.

✦

KEY TAKEAWAY

Think of a stack like a Pringles can. You can only add a chip on top (push / append) and take a chip from the top (pop). You never reach into the middle. Python's list lets you do exactly this with append() and pop(), and the dynamic array underneath makes it efficient.

SECTION 3

Visual Explanation — Stack Operations on a List

The diagram below shows how a Python list behaves as a stack through a sequence of append() and pop() operations. Notice that all action happens at the right end (the "top" of the stack). Each column represents the state of the list after one operation.

The horizontal view (top) shows the list state after each operation. The vertical view (bottom) illustrates the stack metaphor: items stack upward, and pop() always removes the topmost element.

Notice how append() always adds to the right end of the list, and pop() always removes from the right end. This is critical: because no other elements need to shift position, both operations are O(1) — constant time in the typical case. If you were to use insert(0, item) or pop(0) instead, every element would need to shift, making those operations O(n) — much slower.

SECTION 4

How Dynamic Arrays Power the Stack

Under the hood, a Python list is a dynamic array. It reserves a block of memory with some extra room (called capacity) beyond what's currently needed. When you call append() and there's space left, the item drops right in — that's a fast, O(1) operation. But when the capacity is full, Python must allocate a larger block, copy all existing elements to it, and then add the new item. This resize is an O(n) operation.

The Resizing Strategy

Python doesn't just add one extra slot when it resizes — it over-allocates by a growth factor (roughly 1.125× for larger lists). This means resizes happen less and less frequently as the list grows. The key insight is that each expensive resize "pays" for many cheap appends that follow.

AMORTIZED COST PER APPEND

Amortized cost = Total cost of n appends ÷ n ≈ O(1)

Even though some individual appends cost O(n) due to resizing, the total cost of n consecutive appends is O(n). Dividing by n gives an amortized cost of O(1) per operation.

RESIZING FREQUENCY

Resize at append #: 4, 8, 16, 33, 54, 87, ...

Python's growth pattern means that out of, say, 1000 appends, only about 30–40 trigger a resize. The vast majority are fast, single-slot insertions.

ℹ

Why Not Double?

Many textbooks describe dynamic arrays that double in size (2× growth factor). Python uses a smaller growth factor (roughly 1.125×) to save memory. The trade-off is slightly more frequent resizing, but the amortized cost remains O(1).

SECTION 5

Understanding Amortized Behavior

Amortized analysis is a way of thinking about the "true" cost of an operation when you plan to do it many times. Instead of focusing on the worst case of a single call, you spread the total cost across all calls. Let's visualize what happens to the cost of each append() call over a sequence of operations.

Green bars show cheap O(1) appends. Red bars mark expensive resizes at calls 2, 4, and 8 (powers of 2 in a doubling scheme). The dashed yellow line shows the amortized average cost — roughly 2 units of work per operation, which is still O(1).

Here's the intuition: imagine each cheap append "saves up" a small amount of extra work credit. When a resize finally happens, all those saved-up credits pay for the expensive copy. Because the array grows by a multiplicative factor, you accumulate enough credits before the next resize occurs. The result is that the average cost stays constant, no matter how large the list gets.

Append #	Capacity Before	Resize?	Cost	Capacity After
1	0	Yes → 4	1	4
2	4	No	1	4
3	4	No	1	4
4	4	No	1	4
5	4	Yes → 8	5	8
6–8	8	No	1 each	8
9	8	Yes → 16	9	16

Capacity changes during a sequence of appends (doubling growth factor for simplicity)

🐷

THE PIGGY BANK ANALOGY

Think of amortized analysis like saving coins in a piggy bank. Every cheap append drops $1 in. When a resize happens, you break open the bank to "pay" for copying everything. Because you saved enough between resizes, you never go broke. Over time, each append effectively costs about $2 — always constant, always affordable.

SECTION 6

Worked Example — Building and Unwinding a Stack

Let's walk through a complete example: reversing a string using a Python list as a stack. This is a classic stack application that clearly demonstrates the LIFO principle.

Reversing a String with a Stack

1
Step 1 — Define the Problem

We want to reverse the string "hello" to get "olleh". We'll push each character onto a stack, then pop them all off. Since stacks are LIFO, the characters come out in reverse order.
2
Step 2 — Push All Characters

We iterate through the string and append each character to our list-stack:stack = [] for char in "hello": stack.append(char)After this loop, the stack contains:

['h', 'e', 'l', 'l', 'o'] — 'o' is on top
3
Step 3 — Pop All Characters

Now we pop each character and build the reversed string:reversed_str = "" while stack: reversed_str += stack.pop()Each pop() removes the top element: first 'o', then 'l', then 'l', then 'e', then 'h'.

reversed_str = "olleh"
4
Step 4 — Analyze Performance

We performed 5 append() calls and 5 pop() calls. Each is O(1) amortized, so the total time is O(n) where n is the length of the string. The stack itself uses O(n) extra memory.

Time complexity: O(n) | Space complexity: O(n)
5
Step 5 — Complete Code

Here's the full function:def reverse_string(s): stack = [] for char in s: stack.append(char) result = "" while stack: result += stack.pop() return result print(reverse_string("hello")) # Output: olleh

Output: olleh

SECTION 7

List-as-Stack vs. Other Approaches

Python gives you multiple ways to implement a stack. The built-in list is the most common, but the standard library also provides collections.deque. Meanwhile, you should avoid certain list operations that break the efficiency of stack behavior. Let's compare.

Feature	list (append/pop)	list (insert(0)/pop(0))	collections.deque
Push time	O(1) amortized	O(n)	O(1)
Pop time	O(1)	O(n)	O(1)
Random access	O(1)	O(1)	O(n)
Memory layout	Contiguous array	Contiguous array	Linked blocks
Best use	Stack (LIFO)	Avoid this pattern	Queue or double-ended

Comparison of stack implementation strategies in Python

⚠

Common Mistake

Never use insert(0, item) or pop(0) to simulate a stack. These operations must shift every element in the list, turning your O(1) stack into an O(n) disaster. Always use the end of the list as your stack top.

✦

KEY TAKEAWAY

For a pure stack in Python, list with append() and pop() is the standard and recommended approach. It's simple, fast, and built into the language. collections.deque shines when you need both ends (like a queue), but for stack-only use, a plain list is ideal.

SECTION 8

Connecting to Advanced Concepts

The list-as-stack pattern you've learned here is a building block for many important algorithms and systems. Understanding stacks and amortized analysis prepares you for more advanced computer science topics.

What You Learned	Where It Leads
LIFO with append/pop	The call stack — how your computer tracks function calls and returns. Recursion relies on this.
Stack-based algorithms	Depth-first search (DFS), expression evaluation, balanced parentheses checking, undo/redo systems.
Amortized O(1) analysis	Hash table resizing, splay trees, and other data structures that use "pay a little now, save a lot later" strategies.
Dynamic array growth	Understanding memory allocation, cache performance, and how languages like Java (ArrayList) and C++ (std::vector) work internally.

How this lesson connects to advanced CS topics

One particularly important connection is the call stack. Every time you call a function in Python, the interpreter pushes information about that call onto an internal stack. When the function returns, it pops that information off. This is why infinite recursion causes a RecursionError — the call stack runs out of space! Understanding the list-as-stack gives you direct intuition for how this fundamental mechanism works.

💡

Looking Ahead

In a data structures or algorithms course, you'll encounter formal proofs of amortized analysis using techniques called the accounting method (the "piggy bank" approach) and the potential method. The conceptual understanding you built here is the foundation those formal methods are built upon.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain why pop() (with no argument) is O(1) but pop(0) is O(n) for a Python list. What is the key difference between removing from the end versus the beginning?

Show answer

When you call pop() with no argument, Python removes the last element. Since no other elements need to move, this takes constant time — O(1). However, pop(0) removes the first element, which means every remaining element must shift one position to the left to fill the gap. If there are n elements, that's n − 1 shifts, making it O(n). The key difference is that a dynamic array stores elements contiguously, so removing from the front creates a hole that must be filled by shifting.

Question 2: BASIC CALCULATION

Trace the following code and write the exact output:


stack = []
stack.append(5)
stack.append(10)
stack.append(15)
print(stack.pop())
stack.append(20)
print(stack.pop())
print(stack.pop())
print(stack)

Show answer

Let's trace step by step. After three appends, the stack is [5, 10, 15]. The first pop() removes and prints 15 (the top). Then append(20) gives us [5, 10, 20]. The next pop() removes and prints 20. The third pop() removes and prints 10. Finally, printing the stack shows [5]. The output is: 15, 20, 10, [5] — each on a separate line.

Question 3: INTERMEDIATE

Write a function is_balanced(s) that uses a list as a stack to check whether a string of parentheses (), [], and {} is properly balanced. For example, "({[]})" returns True, and "([)]" returns False.

Show answer

The idea is to push every opening bracket onto the stack. When we encounter a closing bracket, we pop the top and check if it matches. If the stack is empty when we try to pop, or if the brackets don't match, the string is unbalanced. At the end, the stack should be empty. Here's the solution:

def is_balanced(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return len(stack) == 0

Each character is processed once, so the time complexity is O(n). The stack uses at most O(n) space.

Question 4: APPLIED

A web browser's back button works like a stack. Design a simple BrowserHistory class with three methods: visit(url) to navigate to a new page, back() to go to the previous page (returning the URL), and current() to see the current page. Use a Python list as your stack.

Show answer

We use a list to store the browsing history. visit() appends the URL to the stack. back() pops the current page and returns the new top page. current() peeks at the top without removing it, using stack[-1]. Implementation:

class BrowserHistory:
    def __init__(self, homepage):
        self.stack = [homepage]
    def visit(self, url):
        self.stack.append(url)
    def back(self):
        if len(self.stack) > 1:
            self.stack.pop()
        return self.stack[-1]
    def current(self):
        return self.stack[-1]

Note that back() guards against popping the homepage. All operations are O(1) amortized.

Question 5: CRITICAL THINKING

Suppose you perform 1,000 append() operations on an empty list using a doubling strategy (capacity goes 1 → 2 → 4 → 8 → ... → 1024). Calculate the total number of element copies due to resizing, and use this to argue that the amortized cost per append is O(1). How would the total copies change if the list only added one extra slot on each resize instead of doubling?

Show answer

With doubling, resizes happen when the list reaches sizes 1, 2, 4, 8, 16, ..., 512. At each resize from capacity k to 2k, we copy k elements. Total copies = 1 + 2 + 4 + 8 + ... + 512 = 2¹⁰ − 1 = 1,023. So for 1,000 appends, we do about 1,023 copies plus 1,000 insertions — roughly 2,023 total units of work. Dividing by 1,000 gives about 2 units per append, which is O(1). With a +1 strategy, a resize happens on every single append after the first: at append #2 you copy 1 element, at #3 you copy 2, at #4 you copy 3, and so on. Total copies = 1 + 2 + 3 + ... + 999 = 999 × 1000 ÷ 2 = 499,500. Dividing by 1,000 gives an amortized cost of about 500 — which is O(n), not O(1). This demonstrates why multiplicative growth is essential for amortized constant-time performance.

SUMMARY

Lesson Summary

Summary

A Python list can be used as a stack by using append() to push items onto the top and pop() to remove them, enforcing the Last-In, First-Out (LIFO) principle. Under the hood, the list is a dynamic array that occasionally resizes by allocating a larger memory block and copying elements. Although a single resize costs O(n), this expense is spread across many cheap O(1) operations.

This spreading of cost is called amortized analysis, and it shows that both append() and pop() run in amortized O(1) time. Always operate on the end of the list — never use insert(0) or pop(0) for stack behavior, as those require shifting all elements and are O(n). Stacks power many real-world systems including browser history, undo features, function call tracking, and algorithms like depth-first search.