Generics, Collections, and Core Data Structures

Deque, Stack, and `ArrayDeque`

ReadingPreview

You are viewing a free preview lesson.

Lesson Overview

আগের lesson-এ আমরা Queue এবং FIFO processing শিখেছি।

Queue-এর basic model ছিল:

Add at back
Remove from front

কিন্তু কিছু problem-এ আমাদের দুই দিক থেকেই data add বা remove করতে হয়।

এই abstraction হলো:

Deque<E>

Deque means:

Double-Ended Queue

অর্থাৎ:

Front থেকেও add/remove করা যায়
Back থেকেও add/remove করা যায়

আর Deque-এর একটি গুরুত্বপূর্ণ use case হলো:

Stack

Stack follows:

LIFO

meaning:

Last In, First Out

এই lesson-এ আমরা শিখব:

What a Deque is
ArrayDeque
Front and back operations
addFirst()
addLast()
offerFirst()
offerLast()
removeFirst()
removeLast()
pollFirst()
pollLast()
peekFirst()
peekLast()
What a Stack is
LIFO ordering
push()
pop()
peek()
Why Deque is normally preferred over legacy Stack
Using ArrayDeque as Queue
Using ArrayDeque as Stack
Practical stack/deque use cases
Common mistakes

What Is a Deque?

A Deque is a collection where elements can be added and removed from both ends।

Conceptually:

Front                          Back
  ↓                              ↓
[A] [B] [C] [D]

We can:

Add at front
Add at back
Remove from front
Remove from back
Inspect front
Inspect back

Pronunciation

Deque is commonly pronounced like:

deck

not:

D-Q

Java `Deque<E>`

Java provides:

java.util.Deque

It is an interface।

A common implementation is:

ArrayDeque

Example:

Deque<String> values =
        new ArrayDeque<>();

Required Imports

import java.util.ArrayDeque;
import java.util.Deque;

Complete example:

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {

    public static void main(String[] args) {
        Deque<String> values =
                new ArrayDeque<>();
    }
}

Why `ArrayDeque` Again?

In the previous lesson, we used:

Queue<String> queue =
        new ArrayDeque<>();

Now:

Deque<String> deque =
        new ArrayDeque<>();

The implementation is the same:

ArrayDeque

but the abstraction exposed to the code is different।

As a Queue, we mainly use one end for insertion and the other for removal।

As a Deque, we intentionally use both ends।

Adding at the Front

Use:

addFirst(...)

Example:

Deque<String> values =
        new ArrayDeque<>();

values.addFirst(
        "Java"
);

Structure:

Front
↓
Java

Then:

values.addFirst(
        "Backend"
);

Now:

Front
↓
Backend
Java
↑
Back

Adding at the Back

Use:

addLast(...)

Example:

values.addLast(
        "System Design"
);

Now:

Front
↓
Backend
Java
System Design
↑
Back

`addFirst()` and `addLast()`

Core idea:

addFirst(value)
→ add at front

addLast(value)
→ add at back

`offerFirst()` and `offerLast()`

Deque also provides:

offerFirst(...)
offerLast(...)

These are analogous to queue-style offer() operations।

Example:

deque.offerFirst(
        "A"
);

deque.offerLast(
        "B"
);

Result:

A B

Add vs Offer

Like Queue, Deque has two method families।

For insertion:

addFirst()
offerFirst()

addLast()
offerLast()

With a capacity-restricted implementation:

offer...

can report inability to insert through a boolean result।

For ordinary ArrayDeque, capacity is managed dynamically, so both normally succeed unless another restriction is violated।

Removing from the Front

Use:

removeFirst()

Example:

Deque<String> values =
        new ArrayDeque<>();

values.addLast(
        "A"
);

values.addLast(
        "B"
);

values.addLast(
        "C"
);

String first =
        values.removeFirst();

Now:

first = "A"

remaining:

B C

Removing from the Back

Use:

removeLast()

Example:

String last =
        values.removeLast();

If current deque is:

B C

then:

last = "C"

remaining:

Empty Deque and `removeFirst()`

If the deque is empty:

deque.removeFirst();

throws:

NoSuchElementException

Same idea for:

removeLast();

Safer Removal with `pollFirst()`

Use:

pollFirst()

to remove the first element or return null if empty।

Example:

String value =
        deque.pollFirst();

`pollLast()`

Likewise:

String value =
        deque.pollLast();

removes the last element or returns:

