A stack is one of the simplest and most useful data structures. Think of a pile of plates: you add to the top and take from the top. This lesson explains the stack’s rules and shows how to implement it.

LIFO

A stack follows LIFO: Last In, First Out. The most recently added item is the first removed. Only the top is accessible.

Operations

  • push(item): add an item to the top.
  • pop(): remove and return the top item.
  • peek(): return the top item without removing it.
  • isEmpty(): true if the stack has no items.
  • isFull(): true if a fixed-size stack has no room (array-based).

Example sequence:

push(5)      // [5]
push(8)      // [5, 8]
push(2)      // [5, 8, 2]   top is 2
pop()        // returns 2, stack is [5, 8]
peek()       // returns 8, stack unchanged

Trying to pop from an empty stack causes stack underflow. Pushing onto a full stack causes stack overflow.

Array implementation

Keep an array and a variable top that stores the index of the top item (start at -1 when empty).

STACK = new array[10]
top = -1

PROCEDURE push(item)
   if top = 9 then
      output "Stack overflow"
   else
      top = top + 1
      STACK[top] = item
   end if
END PROCEDURE

FUNCTION pop()
   if top = -1 then
      output "Stack underflow"
   else
      item = STACK[top]
      top = top - 1
      return item
   end if
END FUNCTION

FUNCTION peek()
   return STACK[top]
END FUNCTION

Note that pop only moves top down; the old value still sits in the array but is ignored and will be overwritten.

Linked-list implementation

Use a linked list where the head is the top. Push inserts at the head and pop removes the head. Both are O(1), and the stack can grow without a fixed limit.

Complexity

All the main operations (push, pop, peek, isEmpty) are O(1). That is a major reason stacks are popular.

Everyday analogy

Pressing the back button in a browser steps back through pages in reverse order of visiting, which is stack behaviour. Undo in a text editor works the same way.

Check your understanding

What does LIFO stand for?

  • Last In, First Out
  • Last In, First Over
  • Linear In, Fixed Out
  • Least In, First Out

Answer: Last In, First Out. The newest item leaves first.

Starting with an empty stack, after push(1), push(2), push(3), pop(), what does peek() return?

  • 1
  • 2
  • 3
  • Nothing

Answer: 2. The 3 was removed, leaving 2 on top.

What is stack underflow?

  • Popping from an empty stack
  • Pushing onto a full stack
  • Peeking twice
  • Deleting the array

Answer: Popping from an empty stack. There is nothing to remove.

What is the complexity of push on an array-based stack?

  • O(1)
  • O(n)
  • O(log n)
  • O(n squared)

Answer: O(1). It only increments top and stores one value.