منشورBEG-030-L05

الطوابير (Queues) والطوابير ثنائية الطرف (deques)

الدرس 5 من 9
10 دقيقة قراءة
مبتدئ

في هذا الدرس 11 موضوعات

Lesson Overview
Learning Objectives
Written Explanation
Examples
Backend Insight
Common Mistakes
Exercises
Mini Challenge
Summary & Next Lesson
References
التطبيق

هذا الدرس متاح حاليًا باللغة الإنجليزية فقط، ولم تُنشر نسخته العربية بعد.

Lesson Overview

So far our collections answered "what is stored?" and "what goes with this key?". A Queue answers a different question: who is next? It models a waiting line, such as customers at a counter, print jobs, or tasks waiting for a worker. The rule is first in, first out (FIFO): the first element added is the first one taken out.

A Deque (pronounced "deck", short for double-ended queue) works at both ends. Used from one end it is also a stack: last in, first out, like a pile of plates. We also meet PriorityQueue, which hands out the smallest element first instead of the oldest.

This lesson builds on Lessons 1 to 4, and on exceptions from BEG-029: some queue methods return a special value when the line is empty, while others throw.

Learning Objectives

By the end of this lesson you will be able to:

Use offer, poll, and peek on a Queue and predict the FIFO order.
Explain what poll and peek return on an empty queue, and how remove() and element() differ.
Declare Queue<String> q = new ArrayDeque<>(); and say why ArrayDeque is a good default queue.
Use a Deque as a stack with push, pop, and peek.
Use addFirst, addLast, pollFirst, and pollLast to work at both ends.
Describe how PriorityQueue orders elements and the one surprise in how it prints.

Written Explanation

The `Queue` interface

A Queue holds elements before processing. The main methods, in the "return a special value" form:

Method	What it does	If the queue is empty
`offer(x)`	Adds `x` at the back	(not applicable)
`poll()`	Removes and returns the front element	returns `null`
`peek()`	Returns the front element, without removing it	returns `null`
`size()`, `isEmpty()`	As usual

There is a second family with the same jobs: add(x), remove(), and element(). They behave the same on success, but when the queue is empty, remove() and element() throw a NoSuchElementException instead of returning null. So the choice is between "tell me with null" and "fail loudly". We use offer, poll, and peek in this lesson because "empty" is a normal state of a waiting line, not an error.

Because poll returns null for an empty queue, never put null into a queue: you would not be able to tell an element from "empty". ArrayDeque enforces this and throws a NullPointerException if you try.

`ArrayDeque`: the default queue

Declare by interface:

java

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

ArrayDeque stores elements in a resizable array and works well at both ends. Its documentation says it is likely to be faster than LinkedList when used as a queue, and faster than the old Stack class when used as a stack. LinkedList also implements Queue (and Deque), but ArrayDeque is the usual first choice.

Compared with a list, a queue is deliberately less capable: no get(i), no insert in the middle. The restriction is the point. It tells the reader "this is a waiting line" and prevents anyone cutting in.

The `Deque`: both ends, and a stack

A Deque adds the "other end":

At the front	At the back
`addFirst(x)` / `offerFirst(x)`	`addLast(x)` / `offerLast(x)` (same as `offer`)
`pollFirst()` / `peekFirst()`	`pollLast()` / `peekLast()`

Used as a stack (last in, first out), you push and pop at the front:

Method	Meaning
`push(x)`	Puts `x` on top (same as `addFirst`)
`pop()`	Removes and returns the top. Throws `NoSuchElementException` if empty
`peek()`	Looks at the top without removing it; `null` if empty

Stacks model "undo": the last action you did is the first one undone. The call stack from BEG-014-L05 has the same last-in, first-out shape.

java

Deque<String> undo = new ArrayDeque<>();
undo.push("type A");

In Java, prefer Deque with ArrayDeque over the older Stack class.

`PriorityQueue`: smallest first

