Login
OR
Don't worry. We'll fix this for you!
Imagine a stack of plates in your kitchen. You place plates one on top of another, forming a neat pile. When you need a plate, you take the one from the top. You cannot take a plate from the middle or bottom without disturbing the ones above it. This simple idea forms the basis of a stack in computer science.
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means the last element added (pushed) to the stack is the first one to be removed (popped). Stacks are essential in many computing tasks such as expression evaluation, undo mechanisms in software, and managing function calls.
Stacks support a few fundamental operations that allow us to add, remove, and inspect elements:
graph TD A[Start] --> B{Is stack full?} B -- No --> C[Push element] C --> D[Update top pointer] D --> E[End] B -- Yes --> F[Stack Overflow Error] A --> G{Is stack empty?} G -- No --> H[Pop element] H --> I[Update top pointer] I --> E G -- Yes --> J[Stack Underflow Error]An array is a collection of elements stored in contiguous memory locations. We can use an array to implement a stack by maintaining a variable called top that points to the current top element in the stack.
Initially, when the stack is empty, top = -1. When we push an element, we increment top and place the new element at array[top]. When popping, we remove the element at array[top] and decrement top.
However, since arrays have fixed size, we must check for overflow (when top == size - 1) before pushing, and underflow (when top == -1) before popping.
A linked list is a collection of nodes where each node contains data and a reference (or pointer) to the next node. Unlike arrays, linked lists allow dynamic memory allocation, so the stack can grow or shrink as needed without worrying about fixed size.
In a linked list-based stack, the top pointer points to the head node. Push operation adds a new node at the head, and pop removes the node from the head. This makes both operations efficient with time complexity \(O(1)\).
5 6 2 + * 12 4 / - using a stack. Step 1: Initialize an empty stack.
Step 2: Read the expression from left to right.
Step 3: Push operands onto the stack.
Step 4: When an operator is encountered, pop the top two operands, apply the operator, and push the result back.
Step 5: Process each token:
Answer: The value of the postfix expression is 37.
Step 1: Initialize top = -1 and array size = 5.
Step 2: Push 10 -> top = 0, stack = [10]
Step 3: Push 20 -> top = 1, stack = [10, 20]
Step 4: Pop -> remove 20, top = 0, stack = [10]
Step 5: Push 30 -> top = 1, stack = [10, 30]
Step 6: Push 40 -> top = 2, stack = [10, 30, 40]
Step 7: Push 50 -> top = 3, stack = [10, 30, 40, 50]
Step 8: Push 60 -> top = 4, stack = [10, 30, 40, 50, 60]
Step 9: Attempt to push another element would cause stack overflow since top = size - 1.
Answer: Final stack contents: [10, 30, 40, 50, 60]
{[()()]} has balanced parentheses using a stack. Step 1: Initialize an empty stack.
Step 2: Traverse the expression character by character:
Step 3: Stack is empty at the end, so parentheses are balanced.
Answer: The expression is balanced.
(A + B) * (C - D) to postfix using stack operations. Step 1: Initialize an empty stack for operators and an empty output string.
Step 2: Scan the expression from left to right:
Step 3: Pop remaining operators -> pop '*' -> Output: "AB+CD-*"
Answer: The postfix expression is AB+CD-*.
Stack Overflow: Occurs when trying to push an element into a full stack.
Example: Stack size = 3, current elements = [10, 20, 30], top = 2.
Attempt to push 40 -> Since top = size - 1, no space left -> Overflow error.
Stack Underflow: Occurs when trying to pop an element from an empty stack.
Example: Stack is empty, top = -1.
Attempt to pop -> No elements to remove -> Underflow error.
Answer: Always check stack boundaries before push/pop to avoid these errors.
When to use: When trying to understand or explain stack behavior quickly.
top to track the current element in array-based stacks to simplify push and pop operations. When to use: During implementation of stack using arrays.
When to use: When solving syntax checking problems in expressions.
When to use: While evaluating postfix or prefix expressions.
top has reached the maximum size before pushing. When to use: When performing push operations in static stacks.
top pointer during push and pop operations.top after push and decrement before pop consistently.top causes data corruption or access errors.| Feature | Stack | Queue | Deque |
|---|---|---|---|
| Order | LIFO (Last In First Out) | FIFO (First In First Out) | Both ends insertion/removal |
| Insertion/Removal | Top only | Front removal, rear insertion | Front and rear |
| Use Cases | Expression evaluation, backtracking | Scheduling, buffering | Yes |
| Overflow Handling | Check top pointer | Check front and rear pointers | Check front and rear pointers |
Progress tracking is paywalled — subscribe to mark subtopics as understood and save your streak.
Go to practice →
Your Score
Your Rank
| Rank | Name | Score |
|---|