8.4 Stack

A stack is a linear data structure that follows:

LIFO — Last In, First Out

This means the last item added is the first item removed.

Think of a stack of plates:

        ┌─────┐
top  →  │  C  │  ← added last, removed first
        ├─────┤
        │  B  │
        ├─────┤
        │  A  │  ← added first, removed last
        └─────┘

You may only add or remove items from one end, called the top. You cannot directly remove A while B and C are above it. 8.DataStructures.pdfPDF

1. What makes a stack different from a normal list?

A Python list allows many operations:

numbers = [10, 20, 30]
 
numbers.append(40)
numbers.insert(1, 15)
numbers.pop()
numbers.pop(0)
numbers[1] = 99

However, a proper stack deliberately restricts what you can do.

You should normally only use:

push    Add at the top
pop     Remove from the top
peek    Examine the top

This restriction is important because a stack is an Abstract Data Type, or ADT.

An ADT describes:

what operations are allowed;
what each operation does;
not necessarily how the data is internally stored.

Therefore, both an array and a linked list can implement a stack, as long as they behave according to LIFO.

2. Main stack operations

Suppose we begin with an empty stack:

top
 ↓
empty

2.1 `push(newItem)`

push adds a new item to the top.

push("A")

Result:

top → A

Then:

push("B")

Result:

top → B
      A

Then:

push("C")

Result:

top → C
      B
      A

The most recently added item is always at the top.

2.2 `pop()`

pop does two things:

removes the top item;
returns that item.

Starting stack:

top → C
      B
      A

After:

item = stack.pop()

C is removed and stored in item.

item = "C"

top → B
      A

A common mistake is thinking that pop() only deletes the item.

It also returns it:

removed_item = stack.pop()
print(removed_item)

2.3 `peek()`

peek returns the top item without removing it.

Starting stack:

top → C
      B
      A

After:

item = stack.peek()

The result is:

item = "C"

But the stack remains:

top → C
      B
      A

`pop` versus `peek`

Operation	Returns top item?	Removes top item?
`pop()`	Yes	Yes
`peek()`	Yes	No

A simple way to remember:

Peek means look. Pop means take.

2.4 `isEmpty()`

This checks whether the stack contains no items.

stack.isEmpty()

It returns:

True

when the stack is empty, and:

False

when the stack contains at least one item.

This is especially important before calling pop() or peek().

2.5 `len(stack)`

This returns the number of items currently in the stack.

top → C
      B
      A

Therefore:

len(stack)

returns:

2.6 `str(stack)`

This produces a string representation of the stack.

For example:

print(stack)

might produce:

A B C

The notes display the items from the bottom to the top, so C is the final item shown.

3. Tracing stack operations

Suppose the following instructions are executed:

stack.push("A")
stack.push("B")
stack.push("C")
x = stack.pop()
stack.push("D")
y = stack.peek()

Let us trace them carefully.

Step 1

stack.push("A")

top → A

Step 2

stack.push("B")

top → B
      A

Step 3

stack.push("C")

top → C
      B
      A

Step 4

x = stack.pop()

C is removed:

x = "C"

top → B
      A

Step 5

stack.push("D")

top → D
      B
      A

Step 6

y = stack.peek()

D is returned but not removed:

y = "D"

top → D
      B
      A

Final results:

x = "C"
y = "D"
stack contains A, B, D

When tracing a stack question, always draw the stack vertically and mark the top.

4. Stack overflow and underflow

Stack underflow

Underflow occurs when the program tries to remove or examine an item from an empty stack.

For example:

stack = ArrayStack()
stack.pop()

There is nothing to remove.

Likewise:

stack.peek()

cannot return a top item because no top item exists.

The code checks:

if self.isEmpty():

before attempting the operation.

Stack overflow

Overflow occurs when the program tries to push an item into a fixed-size stack that is already full.

Suppose the stack capacity is 3:

top → C
      B
      A

Calling:

stack.push("D")

causes overflow because there are already three items.

This mainly applies to an array-based stack, because its physical capacity is fixed.

A linked stack can grow dynamically until the computer runs out of available memory.

5. Implementing a stack using a Python list

Python does not have a separate built-in stack type, but a list can imitate one:

stack = []
 
stack.append("A")   # push
stack.append("B")   # push
stack.append("C")   # push
 
print(stack[-1])    # peek
print(stack.pop())  # pop