A PriorityQueue does not serve in arrival order. It always hands out the least element first, by natural ordering (numbers ascending, strings alphabetical) or by a comparator. Think of an emergency room: the most urgent case is seen first, not the first to arrive.

java

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5); pq.offer(1); pq.offer(8); pq.offer(3);

pq.peek() is 1 and polling repeatedly gives 1 3 5 8. The surprise: printing the queue or looping over it does not give sorted order; the documentation says the iterator is not guaranteed to traverse in any particular order. Only poll/peek respect the priority. Also, contains and remove(x) scan the queue, so use them sparingly.

Which one to pick

Process in arrival order: Queue via ArrayDeque.
Undo, back button, or matching brackets: Deque used as a stack via ArrayDeque.
Most urgent or smallest first: PriorityQueue.
Need both ends: Deque via ArrayDeque.

Concurrent queues for several threads exist (a later topic); none of the classes here is safe for multiple threads at once.

Examples

Example 1: serving customers in arrival order (simple)

java

Queue<String> line = new ArrayDeque<>();
line.offer("Ana"); line.offer("Omar"); line.offer("Lina");
System.out.println(line.peek() + " " + line.size());
System.out.println(line.poll() + " " + line);
while (!line.isEmpty()) System.out.println("serving " + line.poll());
System.out.println(line.poll() + " " + line.peek());
try { line.remove(); }
catch (NoSuchElementException e) { System.out.println("NSEE " + e.getMessage()); }
try { line.offer(null); }
catch (NullPointerException e) { System.out.println("NPE"); }

Output:

text

Ana 3
Ana [Omar, Lina]
serving Omar
serving Lina
null null
NSEE null
NPE

peek showed Ana without removing her. poll removed her. When the queue ran empty, poll and peek gave null, remove() threw, and offer(null) was refused.

Example 2: an undo stack and a deque at both ends (practical)

java

Deque<String> undo = new ArrayDeque<>();
undo.push("type A"); undo.push("type B"); undo.push("delete C");
System.out.println(undo + " top=" + undo.peek());
System.out.println(undo.pop());
System.out.println(undo.pop() + " " + undo);

Deque<Integer> d = new ArrayDeque<>();
d.addLast(1); d.addLast(2); d.addFirst(0);
System.out.println(d + " " + d.peekFirst() + " " + d.peekLast() + " " + d.pollLast());

Output:

text

[delete C, type B, type A] top=delete C
delete C
type B [type A]
[0, 1, 2] 0 2 2

The most recent action sits at the front and is undone first. The second half shows both ends: addFirst(0) put 0 before the others, and pollLast() removed and returned 2. (In the last println, the arguments are evaluated left to right, so the deque is printed before pollLast runs.)

Example 3: priority order versus printed order (realistic)

java

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5); pq.offer(1); pq.offer(8); pq.offer(3);
System.out.println(pq.peek());
System.out.println(pq);
StringBuilder sb = new StringBuilder();
while (!pq.isEmpty()) sb.append(pq.poll()).append(' ');
System.out.println(sb);

PriorityQueue<String> ps = new PriorityQueue<>(List.of("pear", "apple", "fig"));
System.out.println(ps.poll());

Output:

text

1
[1, 3, 8, 5]
1 3 5 8 
apple

The head is correct (1), but [1, 3, 8, 5] is not sorted, because the internal arrangement only guarantees the head. Polling in a loop produced the sorted sequence. This is how you would hand out jobs by urgency, for example: give each job a number and always poll the lowest one.

Backend Insight

Queues are the backbone of backend processing. A web server puts incoming work in a queue for worker threads. A job system holds "send this e-mail" tasks in a queue so a slow mail server does not slow the user's request. Message brokers such as Kafka and RabbitMQ are, at heart, queues that live outside your program and survive restarts. Their delivery rules differ from one product to another, and you will study them in later levels.