null

when empty।

Removal Method Pairs

Remember:

Front:

removeFirst()
→ throws when empty

pollFirst()
→ returns null when empty

and:

Back:

removeLast()
→ throws when empty

pollLast()
→ returns null when empty

Inspecting the Front

Use:

peekFirst()

Example:

String first =
        deque.peekFirst();

It does not remove the element।

Inspecting the Back

Use:

peekLast()

Example:

String last =
        deque.peekLast();

Again, no removal occurs।

Empty Inspection

If empty:

peekFirst()

returns:

null

and:

peekLast()

also returns:

null

Complete Front and Back Example

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {

    public static void main(String[] args) {
        Deque<String> courses =
                new ArrayDeque<>();

        courses.addLast(
                "Java"
        );

        courses.addLast(
                "Backend"
        );

        courses.addFirst(
                "Programming Fundamentals"
        );

        System.out.println(
                "First: "
                + courses.peekFirst()
        );

        System.out.println(
                "Last: "
                + courses.peekLast()
        );

        System.out.println(
                "Removed first: "
                + courses.pollFirst()
        );

        System.out.println(
                "Removed last: "
                + courses.pollLast()
        );
    }
}

Possible output:

First: Programming Fundamentals
Last: Backend
Removed first: Programming Fundamentals
Removed last: Backend

Deque as a Queue

A Deque can behave like a normal FIFO queue।

Add to back:

deque.offerLast(
        value
);

Remove from front:

deque.pollFirst();

Conceptually:

offerLast()
      ↓
[A] [B] [C]
 ↑
pollFirst()

FIFO:

First inserted
First removed

Queue-Style Example

Deque<String> tasks =
        new ArrayDeque<>();

tasks.offerLast(
        "Task 1"
);

tasks.offerLast(
        "Task 2"
);

tasks.offerLast(
        "Task 3"
);

System.out.println(
        tasks.pollFirst()
);

System.out.println(
        tasks.pollFirst()
);

Output:

Task 1
Task 2

What Is a Stack?

A Stack is a structure where the most recently added item is removed first।

This is:

LIFO

meaning:

Last In, First Out

Stack Analogy

Imagine plates stacked on top of each other।

Top
 ↓
[ Plate C ]
[ Plate B ]
[ Plate A ]

Plate C was added last।

It is removed first।

Stack Operations

Traditional stack vocabulary:

push
pop
peek

Meaning:

push → add to top
pop  → remove from top
peek → inspect top

Using `Deque` as a Stack

Java's Deque interface directly supports:

push(...)
pop()
peek()

Example:

Deque<String> stack =
        new ArrayDeque<>();

`push()`

stack.push(
        "Java"
);

Then:

stack.push(
        "Backend"
);

Then:

stack.push(
        "System Design"
);

Conceptually:

Top
↓
System Design
Backend
Java

`pop()`

String value =
        stack.pop();

returns:

System Design

because it was pushed last।

Now:

Backend
Java

remain।

`peek()`

String value =
        stack.peek();

returns the top element without removing it।

Complete Stack Example

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {

    public static void main(String[] args) {
        Deque<String> stack =
                new ArrayDeque<>();

        stack.push(
                "Java"
        );

        stack.push(
                "Backend"
        );

        stack.push(
                "System Design"
        );

        System.out.println(
                stack.pop()
        );

        System.out.println(
                stack.pop()
        );

        System.out.println(
                stack.pop()
        );
    }
}

Output:

System Design
Backend
Java

That is LIFO।

`push()` and `pop()` Use the Front

For Deque, stack operations conceptually correspond to:

push(value)
≈ addFirst(value)

pop()
≈ removeFirst()

peek()
≈ peekFirst()

This is useful to know because Stack behavior is implemented using one end of the deque।

Empty Stack Behavior

If:

Deque<String> stack =
        new ArrayDeque<>();

then:

stack.pop();

throws:

NoSuchElementException

But:

stack.peek();

returns:

null

Safer Stack Removal

You can use:

pollFirst()

instead of:

pop()

if empty-stack behavior should return null rather than throw।

Example:

String value =
        stack.pollFirst();

`Stack` Class Exists

Java also has:

java.util.Stack

Example:

Stack<String> stack =
        new Stack<>();

It is an older class।

Modern Java code normally prefers:

Deque<E>

with:

ArrayDeque<E>

for ordinary stack behavior।

Why Prefer `Deque` Over Legacy `Stack`?

