Algorithms and Problem Solving with Java
Using Stacks, Queues, and Deques in Algorithms
You are viewing a free preview lesson.
Lesson Overview
আগের module-এ আমরা শিখেছি:
Queue → FIFO
Stack → LIFO
Deque → both ends
এখন আমরা দেখব algorithm design-এ এগুলো কীভাবে ব্যবহার করা হয়।
একটি algorithm-এর result শুধু data-এর উপর depend করে না।
অনেক সময় depend করে:
Which item do we process next?
এই প্রশ্নের উত্তরই data structure choice নির্ধারণ করে।
Examples:
Oldest pending item first
→ Queue
Most recently discovered item first
→ Stack
Need both ends
→ Deque
এই lesson-এ আমরা শিখব:
- Worklist-based algorithms
- FIFO vs LIFO processing
ArrayDequeas an algorithmic worklist- Balanced bracket validation
- Undo-style processing
- Reversing data with a Stack
- Processing tasks with a Queue
- Breadth-first processing intuition
- Depth-first processing intuition
- Iterative traversal with Stack
- Queue-based traversal
- Deque-based algorithms
- Palindrome checking
- Sliding-window intuition
- Complexity considerations
- Common mistakes
What Is a Worklist?
Many algorithms repeatedly do this:
1. Discover some work.
2. Store the work.
3. Pick the next item.
4. Process it.
5. Possibly discover more work.
6. Repeat.
The structure storing pending work is often called a:
worklist
The type of worklist matters।
Same Data, Different Processing Order
Suppose pending tasks are:
A
B
C
If we use a Queue:
A → B → C
If we use a Stack:
C → B → A
The same values are processed in a different order।
That can completely change an algorithm's traversal behavior।
Queue as a Worklist
With FIFO:
Queue<String> work =
new ArrayDeque<>();
Add:
work.offer(
"A"
);
work.offer(
"B"
);
work.offer(
"C"
);
Process:
while (
!work.isEmpty()
) {
String item =
work.poll();
System.out.println(
item
);
}
Output:
A
B
C
Stack as a Worklist
Using Deque:
Deque<String> work =
new ArrayDeque<>();
Push:
work.push(
"A"
);
work.push(
"B"
);
work.push(
"C"
);
Process:
while (
!work.isEmpty()
) {
String item =
work.pop();
System.out.println(
item
);
}
Output:
C
B
A
Algorithmic Meaning
Queue means:
Process older discovered work first.
Stack means:
Process newer discovered work first.
This distinction becomes especially important in:
Graph traversal
Tree traversal
Search problems
Parsing
Backtracking
Scheduling
Stack Algorithm Example — Balanced Brackets
Consider:
{[()]}
Opening brackets appear in this order:
{
[
(
They must close in reverse order:
)
]
}
That is:
LIFO
So Stack is a natural fit।
Balanced Bracket Algorithm
Rules:
Opening bracket
→ push
Closing bracket
→ pop most recent opening bracket
Mismatch
→ invalid
Anything left at end
→ invalid
Implementation
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) {
System.out.println(
isBalanced(
"{[()]}"
)
);
System.out.println(
isBalanced(
"{[(])}"
)
);
}
static boolean isBalanced(
String value
) {
Deque<Character> stack =
new ArrayDeque<>();
for (
int i = 0;
i < value.length();
i++
) {
char current =
value.charAt(
i
);
if (
isOpening(
current
)
) {
stack.push(
current
);
continue;
}
if (
isClosing(
current
)
) {
if (
stack.isEmpty()
) {
return false;
}
char opening =
stack.pop();
if (
!matches(
opening,
current
)
) {
return false;
}
}
}
return stack.isEmpty();
}
static boolean isOpening(
char value
) {
return value == '('
|| value == '['
|| value == '{';
}
static boolean isClosing(
char value
) {
return value == ')'
|| value == ']'
|| value == '}';
}
static boolean matches(
char opening,
char closing
) {
return opening == '('
&& closing == ')'
|| opening == '['
&& closing == ']'
|| opening == '{'
&& closing == '}';
}
}
Why Stack Works Here
Suppose input begins:
{[
Stack:
Top
↓
[
{
Then closing bracket:
]
must match:
[
which is exactly the top of the stack।
Complexity of Balanced Brackets
Let:
n = number of characters
Each character is processed once।
Time:
O(n)
In the worst case, all characters may be opening brackets।
Stack space:
O(n)
Stack Algorithm Example — Reverse Values
Suppose:
A
B
C
D
Push all:
Top
↓
D
C
B
A
Pop all:
D
C
B
A
The stack naturally reverses order।
Reverse a List Using Stack
static List<String> reversed(
List<String> values
) {
Deque<String> stack =
new ArrayDeque<>();
for (
String value
: values
) {
stack.push(
value
);
}
List<String> result =
new ArrayList<>();
while (
!stack.isEmpty()
) {
result.add(
stack.pop()
);
}
return result;
}
Complexity
Push all:
O(n)
Pop all:
O(n)
Total:
O(n)
Extra space:
O(n)
Is Stack the Best Way to Reverse a List?
Not always।
For an index-accessible list or array, two-pointer swapping may use:
O(1)
extra space।
The Stack solution is useful when LIFO itself is part of the problem or when we want to demonstrate stack semantics।
Stack Algorithm Example — Undo
Suppose operations occur:
Create course
Rename course
Publish course
Undo should reverse:
Publish
Rename
Create
Again:
LIFO
Simple Undo History
Deque<String> history =
new ArrayDeque<>();
history.push(
"Create course"
);
history.push(
"Rename course"
);
history.push(
"Publish course"
);
Undo:
String action =
history.pop();
returns:
Publish course
Queue Algorithm Example — FIFO Task Processing
Suppose tasks arrive:
Generate invoice
Send email
Update report
If fairness requires arrival order:
FIFO
Use Queue।
Implementation
static void processAll(
Queue<String> tasks
) {
while (
!tasks.isEmpty()
) {
String task =
tasks.poll();
System.out.println(
"Processing: "
+ task
);
}
}
Queue Complexity
With ArrayDeque:
offer()
poll()
are generally efficient, typically amortized:
O(1)
Processing n tasks:
O(n)
Breadth-First Processing
One of the most important Queue-based algorithm ideas is:
Breadth-First Search
or:
BFS
BFS processes items level by level।
Imagine:
A
/ \
B C
/ \ / \
D E F G
Breadth-first order:
A
B C
D E F G
Linearized:
A B C D E F G
Why Queue Fits BFS
Start:
Queue:
[A]
Process A।
Discover:
B
C
Queue becomes:
[B, C]
Process B।
Discover:
D
E
Queue:
[C, D, E]
Older discovered C is processed before newer D and E।
That gives level-order behavior।
Tree Node Example
We have not yet deeply studied trees, but a minimal node can look like:
class Node {
private final String value;
private final Node left;
private final Node right;
Node(
String value,
Node left,
Node right
) {
this.value =
value;
this.left =
left;
this.right =
right;
}
String value() {
return value;
}
Node left() {
return left;
}
Node right() {
return right;
}
}
Breadth-First Traversal
static void breadthFirst(
Node root
) {
if (
root == null
) {
return;
}
Queue<Node> queue =
new ArrayDeque<>();
queue.offer(
root
);
while (
!queue.isEmpty()
) {
Node current =
queue.poll();
System.out.println(
current.value()
);
if (
current.left()
!= null
) {
queue.offer(
current.left()
);
}
if (
current.right()
!= null
) {
queue.offer(
current.right()
);
}
}
}
Important Pattern
Notice the algorithm:
Take next item
Process it
Add newly discovered items
Repeat
This is the worklist pattern again।
Breadth-First Search Complexity
If a tree contains:
n nodes
and every node is visited once:
Time:
O(n)
The queue may hold multiple nodes at the same time।
Space depends on the maximum width of the structure।
Worst case can be:
O(n)
Depth-First Processing
Another major traversal strategy is:
Depth-First Search
or:
DFS
Instead of processing all nearby items first, DFS follows one path deeply before returning।
For:
A
/ \
B C
/ \ / \
D E F G
one possible DFS order:
A B D E C F G
Why Stack Fits DFS
When you discover children, a Stack makes the most recently discovered child the next item processed।
That naturally drives the traversal deeper।
Iterative DFS
static void depthFirst(
Node root
) {
if (
root == null
) {
return;
}
Deque<Node> stack =
new ArrayDeque<>();
stack.push(
root
);
while (
!stack.isEmpty()
) {
Node current =
stack.pop();
System.out.println(
current.value()
);
if (
current.right()
!= null
) {
stack.push(
current.right()
);
}
if (
current.left()
!= null
) {
stack.push(
current.left()
);
}
}
}
Why Push Right Before Left?
Stack is LIFO।
We want:
left child processed first
So we push:
right first
left second
Then:
left
is on top and gets popped first।
Stack Order Can Be Subtle
Suppose:
stack.push(
left
);
stack.push(
right
);
Then right will be processed first।
This is a common beginner mistake।
Always reason about:
What was pushed last?
Recursive DFS vs Explicit Stack
Recursive version:
visit(
node
);
visit(
node.left()
);
visit(
node.right()
);
uses the Java call stack implicitly।
Iterative DFS:
Deque<Node> stack =
new ArrayDeque<>();
uses an explicit stack।
Conceptually, both rely on LIFO behavior।
Why Use an Explicit Stack?
Benefits can include:
More control over traversal state
Avoid very deep recursion
Pause/resume style processing
Store additional metadata
Recursion may still be clearer for some tree algorithms।
Queue vs Stack Traversal
For the same structure:
Queue
→ breadth first
Stack
→ depth first
This is one of the clearest examples of how data structure choice changes algorithm behavior।
BFS vs DFS Intuition
BFS
Good mental model:
Explore nearby first.
Often useful when searching for:
Shortest number of edges in an unweighted graph
Nearest reachable state
Level-based processing
DFS
Good mental model:
Explore one path deeply first.
Often useful for:
Tree traversal
Backtracking
Dependency exploration
Cycle/search problems
We will not go deeply into graph algorithms in this course।
Deque Algorithm Example — Palindrome Check
Deque lets us compare both ends।
Input:
LEVEL
Build:
L E V E L
Compare:
first L
last L
Remove both।
Then:
E V E
Continue।
Implementation
static boolean isPalindrome(
String value
) {
Deque<Character> characters =
new ArrayDeque<>();
for (
int i = 0;
i < value.length();
i++
) {
characters.addLast(
value.charAt(
i
)
);
}
while (
characters.size() > 1
) {
char first =
characters.removeFirst();
char last =
characters.removeLast();
if (
first != last
) {
return false;
}
}
return true;
}
Complexity
Building deque:
O(n)
Comparisons:
O(n)
Total:
O(n)
Extra space:
O(n)
Better Palindrome Approach?
For a String, two indexes are usually simpler and use less extra memory:
static boolean isPalindrome(
String value
) {
int left =
0;
int right =
value.length() - 1;
while (
left < right
) {
if (
value.charAt(
left
)
!= value.charAt(
right
)
) {
return false;
}
left++;
right--;
}
return true;
}
Time:
O(n)
Extra space:
O(1)
This is an important engineering lesson:
A data structure may fit conceptually
without being the most memory-efficient solution.
Deque and Sliding Windows
A Deque becomes especially useful in algorithms involving:
a moving window
Suppose we process:
10 20 30 40 50
with window size:
3
Windows are:
10 20 30
20 30 40
30 40 50
As the window moves:
Old values expire from front
New values arrive at back
This naturally matches:
addLast(...)
removeFirst(...)
Simple Fixed-Size Window
static void printWindows(
int[] values,
int windowSize
) {
if (
windowSize <= 0
|| windowSize > values.length
) {
throw new IllegalArgumentException(
"Invalid window size."
);
}
Deque<Integer> window =
new ArrayDeque<>();
for (
int value
: values
) {
window.addLast(
value
);
if (
window.size()
> windowSize
) {
window.removeFirst();
}
if (
window.size()
== windowSize
) {
System.out.println(
window
);
}
}
}
Output Example
For:
[10, 20, 30, 40, 50]
window size:
3
output:
[10, 20, 30]
[20, 30, 40]
[30, 40, 50]
Why This Matters
Sliding-window techniques appear in problems such as:
Recent events
Rate limiting
Rolling metrics
Moving averages
Streaming analysis
Advanced versions use a Deque to maintain candidates for:
minimum
maximum
efficiently।
We only need the foundation here।
Queue for Level-Based Processing
Suppose tasks contain levels:
Level 0:
root
Level 1:
children
Level 2:
grandchildren
A Queue naturally preserves discovery order so one level can be processed before the next।
This appears in:
Tree level order
Shortest-path exploration in unweighted graphs
Dependency distance
Tracking Level Boundaries
A common BFS pattern is:
int levelSize =
queue.size();
Then process exactly that many items before moving to the next level।
Conceptually:
while (
!queue.isEmpty()
) {
int levelSize =
queue.size();
for (
int i = 0;
i < levelSize;
i++
) {
...
}
}
Example Level Order
static void printByLevel(
Node root
) {
if (
root == null
) {
return;
}
Queue<Node> queue =
new ArrayDeque<>();
queue.offer(
root
);
while (
!queue.isEmpty()
) {
int levelSize =
queue.size();
for (
int i = 0;
i < levelSize;
i++
) {
Node current =
queue.poll();
System.out.print(
current.value()
+ " "
);
if (
current.left()
!= null
) {
queue.offer(
current.left()
);
}
if (
current.right()
!= null
) {
queue.offer(
current.right()
);
}
}
System.out.println();
}
}
Queue Size Captures Current Level
Suppose queue starts with:
A
Then:
levelSize = 1
While processing A, we add:
B
C
But the current loop still processes only the original:
1 item
Next outer iteration:
levelSize = 2
So B and C form the next level।
Graph Traversal Preview
Trees have no cycles when correctly structured।
Graphs may contain:
A → B
B → C
C → A
If we blindly keep adding discovered nodes, traversal may never stop।
Graph algorithms therefore commonly maintain a:
visited set
Example conceptually:
Set<Node> visited =
new HashSet<>();
Worklist + Visited Pattern
General traversal structure:
Add start node to worklist
Mark visited
While worklist not empty:
remove next
process
for each neighbor:
if not visited:
mark visited
add to worklist
The worklist type determines traversal order:
Queue → BFS
Stack → DFS
Why Mark Before Adding?
Suppose multiple nodes discover the same neighbor।
If we mark visited only after removing it later, the same node may be added multiple times।
A common pattern is:
mark when discovered
rather than:
mark much later when processed
Exact strategy can vary by algorithm, but duplicate work must be considered।
Worklist API Design
A useful abstraction question is:
Does the algorithm need:
oldest work?
newest work?
highest-priority work?
That maps naturally to:
Queue
Stack
PriorityQueue
We'll study PriorityQueue in the next lesson।
FIFO vs LIFO vs Priority
Queue
→ First discovered, first processed
Stack
→ Last discovered, first processed
PriorityQueue
→ Highest/lowest priority according to ordering
This is a powerful mental model।
Data Structure Determines Scheduling Policy
Imagine three tasks:
Task A priority 5
Task B priority 1
Task C priority 10
A FIFO Queue cares about:
arrival order
A Stack cares about:
most recent
A PriorityQueue cares about:
priority ordering
Same items।
Different processing policy।
Complexity of Stack/Queue Worklists
With ArrayDeque, common end operations are typically amortized:
O(1)
If an algorithm adds and removes each item once:
n additions
n removals
worklist operations contribute roughly:
O(n)
Example Traversal Complexity
For a tree containing n nodes:
BFS:
Each node:
enqueue once
dequeue once
Time:
O(n)
DFS:
Each node:
push once
pop once
Time:
O(n)
Different traversal order does not necessarily mean different asymptotic complexity।
But Memory Behavior Can Differ
Consider a very wide tree:
root
/ / / / / / \
many children
BFS may hold many nodes simultaneously।
DFS may only hold nodes along a path plus pending siblings।
For different structure shapes:
BFS and DFS can have very different peak memory usage.
So algorithm choice can affect more than processing order।
Recursion as an Implicit Stack
Consider:
static void traverse(
Node node
) {
if (
node == null
) {
return;
}
System.out.println(
node.value()
);
traverse(
node.left()
);
traverse(
node.right()
);
}
The JVM call stack tracks pending calls।
That makes recursion naturally depth-first।
Explicit Stack Gives Visible State
Equivalent iterative style:
Deque<Node> stack =
new ArrayDeque<>();
Now the pending traversal state is visible as application data rather than hidden inside nested method calls।
Common Mistake 1 — Queue for Undo
Undo should normally process:
most recent action first
So FIFO Queue is wrong।
Use LIFO Stack behavior।
Common Mistake 2 — Stack for Fair Arrival Processing
If requests must be processed in arrival order, Stack reverses fairness।
Use Queue।
Common Mistake 3 — Wrong Child Push Order
For iterative DFS:
stack.push(
left
);
stack.push(
right
);
means:
right is processed first
because Stack is LIFO।
Common Mistake 4 — Forgetting Empty Checks
This can throw:
stack.pop();
when empty।
Use:
isEmpty()
or nullable operations such as:
pollFirst()
when appropriate।
Common Mistake 5 — Using ArrayList.remove(0) as Queue
Repeated front removal from ArrayList is not a good default FIFO implementation।
Use:
Queue<T>
with:
ArrayDeque<T>
Common Mistake 6 — Revisiting Graph Nodes Forever
When traversing a graph with cycles, failing to track visited nodes can cause:
Repeated work
Infinite traversal
Memory growth
Trees and graphs are not identical।
Common Mistake 7 — Using Deque Without Clear End Semantics
Code like:
addFirst(...)
pollLast(...)
addLast(...)
pollFirst(...)
can become difficult to reason about if there is no intentional rule।
Define clearly:
What does front mean?
What does back mean?
Common Mistake 8 — Choosing by API Familiarity Instead of Algorithm Need
Do not choose List just because you know it best।
Ask:
What should be processed next?
That often immediately suggests the right worklist।
Common Mistake 9 — Assuming Same Complexity Means Same Behavior
BFS and DFS can both be:
O(n)
on a tree।
But their:
Traversal order
Peak memory
Search behavior
can differ significantly।
Common Mistake 10 — Stack When Recursion Is Simpler
Explicit stacks are useful, but they are not automatically better।
For a small, naturally recursive tree traversal:
Recursive DFS
may be clearer।
Choose the version that fits the constraints and readability needs।
Practical Example — Request Processing
import java.util.ArrayDeque;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<Request> requests =
new ArrayDeque<>();
requests.offer(
new Request(
1,
"Enroll Sakib"
)
);
requests.offer(
new Request(
2,
"Enroll Subu"
)
);
requests.offer(
new Request(
3,
"Enroll Sumu"
)
);
processAll(
requests
);
}
static void processAll(
Queue<Request> requests
) {
while (
!requests.isEmpty()
) {
Request request =
requests.poll();
System.out.println(
request.id()
+ ": "
+ request.description()
);
}
}
record Request(
long id,
String description
) {
}
}
FIFO preserves request order।
Practical Example — Navigation History
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) {
Deque<String> history =
new ArrayDeque<>();
visit(
history,
"/courses"
);
visit(
history,
"/courses/java"
);
visit(
history,
"/courses/java/lesson-1"
);
System.out.println(
"Current: "
+ history.peek()
);
history.pop();
System.out.println(
"Back to: "
+ history.peek()
);
}
static void visit(
Deque<String> history,
String page
) {
history.push(
page
);
}
}
Practice 1 — Choose Queue or Stack
A ticketing system must process requests in arrival order।
Answer
Queue
Practice 2 — Choose Queue or Stack
Undo the most recent command।
Answer
Stack
implemented with:
Deque<T>
Practice 3 — Balanced Brackets
Why is Stack appropriate for:
{[()]}
Answer
Because the most recently opened bracket must be the first one closed।
That is LIFO behavior।
Practice 4 — BFS
What data structure normally drives Breadth-First Search?
Answer
Queue
Practice 5 — DFS
What data structure can drive iterative Depth-First Search?
Answer
Stack
usually implemented using:
Deque<T>
and:
ArrayDeque<T>
Practice 6 — DFS Push Order
Suppose we want:
left child
processed before:
right child
Which should be pushed first?
Answer
Push:
right first
left second
because the left child must be on top of the Stack।
Practice 7 — Complexity
A BFS processes every tree node exactly once।
If there are n nodes, what is the time complexity?
Answer
O(n)
Practice 8 — Bracket Complexity
Balanced bracket validation examines every character once।
Time:
?
Worst-case stack space:
?
Answer
Time:
O(n)
Space:
O(n)
Practice 9 — Deque
When might a Deque be more suitable than a simple Queue?
Answer
When the algorithm intentionally needs operations at both ends, such as:
Sliding windows
Palindrome processing
Recent-item windows
Double-ended scheduling
Practice 10 — Worklist Choice
Fill in:
Oldest pending work first
→ ?
Newest pending work first
→ ?
Priority-based pending work
→ ?
Answer
Oldest first
→ Queue
Newest first
→ Stack
Priority-based
→ PriorityQueue
Practice 11 — Graph Safety
Why is a visited set often required in graph traversal?
Answer
Because graphs can contain cycles or multiple paths to the same node, which can otherwise cause repeated or infinite processing।
Practice 12 — Recursion
Why can recursive DFS be considered stack-based even without creating a Deque?
Answer
Because recursive method calls are stored on the JVM call stack, which follows LIFO behavior।
True or False
- A Queue processes oldest pending work first.
- A Stack processes newest pending work first.
- Balanced bracket validation naturally fits FIFO.
- BFS normally uses a Queue.
- Iterative DFS normally uses a Stack.
- Recursion uses stack-like method-call behavior.
ArrayDequecan implement both Queue and Stack worklists.- BFS and DFS always visit nodes in the same order.
- A Deque can be useful for sliding-window algorithms.
- Graph traversal may require visited tracking.
- Stack push order can affect DFS visitation order.
- A Queue is normally appropriate for undo history.
- BFS and DFS can both be
O(n)on a tree. - Same Big-O means two algorithms behave identically.
Answers
1. True
2. True
3. False
4. True
5. True
6. True
7. True
8. False
9. True
10. True
11. True
12. False
13. True
14. False
Knowledge Check
Question 1
What is a worklist?
Question 2
How does FIFO change work-processing order?
Question 3
How does LIFO change work-processing order?
Question 4
Why is a Stack appropriate for bracket matching?
Question 5
Why does BFS naturally use a Queue?
Question 6
Why does iterative DFS naturally use a Stack?
Question 7
Why might DFS push the right child before the left child?
Question 8
How is recursive DFS related to a Stack?
Question 9
Why can graph traversal require a Set in addition to a Queue or Stack?
Question 10
How can a Deque support a moving window?
Question 11
Why might BFS and DFS have different memory behavior?
Question 12
What question should you ask before choosing Queue, Stack, or PriorityQueue?
Knowledge Check Answers
Answer 1
A worklist is a data structure that stores items discovered by an algorithm but not yet processed।
Answer 2
FIFO processes the earliest pending item before newer ones।
Answer 3
LIFO processes the most recently added pending item first।
Answer 4
Because closing brackets must match opening brackets in reverse order of their appearance।
Answer 5
Because BFS explores previously discovered nearby nodes before newly discovered deeper nodes, which matches FIFO behavior।
Answer 6
Because DFS continues with recently discovered deeper work first, matching LIFO behavior।
Answer 7
Because the Stack removes the most recently pushed item first. Pushing right first and left second makes left the next item processed।
Answer 8
Recursive method calls are tracked by the JVM call stack, so recursive traversal implicitly uses LIFO state management।
Answer 9
A graph may contain cycles or multiple paths to the same node. A visited set prevents unnecessary repeated processing and potential infinite traversal।
Answer 10
New values can be inserted at the back while expired values are removed from the front।
Answer 11
BFS may retain a large level or frontier, while DFS tends to retain a path plus pending alternatives. Their peak memory therefore depends on the structure's shape।
Answer 12
Ask:
Which pending item should be processed next?
If the answer is:
Oldest
→ Queue
Newest
→ Stack
Best priority
→ PriorityQueue
Practical Decision Guide
Use a Queue when:
Arrival order matters
Breadth-first exploration matters
Older pending work should be handled first
Use a Stack when:
Most recent work matters
Undo behavior is required
Depth-first exploration is required
Nested structures must be matched
Use a Deque when:
Both ends are meaningful
You need Queue or Stack behavior with ArrayDeque
A moving window requires front removal and back insertion
Use a Set alongside traversal when:
Items may be discovered more than once
Cycles are possible
Algorithmic Worklist Mental Model
The key idea is:
Discover work
↓
Store it
↓
Choose next according to policy
↓
Process
↓
Discover more work
The processing policy comes from the data structure:
Queue
→ FIFO
Stack
→ LIFO
PriorityQueue
→ priority ordering
This pattern appears repeatedly in real algorithms and backend systems।
Lesson Summary
এই lesson-এ আমরা Stack, Queue, এবং Deque-কে শুধু collections হিসেবে নয়, algorithmic tools হিসেবে ব্যবহার করেছি।
We learned:
- Worklists store discovered but unprocessed work
- Queue creates FIFO processing order
- Stack creates LIFO processing order
ArrayDequecan implement both patterns efficiently- Balanced bracket validation is naturally stack-based
- Undo behavior follows LIFO
- Stack can reverse processing order
- Queue is appropriate for arrival-order task processing
- Breadth-First Search uses Queue semantics
- Depth-First Search can use Stack semantics
- Recursive DFS implicitly uses the JVM call stack
- DFS child push order affects visitation order
- Graph traversal often needs a visited set
- Deque supports double-ended algorithms
- Sliding windows naturally add at one end and remove from the other
- BFS and DFS may share similar time complexity while having different traversal and memory behavior
- Data-structure selection defines work scheduling policy
The most important question is:
Which pending item should the algorithm process next?
That question often tells you the correct data structure:
Oldest
→ Queue
Newest
→ Stack
Both ends
→ Deque
Highest priority
→ PriorityQueue
Next Lesson
পরবর্তী lesson:
Heaps and PriorityQueue
আমরা শিখব:
- What priority-based processing means
- Why FIFO is not always enough
- Heap fundamentals
- Complete binary tree intuition
- Min Heap
- Max Heap
- Heap property
- Insert and heapify-up intuition
- Remove and heapify-down intuition
PriorityQueue- Default min-heap behavior
- Max-heap with Comparator
- Custom object priorities
offer(),poll(), andpeek()O(log n)insertion/removalO(1)top inspection- Top-K style problems
- Priority scheduling