What you learn here is the vocabulary: producer adds with offer, consumer takes with poll, "empty" is normal, and order is part of the contract. Stacks show up in the Java runtime itself (the call stack) and in parsers, undo features, and depth-first algorithms. A PriorityQueue powers schedulers where urgent tasks jump ahead. A real production queue needs more: limits on size, persistence, and thread safety. Here we keep it in-memory and single-threaded.

Common Mistakes

Mistake 1: Using `remove()` or `pop()` on a possibly empty queue

They throw NoSuchElementException when empty. If "empty" is a normal case, use poll() and test the result for null, or check isEmpty() first.

Mistake 2: Putting `null` into a queue

ArrayDeque throws a NullPointerException, and with queues that accept null, poll() returning null becomes ambiguous.

Mistake 3: Expecting a `PriorityQueue` to print sorted

Only the head is guaranteed. Poll repeatedly (or sort a copy) to get sorted order.

Mistake 4: Mixing up queue and stack ends

push and pop work at the front of a Deque, while offer adds at the back and poll takes from the front. If you offer and then pop on the same deque, you get first-in-first-out behavior, not a stack. Pick one style per deque.

Mistake 5: Using a `List` as a queue

list.remove(0) on an ArrayList shifts every element, so draining a long list from the front is slow. A queue is the right tool.

Exercises

Try each exercise yourself before opening the solutions.

Level A: Foundation

A1. What does this print?

java

Queue<Integer> q = new ArrayDeque<>();
q.offer(1); q.offer(2); q.poll(); q.offer(3); q.offer(4); q.poll();
System.out.println(q + " " + q.peek());

أظهر الحل A1

A1. [3, 4] 3. After the two polls, 1 and 2 were removed, and 3 and 4 remain; the front is 3.

A2. On an empty queue, what do poll() and remove() do?

أظهر الحل A2

A2. poll() returns null. remove() throws NoSuchElementException.

A3. Which of these is FIFO and which is LIFO: a queue at a bakery, a stack of plates?

أظهر الحل A3

A3. The bakery queue is FIFO; the plates are LIFO.

Level B: Application

B1. Write static List<String> reversed(List<String> in) that uses a Deque as a stack to return the elements in reverse order. Test it with a, b, c.

أظهر الحل B1

B1.

java

static List<String> reversed(List<String> in) {
    Deque<String> st = new ArrayDeque<>();
    for (String s : in) st.push(s);
    List<String> out = new ArrayList<>();
    while (!st.isEmpty()) out.add(st.pop());
    return out;
}

reversed(List.of("a", "b", "c")) returns [c, b, a].

B2. Simulate a round-robin of three players Ana, Omar, Lina for five turns: each turn, take the front player, print the name, and put the player at the back. Which names print?

أظهر الحل B2

B2.

java

Queue<String> players = new ArrayDeque<>(List.of("Ana", "Omar", "Lina"));
for (int turn = 1; turn <= 5; turn++) {
    String p = players.poll();
    System.out.print(p + " ");
    players.offer(p);
}

It prints Ana Omar Lina Ana Omar.

B3. You offer 5, 1, 8, 3 to a PriorityQueue<Integer> and then call peek() and poll() once each. What do they return, and what is the head afterward?

أظهر الحل B3

B3. peek() returns 1 and leaves the queue unchanged; poll() returns 1 and removes it. The new head is 3, the next smallest.

Level C: Challenge

