Stack Data Structure: LIFO Principle, Implementation, and Applications (2026)
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. The most recently added element is the first to be removed. Think of a stack of plates — you add plates to the top and remove from the top. Stacks are fundamental in recursion, expression evaluation, and backtracking algorithms.
This tutorial covers array-based and linked-list-based stack implementations, infix-to-postfix conversion, postfix evaluation, and balanced parentheses checking with code examples in C++, Java, and Python.
Array-Based and Linked-List-Based Stack
An array-based stack uses a top pointer (index) that increments on push and decrements on pop. The main advantage is O(1) access to the top, but the size is fixed unless you use a dynamic array. A linked-list-based stack uses nodes where each node's next points to the element below it. Push and pop operate on the head in O(1) time with dynamic sizing.
Both implementations provide push(), pop(), peek(), and isEmpty() operations. Choosing between them depends on whether predictable memory layout or dynamic sizing matters more.
// C++ — array stack
class Stack {
int *arr, top, cap;
public:
Stack(int c) { cap = c; arr = new int[c]; top = -1; }
void push(int x) { arr[++top] = x; }
int pop() { return arr[top--]; }
};
// Java — using ArrayList
class Stack {
ArrayList list = new ArrayList<>();
void push(int x) { list.add(x); }
int pop() { return list.remove(list.size()-1); }
}
// Python — using list
stack = []
stack.append(10) # push
top = stack.pop() # pop Infix to Postfix Conversion
Infix expressions (e.g., A + B * C) are human-readable but hard for computers to evaluate. Postfix notation (e.g., A B C * +) eliminates parentheses and enables stack-based evaluation. The conversion uses operator precedence and associativity rules.
The algorithm scans the infix string: operands go directly to output; operators are pushed onto the stack after popping operators with higher or equal precedence. Parentheses are handled specially — '(' is pushed, ')' pops until '('.
// C++ — infix to postfix
string infixToPostfix(string s) {
stack st;
string res;
for(char c : s) {
if(isalnum(c)) res += c;
else if(c == '(') st.push(c);
else if(c == ')') {
while(st.top() != '(')
res += st.top(), st.pop();
st.pop();
} else {
while(!st.empty() && prec(c) <= prec(st.top()))
res += st.top(), st.pop();
st.push(c);
}
}
return res;
}
// Java — similar logic with Stack
// Python
def infix_to_postfix(s):
prec = {'+':1, '-':1, '*':2, '/':2}
st, res = [], ""
for c in s:
if c.isalnum(): res += c
elif c == '(': st.append(c)
elif c == ')':
while st[-1] != '(': res += st.pop()
st.pop()
else:
while st and st[-1] != '(' and prec[c] <= prec[st[-1]]: res += st.pop()
st.append(c)
return res Balanced Parentheses Check
Checking balanced parentheses is a classic stack application. Scan the string: when you see an opening bracket ( [ {, push it onto the stack. When you see a closing bracket ) ] }, check if the stack's top matches the corresponding opening bracket. If it matches, pop; otherwise, the string is unbalanced.
After the scan, the stack must be empty for the expression to be balanced. This algorithm runs in O(n) time and O(n) space. It can be extended to check HTML tags or code block delimiters.
// C++
bool isBalanced(string s) {
stack st;
for(char c : s) {
if(c == '(' || c == '{' || c == '[') st.push(c);
else {
if(st.empty()) return false;
if((c == ')' && st.top() != '(')) return false;
if((c == '}' && st.top() != '{')) return false;
if((c == ']' && st.top() != '[')) return false;
st.pop();
}
}
return st.empty();
}
// Java — similar with Deque
// Python
def is_balanced(s):
st, pairs = [], {")":"(", "]":"[", "}":"{"}
for c in s:
if c in "([{": st.append(c)
elif not st or st.pop() != pairs[c]: return False
return len(st) == 0 Frequently Asked Questions
What is the time complexity of stack operations?
Push, pop, and peek are all O(1) in both array-based and linked-list-based implementations.
What is stack overflow?
Stack overflow occurs when a program attempts to push an element onto a full stack (fixed-size array implementation) or when recursion depth exceeds the call stack limit.
Originally published on Ayodhyyya. Last updated June 1, 2026.