Stack LIFO Principle Explained

The LIFO Principle

A stack is an abstract data type that follows the Last In, First Out (LIFO) principle. The most recently added element is the first to be removed, just like a stack of plates where you always take from the top.

Core Operations

Operation	Description	Time Complexity
push(x)	Add element x to the top	O(1)
pop()	Remove and return the top element	O(1)
peek()	View the top element without removing	O(1)
isEmpty()	Check if the stack is empty	O(1)

How LIFO Works

Consider pushing elements 1, 2, 3 onto a stack:

push(1): [1]         <- 1 is at top
push(2): [1, 2]      <- 2 is at top
push(3): [1, 2, 3]   <- 3 is at top
pop():   [1, 2]      <- 3 removed (last in, first out)
pop():   [1]         <- 2 removed

The key insight is that elements cannot be accessed out of order. You must pop 3 before you can access 2, and pop 2 before you can access 1. This constraint is what makes stacks useful for tracking nested or recursive contexts.

Array vs Linked List Implementation

Stacks can be implemented using either an array or a linked list:

• Array-based: Uses a variable top to track the index of the top element. Push increments top and assigns; pop reads and decrements. Amortized O(1) because array resizing is infrequent.
• Linked list-based: Each node points to the one below it. Push prepends a new head; pop removes the head. Always O(1) with no resizing needed, but each node carries pointer overhead.

Overflow and Underflow

• Stack overflow: Pushing onto a full fixed-size stack. In languages with bounded stacks (like the call stack), this causes a crash.
• Stack underflow: Popping from an empty stack. Implementations should throw an error or return a sentinel value.