The legacy Stack class extends:

Vector

which brings older design decisions and operations that are not necessary for a simple stack abstraction।

Modern Java APIs recommend using Deque implementations for LIFO stack behavior।

So prefer:

Deque<String> stack =
        new ArrayDeque<>();

instead of:

Stack<String> stack =
        new Stack<>();

for new ordinary code।

Stack vs Queue

Compare:

Queue

First In
First Out

Example:

A added
B added
C added

Removal order:
A B C

Stack

Last In
First Out

Example:

A pushed
B pushed
C pushed

Removal order:
C B A

Same `ArrayDeque`, Different Semantics

FIFO:

Deque<String> queue =
        new ArrayDeque<>();

queue.offerLast(
        "A"
);

queue.offerLast(
        "B"
);

queue.pollFirst();

LIFO:

Deque<String> stack =
        new ArrayDeque<>();

stack.push(
        "A"
);

stack.push(
        "B"
);

stack.pop();

Same underlying implementation।

Different operations communicate different intent।

Pick One Vocabulary

When using a deque as a queue, prefer consistent queue-style vocabulary:

offerLast()
pollFirst()
peekFirst()

or simply:

offer()
poll()
peek()

when declared as Queue.

When using it as a stack:

push()
pop()
peek()

Do not unnecessarily mix styles।

Why Consistency Matters

This technically works:

stack.push(
        "A"
);

stack.removeFirst();

because both operate at the front।

But:

push()
pop()

better communicate:

This structure is being used as a stack.

Readable code should reveal the chosen abstraction।

Practical Stack Use Case — Undo History

Imagine a text editor।

User actions:

Type "Hello"
Delete word
Change title

The most recent action should be undone first।

That is LIFO।

Deque<String> history =
        new ArrayDeque<>();

Push actions:

history.push(
        "Type Hello"
);

history.push(
        "Delete word"
);

history.push(
        "Change title"
);

Undo:

String lastAction =
        history.pop();

returns:

Change title

Undo Example

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {

    public static void main(String[] args) {
        Deque<String> history =
                new ArrayDeque<>();

        history.push(
                "Created course"
        );

        history.push(
                "Changed title"
        );

        history.push(
                "Published course"
        );

        undo(
                history
        );

        undo(
                history
        );
    }

    static void undo(
            Deque<String> history
    ) {
        String action =
                history.pollFirst();

        if (
                action == null
        ) {
            System.out.println(
                    "Nothing to undo."
            );

            return;
        }

        System.out.println(
                "Undo: "
                + action
        );
    }
}

Output:

Undo: Published course
Undo: Changed title

Stack Use Case — Browser History Concept

Suppose you visit:

Page A
Page B
Page C

Press Back।

You want to return to:

Page B

Then again:

Page A

A stack-like model naturally tracks previous states।

Real browser history is more complex, often involving forward history too, but the stack abstraction helps explain the basic idea।

Two Stacks for Undo and Redo

Conceptually:

Undo stack
Redo stack

When an action occurs:

push onto undo
clear redo

Undo:

pop undo
push onto redo

Redo:

pop redo
push onto undo

This is a common data-structure design pattern।

Deque Use Case — Sliding Window

Sometimes algorithms maintain a moving range of values and need to remove data from both ends।

A Deque can support:

Remove expired value from front
Add new value at back

More advanced algorithms may also remove values from the back based on comparisons।

We will revisit this kind of reasoning in the Algorithms module।

Deque Use Case — Recent Items

Suppose we want to keep at most three recently viewed courses।

New course goes to the front:

recent.addFirst(
        course
);

If size exceeds 3:

recent.removeLast();

Complete Recent Items Example

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {

    private static final int MAX_RECENT =
            3;

    public static void main(String[] args) {
        Deque<String> recent =
                new ArrayDeque<>();

        view(
                recent,
                "Java"
        );

        view(
                recent,
                "Backend"
        );

        view(
                recent,
                "System Design"
        );

        view(
                recent,
                "Algorithms"
        );

        System.out.println(
                recent
        );
    }

    static void view(
            Deque<String> recent,
            String course
    ) {
        recent.addFirst(
                course
        );

        if (
                recent.size()
                > MAX_RECENT
        ) {
            recent.removeLast();
        }
    }
}

Conceptual result:

Algorithms
System Design
Backend

Java was the oldest item, so it was removed from the back।

Deque for Palindrome Checking