Output:

C
C

The final list is:

["A", "B"]

The end of the list acts as the top:

["A", "B", "C"]
             ↑
            top

However, your notes later implement a proper stack class so that users cannot freely perform inappropriate list operations. 8.DataStructures.pdfPDF

6. Array-based stack

Your notes provide an ArrayStack class.

Here is the basic structure:

class ArrayStack:
    DEFAULT_CAPACITY = 12
 
    def __init__(self):
        self._items = [""] * ArrayStack.DEFAULT_CAPACITY
        self._top = -1
        self._size = 0

There are three important attributes:

Attribute	Purpose
`_items`	The array that stores the items
`_top`	Index of the current top item
`_size`	Number of items currently stored

6.1 Understanding `_items`

self._items = [""] * 12

This creates an array with 12 empty positions:

Index:    0   1   2   3   4   5   ... 11
Items:   [""][""][""][""][""][""] ... [""]

The physical size is 12.

However, when the stack is first created, it contains zero actual items, so its logical size is 0.

6.2 Why does `_top` begin at `-1`?

Initially:

self._top = -1

This means there is currently no valid top index.

Array indices begin at 0:

0, 1, 2, 3, ...

Therefore, -1 is used to represent:

There is currently no item in the stack.

After the first push:

self._top += 1

so:

-1 becomes 0

The first item is placed at index 0.

6.3 Why do we need both `_top` and `_size`?

They contain related but different information.

Suppose there are three items:

Index:   0    1    2
Item:    A    B    C
                   ↑
                  top

Then:

self._top = 2
self._size = 3

The relationship is:

top index = size − 1

However, the program uses:

_top to access the top item directly;
_size to determine how many items exist and whether the stack is full.

7. Understanding the `push` code

def push(self, newItem):
    if self._size == ArrayStack.DEFAULT_CAPACITY:
        print("Stack is full. Abort operation!!")
    else:
        self._top += 1
        self._size += 1
        self._items[self._top] = newItem

Let us examine every part.

Step 1: Check whether the stack is full

if self._size == ArrayStack.DEFAULT_CAPACITY:

For example:

_size = 12
capacity = 12

There is no free space.

The new item cannot be inserted.

Step 2: Move the top upwards

self._top += 1

Suppose:

_top = 1

After incrementing:

_top = 2

The new item will be stored at index 2.

Step 3: Increase the logical size

self._size += 1

If the stack previously contained two items, it now contains three.

Step 4: Store the new item

self._items[self._top] = newItem

Example:

stack.push("C")

Before:

Index:  0    1    2    3
Item:   A    B   ""   ""
             ↑
            top

After increasing _top and storing C:

Index:  0    1    2    3
Item:   A    B    C   ""
                  ↑
                 top

The notes use exactly this approach: increase _top, increase _size, and store the item at the new top index. 8.DataStructures.pdfPDF

8. Understanding the `pop` code

def pop(self):
    if self.isEmpty():
        print("Stack is empty. Abort operation!!")
        return ""
    else:
        oldItem = self._items[self._top]
        self._top -= 1
        self._size -= 1
        return oldItem

Step 1: Check whether the stack is empty

if self.isEmpty():

This prevents underflow.

Step 2: Save the top item

oldItem = self._items[self._top]

Suppose:

Index:  0    1    2
Item:   A    B    C
                  ↑
                 top

Then:

oldItem = "C"

The item must be saved before _top changes.

Step 3: Move the top down

self._top -= 1

_top changes from 2 to 1

Logically, B is now at the top.

Step 4: Decrease the size

self._size -= 1

The stack now contains two items.

Step 5: Return the removed item

return oldItem

So the caller receives "C".

Does the code erase `"C"` from the array?

Not necessarily.

After popping, the internal array may still physically look like:

Index:  0    1    2
Item:   A    B    C
             ↑
            top

Although "C" remains in the memory cell, it is no longer considered part of the stack because:

_top = 1
_size = 2

The logical stack is only:

A, B

The old cell will be overwritten during a later push.

This distinction between physical contents and logical contents is important.

9. Understanding the `peek` code

def peek(self):
    if self.isEmpty():
        print("Stack is empty. Abort operation!!")
        return ""
    else:
        return self._items[self._top]

Unlike pop(), it does not change:

self._top
self._size

It simply returns:

self._items[self._top]

