Problem Statement
What is a stack data structure? Explain its operations and provide real-world applications.
Explanation
A stack is a linear data structure that follows the Last In First Out principle, meaning the last element added is the first one to be removed. Think of it like a stack of plates where you can only add or remove plates from the top.
The fundamental operations of a stack are push which adds an element to the top with O of 1 time complexity, pop which removes and returns the top element with O of 1 complexity, peek or top which returns the top element without removing it in O of 1 time, isEmpty which checks if the stack is empty, and size which returns the number of elements. All these operations work only at one end called the top of the stack.
Stacks can be implemented using arrays with a fixed size where we maintain a top pointer, or using linked lists which provide dynamic size by adding and removing nodes at the head. The array implementation is simple and provides fast access, but has size limitations. The linked list implementation offers dynamic sizing but uses extra memory for pointers.
Real-world applications of stacks are numerous. In function call management, the call stack maintains execution contexts for nested and recursive function calls. For expression evaluation, stacks convert infix expressions to postfix or prefix notation and evaluate postfix expressions efficiently. In undo and redo operations, applications like text editors use stacks to track states. For syntax parsing, compilers use stacks to check balanced parentheses, brackets, and braces in code. In backtracking algorithms, stacks store decision points in problems like maze solving and the N-Queens puzzle. Web browsers use stacks to implement the back button functionality by storing visited pages.
Code Solution
SolutionRead Only
// Stack implementation using array
class Stack {
private int[] arr;
private int top;
private int capacity;
Stack(int size) {
arr = new int[size];
capacity = size;
top = -1;
}
void push(int value) {
if (top == capacity - 1) {
System.out.println("Stack Overflow");
return;
}
arr[++top] = value;
}
int pop() {
if (isEmpty()) {
System.out.println("Stack Underflow");
return -1;
}
return arr[top--];
}
int peek() {
if (isEmpty()) return -1;
return arr[top];
}
boolean isEmpty() {
return top == -1;
}
}
// Application: Balanced Parentheses
boolean isBalanced(String str) {
Stack<Character> stack = new Stack<>();
for (char c : str.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else if (c == ')' || c == '}' || c == ']') {
if (stack.isEmpty()) return false;
char top = stack.pop();
if (!isMatchingPair(top, c)) return false;
}
}
return stack.isEmpty();
}