C1. Write static boolean balanced(String s) that checks only round brackets: every ( must be closed by a ) in the right order. Use a stack. Try it on (a(b)c), (() and )(.

أظهر الحل C1

C1.

java

static boolean balanced(String s) {
    Deque<Character> st = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(') st.push(c);
        else if (c == ')') {
            if (st.isEmpty()) return false;
            st.pop();
        }
    }
    return st.isEmpty();
}

Results: true, false (one ( is never closed), false (a ) arrives with nothing to match).

C2. A support desk handles tickets in arrival order, except that "urgent" tickets must be handled first. Describe two designs using only what this lesson teaches, and say which you prefer.

أظهر الحل C2

C2. Design 1: two queues, one for urgent and one for normal tickets; always poll the urgent queue first, and the normal one only when the urgent queue is empty. Design 2: one PriorityQueue where each ticket has a priority number (lower is more urgent), though tickets of equal priority are not guaranteed to come out in arrival order. Design 1 keeps arrival order within each class, so it is preferable when order among equal tickets matters.

Mini Challenge

Build a "print queue" simulator with a Queue<String> of document names:

Offer five documents.
Use a while loop with isEmpty() to "print" each, showing how many documents are still waiting.
After the loop, call poll() once more and print the result, and explain the output in one sentence.
Then use a Deque<String> to keep a "recently printed" history, where the most recent job is shown first (use push), and print the history.

Check your work: documents print in the order offered, the extra poll() prints null, and the history shows the last-printed document first.

Summary & Next Lesson

Key takeaways

A Queue is first in, first out: offer at the back, poll from the front, peek to look.
poll and peek return null when empty; remove(), element(), and pop() throw.
ArrayDeque is the usual queue and stack; never store null in it.
A Deque works at both ends and, with push and pop, acts as a stack.
PriorityQueue serves the smallest element first, but its printed order is not sorted.

Next lesson

The next lesson, "Choosing a collection: decision chart", puts all four families together into one chart you can follow from a requirement to a class.

Self-check

Which method adds to the back of a queue, and which removes from the front?
What does peek() return on an empty queue?
Which end of a Deque do push and pop use?
Why should you not put null in a queue?
Does printing a PriorityQueue show its elements in sorted order?

أظهر الإجابات

offer adds to the back; poll removes from the front.
null.
The front.
poll() and peek() return null for "empty", so a stored null would be ambiguous; ArrayDeque refuses it with a NullPointerException.
No. Only the head is guaranteed to be the smallest; poll repeatedly to get sorted order.

References

Oracle, Java SE 21 API, ArrayDeque. Supports null elements being prohibited, poll/peek returning null when empty versus remove/pop throwing, push as addFirst, and the "likely faster than LinkedList as a queue" statement.
Oracle, Java SE 21 API, PriorityQueue. Supports the least-element head, natural ordering or comparator, no guaranteed iteration order, and null being prohibited.
Oracle, Java SE 21 API, LinkedList. Supports that it implements both List and Deque.
Outputs were produced by compiling and running the examples and solutions with JDK 21. I did not fetch the Queue or Deque interface pages; the "special value versus exception" method families are taken from the ArrayDeque page's behavior of its methods.

التطبيق

طبّق هذا الدرس بمختبر الوحدة وتمارينها واختبارها.

المختبر والتمارين الاختبار

تعليم الدرس كمكتمل اختياري ويمكنك التراجع عنه في أي وقت. يبقى تقدمك محفوظًا في هذا المتصفح.

تابع إلى الدرس التالي

Lesson Overview

Learning Objectives

Written Explanation

The Queue interface

ArrayDeque: the default queue

The Deque: both ends, and a stack

PriorityQueue: smallest first

Which one to pick

Examples

Example 1: serving customers in arrival order (simple)

Example 2: an undo stack and a deque at both ends (practical)

Example 3: priority order versus printed order (realistic)

Backend Insight

Common Mistakes

Mistake 1: Using remove() or pop() on a possibly empty queue

Mistake 2: Putting null into a queue

Mistake 3: Expecting a PriorityQueue to print sorted

Mistake 4: Mixing up queue and stack ends

Mistake 5: Using a List as a queue

Exercises

Level A: Foundation

Level B: Application

Level C: Challenge

Mini Challenge

Summary & Next Lesson

Key takeaways

Next lesson

Self-check

References

التطبيق

The `Queue` interface

`ArrayDeque`: the default queue

The `Deque`: both ends, and a stack

`PriorityQueue`: smallest first

Mistake 1: Using `remove()` or `pop()` on a possibly empty queue

Mistake 2: Putting `null` into a queue

Mistake 3: Expecting a `PriorityQueue` to print sorted

Mistake 5: Using a `List` as a queue