Therefore, the stack remains unchanged.

10. Understanding `len`

def __len__(self):
    return self._size

The special method __len__ allows this:

len(stack)

instead of needing:

stack.get_size()

For example:

stack.push("A")
stack.push("B")

print(len(stack))

Output:

11. Understanding `isEmpty`

def isEmpty(self):
    return len(self) == 0

This calls:

len(self)

which uses:

__len__()

Therefore, it is effectively checking:

return self._size == 0

Both versions mean the same thing.

12. Understanding `str`

def __str__(self):
    result = ""
 
    for i in range(len(self)):
        result += str(self._items[i]) + " "
 
    return result

Suppose the stack contains:

A, B, C

Then:

print(stack)

calls stack.__str__() and prints:

A B C

The loop only visits:

range(len(self))

Therefore, it does not print unused array cells.

For a size of 3:

range(3)

produces:

0, 1, 2

13. Complete `ArrayStack` with comments

class ArrayStack:
    """Array-based stack implementation."""
 
    DEFAULT_CAPACITY = 12
 
    def __init__(self):
        # Create an array with 12 empty cells
        self._items = [""] * ArrayStack.DEFAULT_CAPACITY
 
        # -1 means that the stack currently has no top item
        self._top = -1
 
        # Number of items currently in the stack
        self._size = 0
 
    def push(self, newItem):
        """Add newItem to the top of the stack."""
 
        # Check for stack overflow
        if self._size == ArrayStack.DEFAULT_CAPACITY:
            print("Stack is full. Abort operation!!")
 
        else:
            # Move top to the next free position
            self._top += 1
 
            # Increase the number of stored items
            self._size += 1
 
            # Store the new item at the top
            self._items[self._top] = newItem
 
    def pop(self):
        """Remove and return the top item."""
 
        # Check for stack underflow
        if self.isEmpty():
            print("Stack is empty. Abort operation!!")
            return ""
 
        else:
            # Save the item before changing the top
            oldItem = self._items[self._top]
 
            # Move top down by one position
            self._top -= 1
 
            # Reduce the number of items
            self._size -= 1
 
            # Return the removed item
            return oldItem
 
    def peek(self):
        """Return the top item without removing it."""
 
        if self.isEmpty():
            print("Stack is empty. Abort operation!!")
            return ""
 
        else:
            return self._items[self._top]
 
    def __len__(self):
        """Return the number of items in the stack."""
        return self._size
 
    def isEmpty(self):
        """Return True when the stack has no items."""
        return len(self) == 0
 
    def __str__(self):
        """Return the items from bottom to top."""
        result = ""
 
        for i in range(len(self)):
            result += str(self._items[i]) + " "
 
        return result

This is the array implementation given in your notes. 8.DataStructures.pdfPDF

14. Example of using `ArrayStack`

stack = ArrayStack()
 
stack.push("A")
stack.push("B")
stack.push("C")
 
print(stack)          # A B C
print(stack.peek())   # C
print(stack.pop())    # C
print(stack)          # A B
print(len(stack))     # 2

Notice:

stack.push("A")

means:

Ask the stack object to place "A" at its top.

You do not call:

ArrayStack.push("A")

because push operates on a particular stack object.

15. Application: checking matching brackets

Stacks are useful when brackets must close in the reverse order in which they opened.

Consider:

[()]

The opening brackets appear in this order:

[
(

They must close in the reverse order:

)
]

That is exactly LIFO.

Example 1: Balanced brackets

Expression:

[(A+B)]

Scan from left to right.

Read `[`

Push it:

top → [

Read `(`

Push it:

top → (
      [

Read `)`

Pop (.

They match:

top → [

Read `]`

Pop [.

They match:

empty

At the end, the stack is empty, so the brackets are balanced.

Example 2: Incorrect bracket types

Expression:

[(])

Push [:

top → [

Push (:

top → (
      [

Then read ].

The top is (, but ] should match [. Therefore, the expression is invalid.

Example 3: Closing bracket without opening bracket

Expression:

A+B)

When ) is encountered, the stack is empty.

There is no earlier ( to match it.

Therefore, it is invalid.

Example 4: Opening bracket never closed

Expression:

[(A+B)

The ( is matched and removed, but [ remains in the stack at the end.

Therefore, the expression is invalid.

Bracket-checking code

def bracketsBalance(exp):
    stk = ArrayStack()
 
    for ch in exp:
 
        # Opening brackets are placed on the stack
        if ch in ["[", "("]:
            stk.push(ch)
 
        # Process closing brackets
        elif ch in ["]", ")"]:
 
            # Closing bracket appeared without an opening bracket
            if stk.isEmpty():
                return False
 
            opening = stk.pop()
 
            # Check whether bracket types match
            if (ch == "]" and opening != "[") or \
               (ch == ")" and opening != "("):
                return False
 
    # Any unmatched opening bracket makes it invalid
    return stk.isEmpty()

The final line is important:

return stk.isEmpty()

It checks whether any unmatched opening brackets remain. Your notes use this stack application in Section 8.4.2. 8.DataStructures.pdfPDF

16. Linked-stack implementation

A stack can also be implemented using a linked structure.

Instead of an array and a top index, it uses:

_top → first node

Example:

_top
  ↓
[C | •] → [B | •] → [A | None]

Here:

C is at the top;
A is at the bottom;
every node stores data and a pointer to the next node.

The linked implementation normally uses:

self._top
self._size

where:

_top points to the first node;
_size stores the number of nodes.

Pushing and popping happen at the head of the linked structure. 8.DataStructures.pdfPDF

17. Pushing onto a linked stack

Starting stack:

_top
  ↓
[C | •] → [B | •] → [A | None]

Suppose we push D.

Step 1: Create the new node

[D | None]

Step 2: Point the new node to the old top

[D | •] ─────────┐
                 ↓
               [C | •] → [B | •] → [A | None]

In code:

newNode.next = self._top

Step 3: Move `_top` to the new node

_top
  ↓
[D | •] → [C | •] → [B | •] → [A | None]

In code:

self._top = newNode

These two linking steps can be combined:

self._top = Node(newItem, self._top)

This means:

create a node containing newItem;
make its next point to the current top;
make it the new top.

18. Popping from a linked stack

Starting stack:

_top
  ↓
[D | •] → [C | •] → [B | •] → [A | None]

Step 1: Save the top item

oldItem = self._top.data

So:

oldItem = "D"

Step 2: Move `_top` to the next node

self._top = self._top.next

Result:

_top
  ↓
[C | •] → [B | •] → [A | None]

The old D node is no longer part of the stack.

Step 3: Decrease the size

self._size -= 1

Step 4: Return the item

return oldItem

19. Complete linked-stack structure

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
 
 
class LinkedStack:
    def __init__(self):
        # Top points to the first node
        self._top = None
 
        # Number of nodes in the stack
        self._size = 0
 
    def push(self, newItem):
        # New node points to the old top
        # Then it becomes the new top
        self._top = Node(newItem, self._top)
 
        self._size += 1
 
    def pop(self):
        if self.isEmpty():
            print("Stack is empty. Abort operation!!")
            return ""
 
        # Save the top data
        oldItem = self._top.data
 
        # Remove the first node by moving top
        self._top = self._top.next
 
        self._size -= 1
 
        return oldItem
 
    def peek(self):
        if self.isEmpty():
            print("Stack is empty. Abort operation!!")
            return ""
 
        return self._top.data
 
    def __len__(self):
        return self._size
 
    def isEmpty(self):
        return self._size == 0

20. Array stack versus linked stack

Feature	Array stack	Linked stack
Storage	Contiguous array	Linked nodes
Capacity	Usually fixed	Dynamic
Top represented by	Index `_top`	Pointer `_top`
Push	Increase index and store	Add node at head
Pop	Decrease index	Remove head node
Overflow	When array is full	Only when memory is exhausted
Extra pointer storage	No	Every node stores `next`

Both still follow LIFO and provide the same stack interface.

21. Why push and pop are fast

For both implementations, push and pop happen directly at the top.

There is:

no traversal;
no searching;
no shifting of all the other items.

Therefore, both operations have constant time complexity:

push: O(1)
pop:  O(1)
peek: O(1)

You probably do not need to focus heavily on complexity yet, but the key idea is:

The amount of work does not increase when the stack becomes larger.

22. Common exam mistakes

Mistake 1: Removing from the bottom

A stack only removes from the top.

Wrong: remove A first
Correct: remove C first

Mistake 2: Treating `peek` like `pop`

peek() must not change _top or _size.

Mistake 3: Forgetting to return the popped item

Incorrect:

def pop(self):
    self._top -= 1

Correct:

oldItem = self._items[self._top]
self._top -= 1
self._size -= 1
return oldItem

Mistake 4: Changing `_top` before saving the item

Incorrect:

self._top -= 1
oldItem = self._items[self._top]

This returns the item underneath the original top.

Correct:

oldItem = self._items[self._top]
self._top -= 1

Save first, move second.

Mistake 5: Forgetting underflow checks

Before pop() or peek():

if self.isEmpty():

must be checked.

Mistake 6: Confusing `_top` and `_size`

For three items:

_size = 3
_top = 2

because indexing starts at zero.

23. What you should remember

STACK = LIFO
Only one accessible end: TOP

Core operations:

push(item)  → add to top
pop()       → remove and return top
peek()      → return top without removing
isEmpty()   → check whether stack is empty
len(stack)  → number of items

Array stack:

push:
1. Check full
2. top += 1
3. size += 1
4. items[top] = newItem

pop:
1. Check empty
2. Save items[top]
3. top -= 1
4. size -= 1
5. Return saved item

Linked stack:

push:
new node points to old top
top points to new node

pop:
save top data
top moves to top.next
return saved data

The single most important idea is:

Everything happens at the top.

Quartz 5

Explorer

8. Data Structure (8.4)

8.4 Stack

1. What makes a stack different from a normal list?

2. Main stack operations

2.1 push(newItem)

2.2 pop()

2.3 peek()

pop versus peek

2.4 isEmpty()

2.5 len(stack)

2.6 str(stack)

3. Tracing stack operations

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

4. Stack overflow and underflow

Stack underflow

Stack overflow

5. Implementing a stack using a Python list

6. Array-based stack

6.1 Understanding _items

6.2 Why does _top begin at -1?

6.3 Why do we need both _top and _size?

7. Understanding the push code

Step 1: Check whether the stack is full

Step 2: Move the top upwards

Step 3: Increase the logical size

Step 4: Store the new item

8. Understanding the pop code

Step 1: Check whether the stack is empty

Step 2: Save the top item

Step 3: Move the top down

Step 4: Decrease the size

Step 5: Return the removed item

Does the code erase "C" from the array?

9. Understanding the peek code

10. Understanding __len__

11. Understanding isEmpty

12. Understanding __str__

13. Complete ArrayStack with comments

14. Example of using ArrayStack

15. Application: checking matching brackets

Example 1: Balanced brackets

Read [

Read (

Read )

Read ]

Example 2: Incorrect bracket types

Example 3: Closing bracket without opening bracket

Example 4: Opening bracket never closed

Bracket-checking code

16. Linked-stack implementation

17. Pushing onto a linked stack

Step 1: Create the new node

Step 2: Point the new node to the old top

Step 3: Move _top to the new node

18. Popping from a linked stack

Step 1: Save the top item

Step 2: Move _top to the next node

Step 3: Decrease the size

Step 4: Return the item

19. Complete linked-stack structure

20. Array stack versus linked stack

21. Why push and pop are fast

22. Common exam mistakes

Mistake 1: Removing from the bottom

Mistake 2: Treating peek like pop

Mistake 3: Forgetting to return the popped item

Mistake 4: Changing _top before saving the item

Mistake 5: Forgetting underflow checks

Mistake 6: Confusing _top and _size

23. What you should remember

Graph View

Table of Contents

2.1 `push(newItem)`

2.2 `pop()`

2.3 `peek()`

`pop` versus `peek`

2.4 `isEmpty()`

2.5 `len(stack)`

2.6 `str(stack)`

6.1 Understanding `_items`

6.2 Why does `_top` begin at `-1`?

6.3 Why do we need both `_top` and `_size`?

7. Understanding the `push` code

8. Understanding the `pop` code

Does the code erase `"C"` from the array?

9. Understanding the `peek` code

10. Understanding `len`

11. Understanding `isEmpty`

12. Understanding `str`

13. Complete `ArrayStack` with comments

14. Example of using `ArrayStack`

Read `[`

Read `(`

Read `)`

Read `]`

Step 3: Move `_top` to the new node

Step 2: Move `_top` to the next node

Mistake 2: Treating `peek` like `pop`

Mistake 4: Changing `_top` before saving the item

Mistake 6: Confusing `_top` and `_size`