Data structures play a significant role in arranging data in a specific format or order within an application. Without applying the proper data structure, your app will not function properly. Stack and queue are prominent data structures that enable developers to perform various concepts and operations. For Data Science professionals, an understanding of various data structures is essential. Learn through this Data Science Training Course. This article will take a comprehensive walkthrough of the stack, its representation, working, essential operation & real-life applications.
What is a Stack Data Structure?
Stack is a linear data structure that follows the LIFO (Last In First Out) principle for inserting and deleting elements from it. By LIFO, we mean the last element that we insert within the stack is the first element we can remove from it. You can assume a stack data structure as the pile of books or rack of plates on top of another.
Here, we can put a new book or plate on the other. Again, we can only remove one book or plate from the top of the stack. In the stack data structure, the position from where we can add or remove elements is called the "Top" of the stack.
Stack Representation
A stack can be represented visually as a vertical column of elements, where insertion and deletion happen only from one end, called the top. Every stack representation revolves around three core elements:
- Top: A pointer or index that always refers to the most recently added element.
- Elements/Data: The actual values stored inside the stack, arranged one above another.
- Base: The fixed end of the stack where the very first element is placed. This end never changes once the stack is created.
When a stack is empty, the top is typically set to -1 (in an array-based representation) or points to NULL (in a linked list-based representation). As elements are pushed in, the top moves upward one position at a time; as elements are popped out, it moves downward.
For example, if you push 10, 20, and 30 into a stack in that order, the representation looks like this from bottom to top:
| 30 | <- Top
| 20 |
| 10 | <- Base
Here, 30 sits at the top because it was inserted last, and it will also be the first one removed — this is the LIFO principle in action. This representation stays the same conceptually whether the stack is implemented using an array or a linked list; only the internal mechanics of tracking the top differ.
How can we Implement a Stack Data Structure?
We can implement stack data structure in almost every programming language like C, C++, Python, Java, C#, etc. In C and C++, we can perform this using an array. In Python, we can use a list to achieve the concept of a stack using Array or ArrayList in Java & C#.
Discover how Linear Search works with our easy-to-follow guide!
Basic Operations of a Stack Data Structure
Here is a list of some significant operations through which we can perform different activities on a stack.
- Push: It helps in adding an element to the top of a stack
- Pop: It helps in removing one element at a time from the top of a stack
- IsEmpty: It helps in checking whether the stack is empty or not
- IsFull: It helps in checking whether the stack is full or not
- Peek: It helps in fetching the top element value without removing it
Stack Insertion: Push Operation
The push operation is used to insert a new element at the top of the stack. Since a stack only allows insertion from one end, the new element always becomes the topmost element immediately after being pushed.
How push works, step by step:
Check whether the stack has reached its maximum capacity (this check prevents a stack overflow).
If the stack is full, the operation is rejected, and an overflow message is displayed.
If space is available, increment the top pointer by one.
Insert the new element at the position now referenced by the top pointer.
Example: Consider an empty stack of size 5.
- Push(10) → Stack: [10], Top = 0
- Push(20) → Stack: [10, 20], Top = 1
- Push(30) → Stack: [10, 20, 30], Top = 2
Each push places the new value above the previous top element, and the top pointer shifts accordingly.
Time Complexity: O(1), since the operation only involves updating the top pointer and inserting one element, regardless of how many elements already exist in the stack.
Space Complexity: O(1) additional space per push, though the overall stack size grows with the number of elements stored.
Stack Deletion: Pop Operation
The pop operation removes the topmost element from the stack. Because deletion is restricted to the top, the most recently inserted element is always the one removed first.
How pop works, step by step:
Check whether the stack is empty (this check prevents a stack underflow).
If the stack is empty, the operation is rejected, and an underflow message is displayed.
If elements exist, note the value at the top position (this is the value returned to the caller).
Decrement the top pointer by one, effectively removing access to that element.
Example: Continuing from the stack [10, 20, 30] with Top = 2:
- Pop() → Returns 30, Stack: [10, 20], Top = 1
- Pop() → Returns 20, Stack: [10], Top = 0
- Pop() → Returns 10, Stack: [], Top = -1
Notice that elements come out in the exact reverse order in which they were pushed — 30, then 20, then 10.
Time Complexity: O(1), since removing an element only requires reading the top value and adjusting the pointer.
Space Complexity: O(1), as no extra space is required to perform the deletion.
Peek Operation in Stack
The peek operation (also called top() in many implementations) allows you to view the value of the topmost element without removing it from the stack. This is useful when you need to inspect the most recent element before deciding whether to pop it.
How peek works, step by step:
Check whether the stack is empty. If it is, peek cannot return a valid value.
If elements exist, return the value stored at the position referenced by the top pointer.
Importantly, the top pointer is not changed — the stack remains exactly as it was.
Example: For a stack [10, 20, 30] with Top = 2:
Peek() → Returns 30 (the stack still remains [10, 20, 30] afterward)
Why peek matters in practice: Many algorithms — such as balanced parenthesis checking or expression evaluation — need to repeatedly check the current top element to decide the next step, without actually removing it until a specific condition is met. Peek makes this possible without disturbing the stack's contents.
Time Complexity: O(1), since it only involves reading a value at a known index or pointer.
Space Complexity: O(1), as no additional memory is used.
How does the Stack Data Structure Work?
You can assume the stack data structure as a pile of books, and you can only put or remove books from the top of it. Here is an algorithmic approach to understanding the working of a stack data structure.
- The first thing is to understand the "TOP" pointer that keeps track of the top element of the stack data structure.
- While creating the stack for the first time, we set the top value to “1”, which helps check whether the stack is empty. We check whether TOP == -1. If yes, we set the "empty" flag to True.
- As we push an element, we have to increase the value of the TOP and point the TOP to the place where the new element gets inserted.
- As we pop an element from the stack, we return our pointer to the location where it has an element.
- Before pushing an element into the stack, we check if the stack is already full.
- Before popping an element into the stack, we check whether the stack is already empty or not.
What is Overflow and Underflow Situation?
These are two situations in a stack data structure that occur as an error handling mechanism to mark the two extreme scenarios.
- Stack underflow: This situation occurs when an item is called or popped from the stack, but the stack is empty. Therefore, while popping an existing element, we check whether the TOP position is in -1 or not.
- Stack overflow: This situation occurs when programmers want to push a new element to the stack, but the stack is always at its maximum potential; that is, the stack is full. Thus, while pushing a new element, we check whether the TOP is equal to the SIZE of the stack.
Algorithm for Push operation
- First, check if your stack is full.
- In case your stack is full or all the element completes it, stop the program from pushing a new element into it.
- If not, increment the top by one location.
- Insert the new element to the point where the top is pointing.
Algorithm for Pop operation
- First, check if your stack is empty or not.
- If the stack is empty, i.e., there is no element in the stack, we cannot perform the pop operation.
- If not, look for the topmost element from the stack and remove it.
- Then, decrement the top by one and done.
Implementing Stack using C
Here is a simple code snippet to show how the stack data structure works and how to perform its basic operations.
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
int count = 0;
/* We will create a stack */
struct stack_ds {
int items[MAX];
int top;
};
typedef struct stack_ds sds;
void createEmptyStack(sds *stk) {
stk->top = -1;
}
/* Checking whether the stack is full or not */
int isfull(sds *stk) {
if (stk -> top == MAX - 1)
return 1;
else
return 0;
}
/* Checking whether the stack is empty or not */
int isempty(sds *stk) {
if (stk -> top == -1)
return 1;
else
return 0;
}
// Add elements into stack
void push(sds *stk, int newitem) {
if (isfull(stk)) {
printf("STACK IS FULL");
} else {
stk -> top++;
stk -> items[stk -> top] = newitem;
}
count++;
}
// Remove an element from stack
void pop(sds *stk) {
if (isempty(stk)) {
printf("\n STACK IS EMPTY \n");
} else {
printf(" Item popped = %d", stk -> items[stk -> top]);
stk -> top--;
}
count--;
printf("\n");
}
// Print elements of stack
void printStack(sds *stk) {
printf("Stack: ");
for (int i = 0; i < count; i++) {
printf("%d ", stk -> items[i]);
}
printf("\n");
}
// Driver code
int main() {
int ch;
sds *stk = (sds *)malloc(sizeof(sds));
createEmptyStack(stk);
push(stk, 1);
push(stk, 2);
push(stk, 3);
push(stk, 4);
printStack(stk);
pop(stk);
printf("\n After popping element.... \n");
printStack(stk);
}
Output:
What are the Various Ways we can Implement a Stack?
There are various ways we can implement a stack using two common data structures:
- Array: While implementing the stack using an array, we must implement the homogenous data structure array. We can perform all the stack operations using this linear data structure. In an array, the top of the stack remains on the right side of the array. Here, all the insertion and deletion take place.
- Linked List: A linked list is a sequence data structure connected through links, one after another, using pointers. Each node contains an item or data element along with one (pointing to the next node) or two (pointing to its next and previous node) pointers. We can perform the stack implementation of data structure using a Linked list.
Stack Complete Implementation
Below are complete, ready-to-run implementations of a stack using both the array-based and linked list-based approaches, in Python and Java.
Stack Implementation Using Array (Python)
class Stack:
def __init__(self, capacity):
self.stack = []
self.capacity = capacity
def is_empty(self):
return len(self.stack) == 0
def is_full(self):
return len(self.stack) == self.capacity
def push(self, item):
if self.is_full():
print("Stack Overflow")
return
self.stack.append(item)
def pop(self):
if self.is_empty():
print("Stack Underflow")
return None
return self.stack.pop()
def peek(self):
if self.is_empty():
print("Stack is empty")
return None
return self.stack[-1]
# Driver code
s = Stack(5)
s.push(10)
s.push(20)
s.push(30)
print("Top element:", s.peek())
print("Popped element:", s.pop())
print("Stack after pop:", s.stack)
Stack Implementation Using Linked List (Java)
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class Stack {
private Node top;
public boolean isEmpty() {
return top == null;
}
public void push(int value) {
Node newNode = new Node(value);
newNode.next = top;
top = newNode;
}
public int pop() {
if (isEmpty()) {
System.out.println("Stack Underflow");
return -1;
}
int value = top.data;
top = top.next;
return value;
}
public int peek() {
if (isEmpty()) {
System.out.println("Stack is empty");
return -1;
}
return top.data;
}
public static void main(String[] args) {
Stack stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println("Top element: " + stack.peek());
System.out.println("Popped element: " + stack.pop());
System.out.println("New top element: " + stack.peek());
}
}
Key takeaway: The array-based version is simple and memory-efficient for a fixed, known size, but it has a capacity limit. The linked list-based version grows dynamically and avoids overflow (as long as memory is available), at the cost of slightly higher memory overhead per element due to the pointer field.
Application of Stack Data Structure
There are various applications of stack data structure. Some of them are:
- Undo and Redo operation: The undo (Ctrl+Z) and Redo (Ctrl+Y) operations we perform in almost all the applications leverage the stack data structure. It arranges the tasks in a stacked order. If anything gets wrong and we press Ctrl+Z, it pops that task from that stack. Again, if we want to bring it back, we use Ctrl+Y to push it back to the stack.
- Expression evaluation or expression conversion: Another well-known use case of the stack data structure is when we evaluate or convert expressions like prefix, infix, or postfix.
- In prefix expression, the operator is followed by two prefix strings. For example: +XY or + + G K - P Q
- In an infix expression, the operator remains surrounded by a single infix string on both sides. For example: X+Y or (G + K ) + (P - Q)
- In a postfix expression, the operator is preceded by two postfix strings in a postfix expression. For example: XY+ or G K + P Q - +
- Backtracking: It is a recursive technique and algorithm that helps solve optimisation problems. N-queen problem and recursive function use the stack to perform backtracking.
- Parenthesis checking: If you have seen your compiler or interpreter popping with a parenthesis missing compile-time error, it's the stack that helps in checking. The compiler or interpreter uses the stack for pairing and inspecting whether you have closed all the opened parentheses.
- Syntax parsing and memory management: Compiler and interpreter designers also prefer stack data structure to perform various parsing of programming tokens and manage memory allocation, deallocation, and other management using the stack data structure.
Stack Data Structure Problems: Easy, Medium & Hard
Practicing problems is the best way to strengthen your understanding of stacks. Here is a curated list of problems categorized by difficulty level.
Easy
Reverse a String using Stack — Push each character onto a stack and pop them out to get the reversed string.
Check for Balanced Parentheses — Use a stack to verify whether an expression's brackets (), {}, [] are correctly matched and closed.
Implement Two Stacks in One Array — Design a way to store two independent stacks within a single array without overlap.
Delete Middle Element of a Stack — Remove the middle element of a stack using recursion, without using any other data structure.
Medium
Evaluate Postfix Expression — Use a stack to compute the result of an expression written in postfix (Reverse Polish) notation.
Infix to Postfix Conversion — Convert a standard infix expression into postfix form using a stack to manage operator precedence.
Next Greater Element — For every element in an array, find the next element to its right that is greater, using a stack to track candidates efficiently.
Min Stack (Design a Stack that Supports getMin() in O(1)) — Design a stack that can return the minimum element in constant time alongside regular push and pop operations.
Sort a Stack using Recursion — Sort the elements of a stack in ascending order using only recursive calls and no additional loops or data structures.
Hard
Largest Rectangle in Histogram — Use a stack to find the largest rectangular area possible in a histogram in O(n) time.
Trapping Rain Water — Calculate the amount of water that can be trapped between bars of varying heights, using a stack-based approach.
Design a Stack With Increment Operation — Build a stack that supports an additional operation to increment the bottom k elements by a given value, while keeping push/pop efficient.
Maximum of Minimums for Every Window Size — For every window size in an array, find the maximum of the minimum values using a stack-based sliding technique.
Basic Calculator (Expression Evaluation with Parentheses) — Evaluate a mathematical expression containing parentheses, plus, and minus signs using a stack to manage nested operations.
Working through these problems in order of difficulty helps build a strong foundation before tackling stack-based questions in technical interviews.
Conclusion
We hope this article has given a complete idea of the stack data structure. To learn about other data structures and how to manage large data development projects, get certified through our data science training & boost your career with a 100 % job guarantee. Learn from experts having 15+ years of experience with multiple case studies, simulated projects, & assignments.
Frequently Asked Questions (FAQs)
1. What is a stack in data structure with an example?
A stack is a linear data structure that follows the LIFO (Last In First Out) principle. For example, a stack of plates — you can only add or remove a plate from the top, never from the middle or bottom.
2. What are the main operations performed on a stack?
The main operations are push (insert an element), pop (remove the top element), peek/top (view the top element without removing it), isEmpty (check if the stack has no elements), and isFull (check if the stack has reached its capacity).
3. What is the difference between stack and queue?
A stack follows LIFO (Last In First Out), where insertion and deletion happen from the same end (the top). A queue follows FIFO (First In First Out), where insertion happens at one end (rear) and deletion happens at the other end (front).
4. Can a stack be implemented using an array as well as a linked list?
Yes. An array-based stack is simple to implement but has a fixed size, which can lead to overflow. A linked list-based stack grows dynamically, avoiding overflow, but uses slightly more memory due to pointer storage in each node.
5. What is stack overflow and stack underflow?
Stack overflow occurs when you try to push an element into a stack that has already reached its maximum capacity. Stack underflow occurs when you try to pop an element from a stack that is already empty.
6. What is the time complexity of push and pop operations?
Both push and pop operations run in O(1) time complexity, since they only involve updating the top pointer and inserting or removing a single element.
7. Where is the stack data structure used in real life?
Stacks are used in undo/redo functionality in applications, expression evaluation and conversion (infix, postfix, prefix), backtracking algorithms, browser history navigation, function call management (call stack), and syntax parsing in compilers.
8. Is recursion related to the stack data structure?
Yes. Every time a function calls itself recursively, the system uses an internal call stack to keep track of function calls, their local variables, and return addresses, following the same LIFO principle.
9. What is the difference between push, pop, and peek operations?
Push adds a new element to the top of the stack. Pop removes and returns the top element. Peek returns the value of the top element without removing it, leaving the stack unchanged.
10. Which is better for implementing a stack: array or linked list?
It depends on the use case. If the maximum size of the stack is known in advance and memory efficiency matters, an array-based implementation works well. If the size is unpredictable and dynamic growth is needed, a linked list-based implementation is the better choice.
