StacksLesson 2

Implementing a Stack

Build a stack from scratch using an array, then using a linked list. Compare the two implementations and their trade-offs.

What Is It?

Now that you know what a stack does, let's build one. There are two common ways:

  1. Array-based stack — use a regular array plus a number that tracks where the top is.
  2. Linked-list-based stack — use a chain of nodes where adding and removing always happens at the front.

Both give you O(1) — instant — push, pop, and peek. The main difference is how they handle memory.

Analogy

Think of two ways to stack books:

Array approach: You have a shelf with 10 numbered slots (0 through 9). You fill slots from left to right. A sticky note on the shelf says "top = 2" so you always know where the current top is. Fast and simple, but you can't fit more than 10 books without getting a bigger shelf.

Linked list approach: You tie each new book to the previous one with a piece of string. You always hold the string attached to the newest book. To add, tie the new book to the current top and switch to holding the new string. To remove, follow the string to the next book. No limit on books, but each book needs its own piece of string (a little extra memory).

How It Works

Implementation 1: Array-Based Stack

The idea is simple. Use an array and an integer called top that starts at -1 (meaning the stack is empty). Each push moves top up by one and stores the value. Each pop reads the value and moves top down by one.

pseudocode
1
2
3
structure ArrayStack:
    array = new array of size CAPACITY
    top = -1

What it looks like in memory:

pseudocode
1
2
3
4
5
Capacity = 5
Index:   [0]  [1]  [2]  [3]  [4]
Data:    [10] [20] [30] [  ] [  ]
                    ^
                   top = 2

The top is at index 2 (value 30). Slots 3 and 4 are unused.

#### Full Pseudocode

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function push(stack, value):
    if stack.top equals CAPACITY - 1:
        error("Stack is full")
    stack.top = stack.top + 1
    stack.array[stack.top] = value
​
function pop(stack):
    if stack.top equals -1:
        error("Stack is empty")
    value = stack.array[stack.top]
    stack.top = stack.top - 1
    return value
​
function peek(stack):
    if stack.top equals -1:
        error("Stack is empty")
    return stack.array[stack.top]
​
function isEmpty(stack):
    return stack.top equals -1
​
function size(stack):
    return stack.top + 1

#### Tracing Through Operations

Array-Based Stack Trace— top index and array contents
1 / 8
(initial) top=-1
_
_
_
_
_
[0]
[1]
[2]
[3]
[4]

After popping, the old values still sit in the array — but they're invisible because top has moved below them. They'll be overwritten by future pushes. We never look at anything above top, so it doesn't matter.

#### Time Complexity

Every operation is O(1) — instant. No loops, no searching. Just move an index and read or write one slot.

#### What If the Array Gets Full?

If you push past the capacity, that's a stack overflow. Two solutions:

  • Pick a capacity large enough for your use case.
  • Use a dynamic array: when the array fills up, create a new one double the size and copy everything over. This makes push O(1) on average — it's occasionally slow (during the copy) but fast almost every time.

Implementation 2: Linked-List-Based Stack

The idea: each item is a node — a small object that holds a value and a pointer to the next node. The top of the stack is always the first node (called the head). Push adds a new node at the front. Pop removes the front node. Both are instant.

pseudocode
1
2
3
4
5
6
7
structure Node:
    data
    next
​
structure LinkedStack:
    head = null
    count = 0

What it looks like:

pseudocode
1
2
3
4
5
6
7
8
9
10
11
top (head)
  |
  v
[30|*]-->[20|*]-->[10|null]
​
After push(40):
​
top (head)
  |
  v
[40|*]-->[30|*]-->[20|*]-->[10|null]

#### Full Pseudocode

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function push(stack, value):
    newNode = new Node(value)
    newNode.next = stack.head
    stack.head = newNode
    stack.count = stack.count + 1
​
function pop(stack):
    if stack.head is null:
        error("Stack is empty")
    value = stack.head.data
    stack.head = stack.head.next
    stack.count = stack.count - 1
    return value
​
function peek(stack):
    if stack.head is null:
        error("Stack is empty")
    return stack.head.data
​
function isEmpty(stack):
    return stack.head is null
​
function size(stack):
    return stack.count

#### Tracing Through Operations

Linked-List Stack Trace— head chain (top at head)
1 / 8
(initial)
null
[0]

#### Time Complexity

All operations are O(1) — instant. You're just updating a pointer or two.

#### No Capacity Limit

The linked list grows as long as your computer has memory. No need to worry about overflow or resizing.

Comparison: Array vs. Linked List

Array-Based Stack

  • push / pop / peek: O(1)
  • Contiguous memory layout
  • Fixed capacity (or resize)
  • No extra memory per element
  • Excellent cache performance
  • Overflow possible with fixed array

contiguous memory