We can use both ends of a Deque।

Suppose:

LEVEL

To check palindrome:

Compare first and last
Remove both
Repeat

Example

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;
}

Is This the Only Way to Check Palindrome?

No।

For strings or arrays, two indexes are often simpler and require less extra storage।

Example:

left
right

But the Deque version demonstrates why double-ended operations can be useful।

Stack Use Case — Balanced Brackets

Suppose:

(a + b)

or:

[(a + b) * c]

Opening brackets must be closed in reverse order।

Example:

[
(

Then closing order should be:

)
]

This is LIFO।

A stack is therefore natural।

Simple Parentheses Example

For only:

(
)

we can use a counter։

But for multiple bracket types:

()
[]
{}

a stack is more expressive।

Bracket Matching Example

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 (
                    current == '('
                    || current == '['
                    || current == '{'
            ) {
                stack.push(
                        current
                );

                continue;
            }

            if (
                    current == ')'
                    || current == ']'
                    || current == '}'
            ) {
                if (
                        stack.isEmpty()
                ) {
                    return false;
                }

                char opening =
                        stack.pop();

                if (
                        !matches(
                                opening,
                                current
                        )
                ) {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }

    static boolean matches(
            char opening,
            char closing
    ) {
        return opening == '('
                && closing == ')'
                || opening == '['
                && closing == ']'
                || opening == '{'
                && closing == '}';
    }
}

Why `stack.isEmpty()` at the End?

Input:

(((

never encounters mismatched closing brackets।

But three opening brackets remain।

So:

return stack.isEmpty();

ensures every opening bracket was matched।

Stack and Function Calls

The term:

Call stack

that we learned during recursion uses stack-like behavior।

When methods are called:

main
→ first
→ second
→ third

the most recent call:

third

finishes first।

Then:

second
first
main

This is LIFO।

That is why recursion and stacks are closely connected conceptually।

Explicit Stack vs Recursive Call Stack

Some recursive algorithms can be rewritten using an explicit stack:

Deque<Node> stack =
        new ArrayDeque<>();

instead of relying on method recursion।

This can provide more control over memory and traversal behavior।

We will revisit this with trees and algorithms।

`ArrayDeque` and Null

As with the previous lesson:

ArrayDeque

does not permit:

null

Example:

deque.addFirst(
        null
);

throws:

NullPointerException

Avoid null elements।

Duplicate Values Are Allowed

Deque<String> values =
        new ArrayDeque<>();

values.addLast(
        "A"
);

values.addLast(
        "A"
);

This is valid।

Deque does not enforce uniqueness।

`size()`

You can inspect element count:

deque.size();

`isEmpty()`

Check emptiness:

deque.isEmpty();

`clear()`

Remove everything:

deque.clear();

Iteration Order

When iterating normally:

for (
        String value
        : deque
) {
    System.out.println(
            value
    );
}

elements are traversed from first to last according to the deque's current order।

Descending Iteration

Deque also provides:

descendingIterator()

which traverses from the opposite direction।

Example:

Iterator<String> iterator =
        deque.descendingIterator();

Then:

while (
        iterator.hasNext()
) {
    System.out.println(
            iterator.next()
    );
}

This is useful when reverse traversal is required without modifying the deque।

Required Import for Iterator

import java.util.Iterator;

Example:

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;

Do Not Overuse Deque

A Deque is useful when:

Both ends matter
Queue behavior matters
Stack behavior matters

If you simply need:

Indexed ordered elements

a List may be a clearer abstraction।

Collection Choice by Intent

Ask:

Need index-based ordered access?
→ List

Need uniqueness?
→ Set

Need key-value lookup?
→ Map

Need FIFO processing?
→ Queue

Need both ends?
→ Deque

Need LIFO?
→ Deque used as Stack

Common Beginner Mistake 1 — Thinking Deque Is Always FIFO

A deque is more general than a queue।

You decide how to use its ends।

Example:

addFirst()
removeFirst()

behaves LIFO-like।

While:

addLast()
removeFirst()

behaves FIFO।

Common Beginner Mistake 2 — Mixing Ends Accidentally

Suppose your intended FIFO logic is:

offerLast(...)
pollFirst()

but you accidentally use:

pollLast()

Then your behavior becomes LIFO-like।

Be explicit about which end is:

Input
Output

Common Beginner Mistake 3 — Mixing Stack Vocabulary

Avoid:

stack.push(
        value
);

stack.removeLast();

This is conceptually inconsistent।

Prefer:

push()
pop()
peek()

for stack semantics।

Common Beginner Mistake 4 — Using Legacy `Stack`

For new code, do not default to:

Stack<T>

Prefer:

Deque<T> stack =
        new ArrayDeque<>();

unless there is a specific compatibility reason।

Common Beginner Mistake 5 — Assuming `pop()` Returns Null

It does not।

On empty deque:

pop()

throws:

NoSuchElementException

If nullable empty-state behavior is desired:

pollFirst()

is available।

Common Beginner Mistake 6 — Forgetting Stack Order

Push:

A
B
C

Pop order:

C
B
A

not:

A
B
C

Common Beginner Mistake 7 — Wrong Undo Direction

Undo should normally reverse the most recent action first।

That means:

LIFO

not FIFO।

A queue is the wrong abstraction for normal undo history।

Common Beginner Mistake 8 — Using a Deque When Richer Modeling Is Needed

A deque can hold jobs:

Deque<Job>

but it should not become a replacement for application concepts such as:

Job lifecycle
Persistence
Retry state
Ownership
Concurrency rules

The collection only models ordering and storage behavior।

Practical Example — Work Queue and Undo Stack

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {

    public static void main(String[] args) {
        Deque<String> workQueue =
                new ArrayDeque<>();

        workQueue.offerLast(
                "Send email"
        );

        workQueue.offerLast(
                "Generate invoice"
        );

        workQueue.offerLast(
                "Update analytics"
        );

        System.out.println(
                workQueue.pollFirst()
        );

        Deque<String> undoStack =
                new ArrayDeque<>();

        undoStack.push(
                "Create course"
        );

        undoStack.push(
                "Rename course"
        );

        undoStack.push(
                "Publish course"
        );

        System.out.println(
                "Undo: "
                + undoStack.pop()
        );
    }
}

Output:

Send email
Undo: Publish course

Same implementation:

ArrayDeque

different semantics:

Queue → FIFO
Stack → LIFO

Practice 1 — Add to Both Ends

Create:

Deque<Integer> values =
        new ArrayDeque<>();

and produce this order:

10 20 30

using both addFirst() and addLast()।

Possible Solution

values.addFirst(
        20
);

values.addFirst(
        10
);

values.addLast(
        30
);

Practice 2 — Remove from Both Ends

Given:

10 20 30 40

remove:

then:

Solution

values.pollFirst();
values.pollLast();

Practice 3 — Predict the Output

Deque<String> values =
        new ArrayDeque<>();

values.addLast(
        "A"
);

values.addLast(
        "B"
);

values.addFirst(
        "C"
);

System.out.println(
        values.pollFirst()
);

System.out.println(
        values.pollLast()
);

Answer

C
B

A remains।

Practice 4 — Stack Order

Given:

Deque<Integer> stack =
        new ArrayDeque<>();

stack.push(
        10
);

stack.push(
        20
);

stack.push(
        30
);

What does the first pop() return?

Answer

Practice 5 — Implement Undo

Implement:

static String undo(
        Deque<String> history
)

Return:

"Nothing to undo"

if empty।

Solution

static String undo(
        Deque<String> history
) {
    String action =
            history.pollFirst();

    if (
            action == null
    ) {
        return "Nothing to undo";
    }

    return action;
}

Practice 6 — FIFO with Deque

Implement:

static void processAll(
        Deque<String> tasks
)

using:

add at back
remove at front

Assume queue is already populated।

Solution

static void processAll(
        Deque<String> tasks
) {
    while (
            !tasks.isEmpty()
    ) {
        String task =
                tasks.pollFirst();

        System.out.println(
                task
        );
    }
}

Practice 7 — Recent Three Items

Implement:

static void addRecent(
        Deque<String> recent,
        String item
)

where newest items are at the front and maximum size is 3।

Solution

static void addRecent(
        Deque<String> recent,
        String item
) {
    recent.addFirst(
            item
    );

    if (
            recent.size() > 3
    ) {
        recent.removeLast();
    }
}

Practice 8 — Choose FIFO or LIFO

Which ordering fits each situation?

A

Customer support tickets processed in arrival order.

B

Undo most recent text edit.

C

Breadth-first traversal worklist.

D

Method call stack.

Answers

A → FIFO
B → LIFO
C → FIFO
D → LIFO

Practice 9 — Choose Method

You want to inspect the back element without removing it।

Which method?

Answer

peekLast()

Practice 10 — Choose Method

You want to remove the front and receive null if empty।

Answer

pollFirst()

Practice 11 — Why Is This Wrong?

Deque<String> stack =
        new ArrayDeque<>();

stack.push(
        "A"
);

stack.push(
        "B"
);

System.out.println(
        stack.pollLast()
);

Answer

If the intent is stack behavior, pollLast() removes from the opposite end and therefore violates the intended LIFO operation sequence।

Use:

stack.pop();

or:

stack.pollFirst();

depending on desired empty behavior।

Practice 12 — Legacy Choice

Which is preferred for new ordinary stack code?

Stack<String>

or:

Deque<String> stack =
        new ArrayDeque<>();

Answer

Prefer:

Deque<String> stack =
        new ArrayDeque<>();

True or False

Deque means Double-Ended Queue.
A Deque can add values at both ends.
pollFirst() removes from the back.
peekLast() removes the last element.
ArrayDeque can implement FIFO behavior.
ArrayDeque can implement LIFO behavior.
LIFO means Last In, First Out.
push() adds to the stack top.
pop() removes the oldest stack item.
Deque is generally preferred over legacy Stack for new stack code.
ArrayDeque allows null.
A stack is useful for undo behavior.
A queue is usually appropriate for method call-stack behavior.
A Deque can support algorithms needing both ends.

Answers

1. True
2. True
3. False
4. False
5. True
6. True
7. True
8. True
9. False
10. True
11. False
12. True
13. False
14. True

Knowledge Check

Question 1

What does Deque mean?

Question 2

What is the difference between Queue and Deque conceptually?

Question 3

What does addFirst() do?

Question 4

What does pollLast() do?

Question 5

What does LIFO mean?

Question 6

What are the three common stack operations?

Question 7

How does push() relate to addFirst()?

Question 8

Why is ArrayDeque useful for both Queue and Stack behavior?

Question 9

Why is Deque normally preferred over the legacy Stack class?

Question 10

What kind of processing naturally fits a Stack?

Question 11

What kind of processing naturally fits a FIFO Queue?

Question 12

Why should queue-style and stack-style vocabulary not be mixed unnecessarily?

Knowledge Check Answers

Answer 1

Deque means:

Double-Ended Queue

It allows operations at both the front and back।

Answer 2

A normal Queue mainly expresses ordered processing from one insertion side to one removal side, while a Deque explicitly supports insertion and removal at both ends।

Answer 3

It inserts an element at the front of the deque।

Answer 4

It removes and returns the last element, or returns null if the deque is empty।

Answer 5

LIFO means:

Last In, First Out

The most recently inserted item is processed first।

Answer 6

Common stack operations are:

push
pop
peek

Answer 7

For a Deque, push() inserts at the front and is conceptually similar to addFirst()।

Answer 8

Because ArrayDeque efficiently supports operations at both ends, allowing it to express both FIFO and LIFO semantics depending on which methods are used।

Answer 9

The older Stack class extends Vector and carries legacy design choices, while Deque provides a modern abstraction directly suited to stack operations।

Answer 10

Examples include:

Undo
Expression parsing
Bracket matching
Depth-first traversal
Recursive-call-style processing

Answer 11

Examples include:

Arrival-order tasks
Background jobs
Request processing
Breadth-first traversal

Answer 12

Consistent vocabulary communicates the intended abstraction and reduces mistakes about which end should be used।

Lesson Summary

এই lesson-এ আমরা Deque, stack behavior, এবং ArrayDeque-এর flexibility শিখেছি।

We learned:

Deque<E> means Double-Ended Queue
A Deque supports operations at both front and back
ArrayDeque is a common implementation
addFirst() and addLast() insert at specific ends
pollFirst() and pollLast() safely remove from specific ends
peekFirst() and peekLast() inspect without removal
Deque can implement FIFO behavior
Deque can implement LIFO stack behavior
LIFO means Last In, First Out
Stack vocabulary is push(), pop(), and peek()
push() and pop() operate at the Deque's front
Modern Java normally prefers Deque with ArrayDeque over legacy Stack
ArrayDeque does not accept null
Stack semantics fit undo, parsing, and depth-first-style processing
Queue semantics fit arrival-order work and breadth-first processing
Both-end access enables additional algorithms and bounded recent-history structures
The same concrete data structure can express different abstractions depending on how it is used
Method vocabulary should consistently reflect the intended abstraction

The key relationship is:

ArrayDeque
   |
   +---- Queue behavior
   |     FIFO
   |
   +---- Deque behavior
   |     both ends
   |
   +---- Stack behavior
         LIFO

The important design principle is:

Choose the abstraction that communicates
how the data is supposed to behave.

Module 5 Adjustment

The new Core Data Structures additions are now complete:

Queues and FIFO Processing
Deque, Stack, and ArrayDeque

The previously written lessons on:

Iteration and Collection Operations
Choosing the Right Collection
Module Practice and Assessment

can remain as they are, with only a small future assessment adjustment if we want Queue and Deque questions included।

Next Module

পরবর্তী genuinely new content:

Module 6 — Algorithms and Problem Solving with Java

Lesson 1 — Understanding Algorithmic Complexity and Big-O

আমরা শিখব:

What an algorithm is
Why performance matters
Input size
Time complexity
Space complexity
Big-O notation
O(1)
O(log n)
O(n)
O(n log n)
O(n²)
Ignoring constants
Best, average, and worst-case intuition
How Java collection operations relate to complexity
Practical engineering reasoning instead of mathematical proofs

Lesson Overview

What Is a Deque?

Pronunciation

Java Deque<E>

Required Imports

Why ArrayDeque Again?

Adding at the Front

Adding at the Back

addFirst() and addLast()

offerFirst() and offerLast()

Add vs Offer

Removing from the Front

Removing from the Back

Empty Deque and removeFirst()

Safer Removal with pollFirst()

pollLast()

Removal Method Pairs

Inspecting the Front

Inspecting the Back

Empty Inspection

Complete Front and Back Example

Deque as a Queue

Queue-Style Example

What Is a Stack?

Stack Analogy

Stack Operations

Using Deque as a Stack

push()

pop()

peek()

Complete Stack Example

push() and pop() Use the Front

Empty Stack Behavior

Safer Stack Removal

Stack Class Exists

Why Prefer Deque Over Legacy Stack?

Stack vs Queue

Queue

Stack

Same ArrayDeque, Different Semantics

Pick One Vocabulary

Why Consistency Matters

Practical Stack Use Case — Undo History

Undo Example

Stack Use Case — Browser History Concept

Two Stacks for Undo and Redo

Deque Use Case — Sliding Window

Deque Use Case — Recent Items

Complete Recent Items Example

Deque for Palindrome Checking

Example

Is This the Only Way to Check Palindrome?

Stack Use Case — Balanced Brackets

Simple Parentheses Example

Bracket Matching Example

Why stack.isEmpty() at the End?

Stack and Function Calls

Explicit Stack vs Recursive Call Stack

ArrayDeque and Null

Duplicate Values Are Allowed

size()

isEmpty()

clear()

Iteration Order

Descending Iteration

Required Import for Iterator

Do Not Overuse Deque

Collection Choice by Intent

Common Beginner Mistake 1 — Thinking Deque Is Always FIFO

Common Beginner Mistake 2 — Mixing Ends Accidentally

Common Beginner Mistake 3 — Mixing Stack Vocabulary

Common Beginner Mistake 4 — Using Legacy Stack

Common Beginner Mistake 5 — Assuming pop() Returns Null

Common Beginner Mistake 6 — Forgetting Stack Order

Common Beginner Mistake 7 — Wrong Undo Direction

Common Beginner Mistake 8 — Using a Deque When Richer Modeling Is Needed

Practical Example — Work Queue and Undo Stack

Practice 1 — Add to Both Ends

Possible Solution

Practice 2 — Remove from Both Ends

Java `Deque<E>`

Why `ArrayDeque` Again?

`addFirst()` and `addLast()`

`offerFirst()` and `offerLast()`

Empty Deque and `removeFirst()`

Safer Removal with `pollFirst()`

`pollLast()`

Using `Deque` as a Stack

`push()`

`pop()`

`peek()`

`push()` and `pop()` Use the Front

`Stack` Class Exists

Why Prefer `Deque` Over Legacy `Stack`?

Same `ArrayDeque`, Different Semantics

Why `stack.isEmpty()` at the End?

`ArrayDeque` and Null

`size()`

`isEmpty()`

`clear()`

Common Beginner Mistake 4 — Using Legacy `Stack`

Common Beginner Mistake 5 — Assuming `pop()` Returns Null