Stack
What is a Stack?
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle — the last element added is the first one removed. Think of a stack of plates: you always add and remove from the top.
- push(x) — add element to top — O(1)
- pop() — remove and return top element — O(1)
- peek() / top() — view top element without removing — O(1)
- isEmpty() — check if stack is empty — O(1)
Real-World Applications
- Function call stack — how programming languages manage function calls
- Undo/Redo — text editors, Photoshop
- Browser history — back button
- Expression evaluation — parsing mathematical expressions
- Balanced parentheses — compiler syntax checking
- DFS traversal — depth-first search in graphs
#include <iostream>
#include <stack>
#include <string>
using namespace std;
// Using STL stack
void stackDemo() {
stack<int> s;
s.push(10); s.push(20); s.push(30);
cout << "Top: " << s.top() << endl; // 30
s.pop();
cout << "After pop, top: " << s.top() << endl; // 20
cout << "Size: " << s.size() << endl; // 2
}
// Application: Balanced Parentheses
bool isBalanced(const string& s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
st.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (st.empty()) return false;
char top = st.top(); st.pop();
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) return false;
}
}
return st.empty();
}
int main() {
stackDemo();
cout << boolalpha;
cout << isBalanced("({[]})") << endl; // true
cout << isBalanced("({[})") << endl; // false
return 0;
}import java.util.Stack;
public class StackDemo {
// Application: Balanced Parentheses
static boolean isBalanced(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (stack.isEmpty()) return false;
char top = stack.pop();
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) return false;
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
Stack<Integer> s = new Stack<>();
s.push(10); s.push(20); s.push(30);
System.out.println("Top: " + s.peek()); // 30
s.pop();
System.out.println("After pop: " + s.peek()); // 20
System.out.println(isBalanced("({[]})")); // true
System.out.println(isBalanced("({[})")); // false
}
}# Python list as stack
stack = []
stack.append(10) # push
stack.append(20)
stack.append(30)
print("Top:", stack[-1]) # 30 — peek
stack.pop() # pop
print("After pop:", stack[-1]) # 20
# Application: Balanced Parentheses
def is_balanced(s):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for c in s:
if c in '([{':
stack.append(c)
elif c in ')]}':
if not stack or stack[-1] != pairs[c]:
return False
stack.pop()
return len(stack) == 0
print(is_balanced("({[]})")) # True
print(is_balanced("({[})")) # False
# Application: Evaluate postfix expression
def eval_postfix(expr):
stack = []
for token in expr.split():
if token.lstrip('-').isdigit():
stack.append(int(token))
else:
b, a = stack.pop(), stack.pop()
if token == '+': stack.append(a + b)
elif token == '-': stack.append(a - b)
elif token == '*': stack.append(a * b)
elif token == '/': stack.append(int(a / b))
return stack[0]
print(eval_postfix("3 4 + 2 *")) # 14 → (3+4)*2// JavaScript array as stack
const stack = [];
stack.push(10); // push
stack.push(20);
stack.push(30);
console.log("Top:", stack[stack.length - 1]); // 30 — peek
stack.pop(); // pop
console.log("After pop:", stack[stack.length - 1]); // 20
// Application: Balanced Parentheses
function isBalanced(s) {
const stack = [];
const pairs = { ')': '(', ']': '[', '}': '{' };
for (const c of s) {
if ('([{'.includes(c)) {
stack.push(c);
} else if (')]}'.includes(c)) {
if (!stack.length || stack[stack.length - 1] !== pairs[c]) return false;
stack.pop();
}
}
return stack.length === 0;
}
console.log(isBalanced("({[]})")); // true
console.log(isBalanced("({[})")); // false
// Stack class implementation
class Stack {
constructor() { this.items = []; }
push(x) { this.items.push(x); }
pop() { return this.items.pop(); }
peek() { return this.items[this.items.length - 1]; }
isEmpty() { return this.items.length === 0; }
size() { return this.items.length; }
}