A stack is a linear data structure that follows the LIFO(Last-In-First-Out) principle. The last element added to the stack is the first one to be removed, similar to a stack of plates where you can only add or remove from the top.
Stacks provide O(1) time complexity for push (insert), pop (remove), and peek (view top element) operations, making them highly efficient for specific use cases like function call management, undo mechanisms, and expression evaluation.
Push: Enter a value and click "Push" to add it to the top of the stack.
Pop: Click "Pop" to remove and see the top element of the stack.
Peek: Click "Peek" to view the top element without removing it.
Clear: Click "Clear" to remove all elements and reset the stack.
Visualization: Watch elements stack vertically to understand LIFO (Last-In-First-Out) behavior.
Push: Add an element to the top of the stack
Pop: Remove and return the top element from the stack
Peek: View the top element without removing it
Clear: Remove all elements from the stack
Push: O(1) - Add to top, no shifting required.
Pop: O(1) - Remove from top, no shifting required.
Peek/Top: O(1) - Direct access to top element.
isEmpty: O(1) - Check size or top pointer.
Search: O(n) - Must pop elements to find; not a standard stack operation.
Space Complexity: O(n) - Linear space for n elements stored.
vs Queue: Stack is LIFO (Last-In-First-Out); Queue is FIFO (First-In-First-Out). Use stack for backtracking, queue for scheduling.
vs Array: Stack restricts access to top only (O(1) push/pop); arrays allow random access anywhere (O(1) read, O(n) insert).
vs Linked List: Stack can be implemented with either; linked list gives O(1) operations without size limits, array-based has better cache locality.
vs Deque: Stack operates on one end only; deque allows operations at both ends with same O(1) complexity.
Best Use Case: Function call management, undo operations, expression evaluation, DFS traversal, and backtracking algorithms.
Undo/Redo Operations: Text editors and graphic tools push actions onto a stack, allowing users to undo by popping the most recent action.
Function Call Management: The call stack tracks function invocations, local variables, and return addresses during program execution.
Expression Evaluation: Compilers use stacks to convert infix expressions to postfix and evaluate arithmetic expressions.
Browser Back Button: Web browsers use a stack to track visited pages, enabling navigation to previously viewed sites.
Syntax Parsing: Compilers and interpreters use stacks to match parentheses, brackets, and validate code structure.
DFS & Backtracking: Depth-first search and maze-solving algorithms use stacks to explore paths and backtrack when needed.
Memory Management: The program stack allocates and deallocates local variables automatically as functions are called and return.
Recursion Simulation: Iterative solutions can simulate recursion by explicitly managing a stack of states.
Valid Parentheses: Push opening brackets, pop and match for closing; empty stack at end means valid.
Monotonic Stack: Maintain increasing/decreasing stack for next greater/smaller element problems in O(n).
Evaluate Postfix: Push operands; on operator, pop two values, compute, push result back.
Infix to Postfix: Use operator precedence rules with stack to convert expressions for evaluation.
Min Stack: Track minimum alongside values using auxiliary stack or storing pairs (value, currentMin).
Stock Span Problem: Use stack of indices to find consecutive days with price ≤ current day.
Largest Rectangle in Histogram: Monotonic stack to find left/right boundaries for each bar in O(n).
/* Simple stack using array in C */
#include <stdio.h>
#include <stdlib.h>
#define CAP 100
int top = -1;
int stack[CAP];
void push(int v) { if (top < CAP-1) stack[++top] = v; }
int pop() { if (top >= 0) return stack[top--]; return -1; }
int peek() { if (top >= 0) return stack[top]; return -1; }
int main(){
push(1); push(2); push(3);
printf("Top: %d
", peek());
pop();
printf("After pop Top: %d
", peek());
return 0;
}