Linked-List Stack

  • push / pop / peek: O(1)
  • Scattered memory layout
  • Unlimited dynamic capacity
  • One pointer per node overhead
  • Poor cache (pointer chasing)
  • Practically no overflow

scattered nodes

Pick array-based when: you know roughly how many items you'll have, or you want the simplest possible implementation.

Pick linked-list-based when: you have no idea how many items you'll need and don't want to deal with resizing.

In practice, most real-world stack implementations (including the ones in programming language standard libraries) use dynamic arrays. They're fast and handle resizing automatically.

A Clean Stack Wrapper

Here's a nice pattern — wrap whichever implementation you choose so the user only sees the clean stack interface:

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
structure Stack:
    storage = new ArrayStack()   // swap to LinkedStack() if needed
​
    function push(value):
        storage.push(value)
​
    function pop():
        return storage.pop()
​
    function peek():
        return storage.peek()
​
    function isEmpty():
        return storage.isEmpty()
​
    function size():
        return storage.size()

The user just calls push and pop. They never need to know what's underneath.

Examples

Example 1: Array-Based — Push Until Full

pseudocode
1
2
3
4
5
stack = new ArrayStack(capacity=3)
push(stack, 10)    // top=0, array=[10, _, _]
push(stack, 20)    // top=1, array=[10, 20, _]
push(stack, 30)    // top=2, array=[10, 20, 30]
push(stack, 40)    // ERROR: Stack is full!

Example 2: Linked List — No Limit

pseudocode
1
2
3
4
5
6
stack = new LinkedStack()
push(stack, 10)    // [10|null]
push(stack, 20)    // [20|*]->[10|null]
push(stack, 30)    // [30|*]->[20|*]->[10|null]
push(stack, 40)    // [40|*]->[30|*]->[20|*]->[10|null]
// Keep going as long as you like

Example 3: Reversing an Array

pseudocode
1
2
3
4
5
6
function reverseArray(arr):
    stack = new Stack()
    for each element in arr:
        stack.push(element)
    for i from 0 to length(arr) - 1:
        arr[i] = stack.pop()

Input: [1, 2, 3, 4]. Push all four, then pop — out comes [4, 3, 2, 1].

Common Mistakes

1. Off-by-one with the top index. When top starts at -1, the first push goes to index 0 (top + 1 = 0). When top starts at 0, you need different logic. Pick one convention and stick with it.

2. Not checking for full (array) or empty (both). Every push should check if the array is full. Every pop and peek should check if the stack is empty.

3. Forgetting to update top or count. After push, increment. After pop, decrement. If you forget, size() and isEmpty() give wrong answers.

4. Returning the wrong value on pop. Save the value BEFORE moving the index. value = array[top]; top--; return value is correct. top--; return array[top] returns the wrong element.

Best Practices

Start with the array-based version. It's simpler to write and understand. Only switch to a linked list if you genuinely need unlimited growth.

Use -1 to mean empty. The convention top == -1 means the stack is empty is the most common and least confusing.

Always test the edges. Push onto a full stack. Pop from an empty stack. Push then immediately pop. Single-element operations. These are the cases most likely to break.

Track size properly. Whether it's top + 1 for array or a count variable for linked list, always know how many items are in the stack.

Runnable Code

Here is a complete JavaScript stack implementation you can run. It includes push, pop, peek, isEmpty, and size operations.

js
Stack — Full Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Stack {
  constructor() {
    this.items = [];
  }
​
  push(item) {
    this.items.push(item);
  }
​
  pop() {
    if (this.isEmpty()) return 'Stack is empty';
    return this.items.pop();
  }
​
  peek() {
    if (this.isEmpty()) return 'Stack is empty';
    return this.items[this.items.length - 1];
  }
​
  isEmpty() {
    return this.items.length === 0;
  }
​
  size() {
    return this.items.length;
  }
​
  print() {
    console.log('Stack (top -> bottom):', [...this.items].reverse().join(', '));
  }
}
​
// --- Demo ---
const stack = new Stack();
​
stack.push(10);
stack.push(20);
stack.push(30);
console.log('After push 10, 20, 30:');
stack.print();
​
console.log('Peek:', stack.peek());
console.log('Pop:', stack.pop());
console.log('Pop:', stack.pop());
console.log('After two pops:');
stack.print();
console.log('Size:', stack.size());
console.log('isEmpty:', stack.isEmpty());
​
// Reverse an array using a stack
console.log('\n--- Reverse Array ---');
const arr = [1, 2, 3, 4, 5];
console.log('Original:', arr.join(', '));
const s = new Stack();
for (const val of arr) s.push(val);
const reversed = [];
while (!s.isEmpty()) reversed.push(s.pop());
console.log('Reversed:', reversed.join(', '));
How Stacks WorkStack Applications