Stack is one of the most widely used linear data structures in computer science. It stores data in a specific order and follows a unique rule called Last In First Out (LIFO). According to this rule, the element inserted most recently is removed first.
Stacks are used in operating systems, compilers, memory management, web browsers, calculators, programming languages, and many real-world software applications. Understanding stacks helps students build a strong foundation for advanced data structures and algorithms.
Unlike arrays where elements can be accessed directly using indexes, a stack allows insertion and deletion from only one end known as the TOP. This restriction makes stack operations simple and efficient.
A Stack is a linear data structure in which insertion and deletion operations are performed from the same end. The insertion operation is called Push and the deletion operation is called Pop.
The stack follows the Last In First Out principle, meaning the newest element enters and leaves first.
A Stack is a linear data structure that follows the Last In First Out (LIFO) principle where insertion and deletion are performed only from the top position.
Understanding stacks becomes easier when we relate them to everyday situations.
In a restaurant, plates are placed one on top of another. The last plate placed on the stack is the first plate removed.
If books are stacked vertically, the book placed last will be removed first.
Modern web browsers use stacks to store visited pages. Pressing the back button takes users to the most recently visited page.
Many computing tasks require temporary storage where recently stored information must be processed before older information. Stacks provide an efficient mechanism for handling such requirements.
LIFO stands for Last In First Out. It means the last element inserted into the stack is the first element removed.
Push(10) Push(20) Push(30) Push(40)
Stack Representation:
TOP ↓ 40 30 20 10
If a Pop operation is performed, the value 40 will be removed first because it was inserted last.
| Term | Description |
|---|---|
| Stack | A linear data structure following LIFO. |
| TOP | Pointer to the topmost element. |
| Push | Operation used to insert data. |
| Pop | Operation used to remove data. |
| Peek | Displays the top element. |
| Overflow | Occurs when stack becomes full. |
| Underflow | Occurs when stack becomes empty. |
Stacks are usually represented vertically because all operations occur from the top.
TOP ↓ 50 40 30 20 10
The topmost element is always the first candidate for removal.
Several operations can be performed on a stack for managing stored elements.
Push is the operation used to insert a new element into the stack.
Every new element is added at the top position.
Before Push TOP ↓ 30 20 10 Push(40)
After Push:
TOP ↓ 40 30 20 10
Pop removes the topmost element from the stack.
Before Pop TOP ↓ 40 30 20 10
After Pop:
TOP ↓ 30 20 10
Removed Element = 40
Peek displays the top element without removing it from the stack.
Stack TOP ↓ 40 30 20 10 Peek() Output = 40
Stack Overflow occurs when an insertion operation is attempted on a full stack.
Maximum Size = 5 Current Elements = 5 Push(60) Result: Stack Overflow
Stack Underflow occurs when a deletion operation is attempted on an empty stack.
Stack Empty Pop() Result: Stack Underflow
| Stack | Array |
|---|---|
| Follows LIFO. | Does not follow LIFO. |
| Restricted access. | Direct index access. |
| Insertion at top. | Insertion anywhere. |
| Special-purpose structure. | General-purpose structure. |
One of the most common methods of implementing a stack is by using an array. In this approach, elements are stored in contiguous memory locations, and a variable called TOP keeps track of the last inserted element.
Array implementation is simple and suitable when the maximum stack size is known in advance.
#define MAX 100 int stack[MAX]; int top = -1;
Initially, the TOP value is set to -1, indicating that the stack is empty.
The push operation inserts a new element at the top of the stack.
void push(int value)
{
if(top == MAX-1)
{
printf("Stack Overflow");
}
else
{
top++;
stack[top] = value;
}
}
Before inserting a new element, the program checks whether the stack is already full.
The pop operation removes the topmost element from the stack.
int pop()
{
if(top == -1)
{
printf("Stack Underflow");
}
else
{
return stack[top--];
}
}
The removed value is returned and the TOP pointer is decreased by one position.
Stacks can also be implemented using linked lists. Unlike arrays, linked lists do not require a fixed size. Memory is allocated dynamically whenever a new element is inserted.
In a linked-list-based stack, insertion and deletion occur at the beginning of the list.
Most stack operations are highly efficient because they involve only the top element.
| Operation | Time Complexity |
|---|---|
| Push | O(1) |
| Pop | O(1) |
| Peek | O(1) |
| IsEmpty | O(1) |
| IsFull | O(1) |
Because stack operations require direct access to the top element only, they are extremely fast.
Stacks play an important role in many real-world software systems and algorithms.
Whenever a function is called, information such as local variables, parameters, and return addresses is stored in a stack. When the function completes execution, its data is removed from the stack.
Recursive functions depend heavily on stacks. Each recursive call creates a new stack frame, which is removed after execution.
Stacks are used to evaluate arithmetic and logical expressions efficiently.
Compilers use stacks to verify whether brackets and parentheses are balanced correctly.
The Back button in a browser uses a stack to store previously visited pages.
Text editors and design software use stacks to manage undo and redo actions.
Many problem-solving techniques use stacks to return to previous states when required.
Recursion is a programming technique where a function calls itself. Every recursive call is stored in the system stack until the base condition is reached.
factorial(3) factorial(2) factorial(1)
The stack stores each function call. Once the base condition is reached, execution returns in reverse order.
This behavior perfectly matches the Last In First Out principle.
Stacks are commonly used to evaluate arithmetic expressions.
For example:
(10 + 20) * 5
Operators and operands can be stored temporarily in stacks during evaluation.
Many calculators internally use stack-based algorithms to process mathematical expressions.
One of the most common applications of stacks is checking balanced parentheses.
{ [ ( ) ] }
Whenever an opening bracket is encountered, it is pushed onto the stack. When a closing bracket appears, the corresponding opening bracket is removed.
If all brackets match correctly, the expression is balanced.
Browsers store previously visited pages in a stack. Clicking the Back button retrieves the most recently visited page.
Many mobile apps maintain screen navigation using stacks.
Operating systems use stacks for managing processes and function calls.
Compilers use stacks for syntax analysis and expression processing.
Game engines often use stacks to manage states and navigation between game screens.
| Stack | Queue |
|---|---|
| Follows LIFO. | Follows FIFO. |
| Insertion and deletion at same end. | Insertion and deletion at different ends. |
| Uses TOP pointer. | Uses FRONT and REAR pointers. |
| Last inserted element removed first. | First inserted element removed first. |
A Stack is a linear data structure that follows the Last In First Out (LIFO) principle.
Push, Pop, Peek, IsEmpty, and IsFull.
Last In First Out means the most recently inserted element is removed first.
It occurs when an insertion operation is performed on a full stack.
It occurs when a deletion operation is performed on an empty stack.
O(1)
O(1)
Arrays and Linked Lists.
Because each recursive function call requires temporary storage that follows LIFO behavior.
It stores the position of the topmost element in the stack.
Peek Operation.
Fast insertion and deletion operations.
Only the top element can be accessed directly.
It stores browsing history and supports the Back functionality.
Stack follows LIFO, while Queue follows FIFO.
Stack is one of the most fundamental and useful data structures in computer science. It follows the Last In First Out principle and provides efficient insertion and deletion operations. Stacks are widely used in recursion, compiler design, operating systems, browser navigation, expression evaluation, and many other applications.
Understanding stack implementation, operations, complexity analysis, and practical applications helps students build a strong foundation in Data Structures and Algorithms. Stack-based problems are frequently asked in technical interviews, competitive programming, and university examinations.