A Stack is a linear data structure in which insertion and deletion are performed from one end called the top. It follows the Last In, First Out (LIFO) principle: the element added most recently is the first element removed.
The restricted access provided by a stack is useful when a program needs to process the most recent item before older items. Stacks are important in function calls, recursion, expression processing, syntax checking, backtracking, undo operations, and navigation systems.
A stack can be viewed as a sequence of elements with access concentrated at one end. If the elements are inserted in the order 10, 20 and 30, then 30 is at the top and will be removed first.
TOP ↓ 30 20 10
The two fundamental operations are push, which adds an element to the top, and pop, which removes the top element. A peek operation can be used when the program needs to inspect the top element without removing it.
LIFO is useful when the newest unfinished task must be handled before an older task. For example, nested function calls return in reverse order: the most recently called function must finish before control returns to the earlier call.
Consider these operations:
push(10)
push(20)
push(30)
Stack:
TOP → 30
20
10
pop() → 30
After the pop operation, 20 becomes the new top. This simple rule is the key idea behind every stack implementation.
| Term | Meaning |
|---|---|
| Top | Identifies the element currently available at the top of the stack. |
| Push | Adds a new element to the top. |
| Pop | Removes and normally returns the top element. |
| Peek | Reads the top element without removing it. |
| IsEmpty | Checks whether the stack contains no elements. |
| IsFull | For a fixed-capacity implementation, checks whether no more elements can be inserted. |
| Overflow | An insertion attempt fails because a fixed-capacity stack is full. |
| Underflow | A removal attempt fails because the stack is empty. |
The behavior of a stack is mainly defined by its operations. Although the implementation may use an array or linked list, the logical behavior remains the same.
Push inserts a new value at the top. In an array-based stack, the top index is increased before storing the new value.
Before:
TOP → 30
20
10
push(40)
After:
TOP → 40
30
20
10
For a correctly maintained top position, push takes O(1) time.
Pop removes the element currently at the top. The top position is then moved to the previous element.
Before:
TOP → 40
30
20
10
pop() → 40
After:
TOP → 30
20
10
Pop takes O(1) time because it works only with the top element.
Peek returns or displays the top value without changing the stack.
TOP → 40
30
20
peek() → 40
Stack remains unchanged.
Peek is also an O(1) operation.
IsEmpty checks whether the stack has no elements. In an array implementation using top = -1 for an empty stack, the condition is:
top == -1
IsFull is relevant to a fixed-capacity array stack. If the maximum valid index is MAX - 1, the stack is full when:
top == MAX - 1
Overflow is a capacity-related condition. In a fixed-size array stack, it occurs when a push is requested while every available position is already occupied.
Maximum capacity = 3
TOP → 30
20
10
push(40)
→ Stack Overflow
A dynamically allocated or linked-list implementation does not have the same fixed-capacity boundary, although insertion can still fail if the system cannot provide the required memory.
Underflow occurs when pop or another removal operation is requested while the stack is empty.
Stack = empty pop() → Stack Underflow
Checking the empty condition before removing an element prevents invalid access.
An array is a straightforward way to implement a stack when its maximum capacity is known or intentionally bounded. The array stores the values, while an integer top identifies the current top position.
#define MAX 100 int stack[MAX]; int top = -1;
When top is -1, the stack contains no elements. The first push changes it to 0 and stores the value at stack[0].
void push(int value)
{
if (top == MAX - 1)
{
printf("Stack Overflow");
return;
}
stack[++top] = value;
}
The overflow check is performed before changing top. This prevents writing outside the allocated array.
int pop()
{
if (top == -1)
{
printf("Stack Underflow");
return -1;
}
return stack[top--];
}
The function returns the current top value and then decreases the top index. In production code, returning a separate status value is often preferable when every possible data value, including -1, is valid.
int peek()
{
if (top == -1)
{
printf("Stack is empty");
return -1;
}
return stack[top];
}
Unlike pop, peek does not modify top.
A stack can also be implemented with a linked list. In this design, the first node acts as the top of the stack. A push creates a new node at the beginning, while a pop removes the first node.
TOP ↓ [30 | next] → [20 | next] → [10 | NULL]
struct Node
{
int data;
struct Node *next;
};
A linked-list stack does not require a fixed array capacity. Its practical limit is the memory available to the program. It also requires additional memory for the pointer stored in each node.
| Feature | Array Stack | Linked List Stack |
|---|---|---|
| Capacity | Usually fixed | Grows as nodes are allocated |
| Memory layout | Contiguous array storage | Separate dynamically allocated nodes |
| Extra pointer memory | Not required per element | Required for each node |
| Push / Pop | O(1) | O(1) when operating at the head |
| Operation | Typical Time Complexity | Reason |
|---|---|---|
| Push | O(1) | Works at the top position. |
| Pop | O(1) | Removes the top element. |
| Peek | O(1) | Reads the top element directly. |
| IsEmpty | O(1) | Checks the maintained top state. |
| IsFull | O(1) | Checks capacity in a fixed-size implementation. |
These complexities assume that the implementation maintains direct access to the top. A stack does not normally provide an efficient operation for searching an arbitrary element; finding a value may require examining elements one by one.
When a function calls another function, the program needs to preserve information such as the return location and execution state. A call stack organizes these nested calls so that the most recent call can complete first.
Each active recursive call needs its own execution state. These states are maintained in stack frames and are removed as calls return.
Stacks are useful for processing operators and operands in expression-conversion and evaluation algorithms. They are commonly associated with infix, postfix, and prefix expression processing.
A parser can push opening brackets and match them when closing brackets appear. If the closing bracket does not match the most recent opening bracket, the expression is not balanced.
Applications can maintain previous states or actions in stack-like structures. Undo removes the most recent action, while a second structure can be used to support redo.
Backtracking problems need a way to return to earlier decisions. A stack can store states or choices so that the latest decision can be revisited first.
Stack-like behavior is useful when software needs to return from the current state to the immediately previous state, such as nested menus or certain navigation models.
Consider the following factorial function:
int factorial(int n)
{
if (n == 0)
return 1;
return n * factorial(n - 1);
}
For factorial(3), calls are made in this order:
factorial(3)
↓
factorial(2)
↓
factorial(1)
↓
factorial(0)
The calls remain active until the base case is reached. Returning from the most recent call before the earlier calls is consistent with LIFO behavior.
A stack provides a simple way to check whether brackets are properly nested. When an opening bracket such as (, [, or { is encountered, it is pushed. When a closing bracket appears, the top opening bracket is checked.
Input:
{ [ ( ) ] }
Processing:
{ → push
[ → push
( → push
) → match and pop
] → match and pop
} → match and pop
Stack becomes empty
Result: Balanced
The same idea can be extended to programming languages and syntax-processing tools where nested delimiters must be validated.
Stacks are central to several classical expression algorithms. For example, postfix expressions can be evaluated by pushing operands and applying an operator to the most recently available operands.
Expression: 2 3 + 4 * Step 1: Push 2 Step 2: Push 3 Step 3: + → 2 + 3 = 5 Step 4: Push 4 Step 5: * → 5 * 4 = 20 Result = 20
This example demonstrates why LIFO access is useful: an operator can retrieve the operands that were most recently placed on the stack.
| Feature | Stack | Queue |
|---|---|---|
| Principle | LIFO | FIFO |
| Insertion | At the top | At the rear |
| Deletion | From the top | From the front |
| Main pointers | Top | Front and Rear |
| Typical use | Recursion, backtracking, undo | Scheduling, buffering, sequential processing |
An array is a storage structure that normally allows indexed access to its elements, whereas a stack is an abstract data structure that restricts access to the top according to LIFO. An array can therefore be used to implement a stack, but an array and a stack are not the same concept.
| Feature | Array | Stack |
|---|---|---|
| Access | Index-based access is available. | Normal operations use the top. |
| Ordering rule | No inherent LIFO rule. | Follows LIFO. |
| Typical operations | Read or update by index. | Push, pop and peek. |
| Implementation relationship | Can be used as storage for a stack. | Can be implemented using an array. |
A stack follows Last In, First Out (LIFO), so the most recently inserted element is removed first.
Push inserts an element, pop removes the top element, and peek reads the top element without removing it. IsEmpty and IsFull are commonly used for state checks.
Both operations work directly with the top of the stack, so they do not normally require traversal through all elements.
Overflow is an insertion failure caused by a full fixed-capacity stack, while underflow is a removal failure caused by an empty stack.
Yes. An array can store the elements and a top index can identify the current top position.
Yes. A linked-list stack normally uses the first node as the top, allowing push and pop at the beginning in O(1) time.
Active recursive calls require stack frames. The most recent call returns before the earlier calls, which follows LIFO behavior.
Opening brackets can be pushed and the most recent opening bracket can be checked when a closing bracket is encountered. This handles nested brackets naturally.
A stack removes the most recently inserted element (LIFO), whereas a queue normally removes the earliest inserted element (FIFO).
Stack is a fundamental linear data structure built around the LIFO access rule. Its restricted top-based access makes push, pop and peek simple and efficient, while also making the structure suitable for problems involving nested or reverse-order processing.
Understanding both array-based and linked-list implementations gives students a practical view of how a stack is stored in memory. The same concept appears in recursion, function-call management, expression processing, balanced-bracket checking, backtracking and undo-style operations.
For Data Structures and Algorithms, mastering the stack means understanding not only its definition, but also its operations, boundary conditions, implementation choices, complexity and practical use cases.