0Pricing
Java Academy · Lezione

Operazioni su Deque: stack e queue

Utilizzi LinkedList come Deque per implementare il comportamento di stack (push/pop) e queue (offer/poll).

Operazioni su Deque: stack e queue è una lezione Java Academy gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Java Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Java Academy include 4 lezioni in totale.

Deque: coda a doppia estremità

Una Deque (Double-Ended Queue, coda a doppia estremità) consente inserimenti e rimozioni a entrambe le estremità. L'interfaccia Deque di Java è implementata da LinkedList e ArrayDeque.

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

Deque<String> deque = new ArrayDeque<>();
deque.addFirst("A"); // front
deque.addLast("B");  // back
deque.addFirst("Z"); // new front

System.out.println(deque); // [Z, A, B]

ArrayDeque e LinkedList come Deque

ArrayDeque è generalmente preferibile a LinkedList come Deque:

  • Nessun overhead di nodi per ogni elemento
  • Località della cache migliore
  • Operazioni di stack e coda leggermente più veloci

Scelga LinkedList solo quando è necessaria anche l'interfaccia List.

Operazioni di stack con Deque

Utilizzi push (addFirst) e pop (removeFirst) per simulare uno stack LIFO. Eviti la classe Stack obsoleta: è sincronizzata e non è più consigliata.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);

System.out.println(stack.pop());  // 3
System.out.println(stack.peek()); // 2 (no removal)
System.out.println(stack.pop());  // 2

Operazioni di coda con Deque

Utilizzi offer (addLast) e poll (removeFirst) per simulare una coda FIFO. offer restituisce false in caso di errore, mentre add genera un'eccezione.

Deque<String> queue = new ArrayDeque<>();
queue.offer("task1");
queue.offer("task2");
queue.offer("task3");

System.out.println(queue.poll());  // task1
System.out.println(queue.poll());  // task2
System.out.println(queue.size());  // 1

Tabella di riferimento dei metodi Deque

Deque fornisce due famiglie di metodi: una genera eccezioni, l'altra restituisce valori speciali:

  • addFirst/addLast rispetto a offerFirst/offerLast
  • removeFirst/removeLast rispetto a pollFirst/pollLast
  • getFirst/getLast rispetto a peekFirst/peekLast

Preferisca la famiglia offer/poll/peek per evitare eccezioni sulle deque vuote.

Esempio reale: annullamento e ripristino con due stack

Un caso d'uso classico di Deque: la cronologia delle operazioni da annullare è uno stack. Il ripristino utilizza un altro stack.

Deque<String> undo = new ArrayDeque<>();
Deque<String> redo = new ArrayDeque<>();

undo.push("type 'Hello'");
undo.push("type ' World'");

String action = undo.pop();
System.out.println("Undone: " + action); // type ' World'
redo.push(action);

System.out.println("Redo top: " + redo.peek()); // type ' World'

Verifica dei palindromi con Deque

Le deque rendono elegante la verifica dei palindromi: consentono di confrontare simultaneamente i caratteri alle due estremità.

Deque<Character> deque = new ArrayDeque<>();
for (char c : "racecar".toCharArray()) deque.add(c);

boolean isPalindrome = true;
while (deque.size() > 1) {
    if (!deque.pollFirst().equals(deque.pollLast())) {
        isPalindrome = false;
        break;
    }
}
System.out.println(isPalindrome); // true

BFS con una coda

La ricerca in ampiezza utilizza una coda. ArrayDeque è la scelta standard per la BFS nella programmazione competitiva e nell'attraversamento dei grafi.

import java.util.*;

// BFS on a simple adjacency list
Map<Integer,List<Integer>> graph = Map.of(
    1, List.of(2,3),
    2, List.of(4),
    3, List.of(4),
    4, List.of()
);
Deque<Integer> queue = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
queue.offer(1);
while (!queue.isEmpty()) {
    int node = queue.poll();
    if (visited.add(node)) {
        System.out.print(node + " ");
        queue.addAll(graph.get(node));
    }
}

DFS con uno stack

La ricerca in profondità utilizza uno stack. Anche in questo caso, preferisca ArrayDeque alla classe Stack obsoleta.

Deque<Integer> stack = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
stack.push(1);
while (!stack.isEmpty()) {
    int node = stack.pop();
    if (visited.add(node)) {
        System.out.print(node + " ");
        // push neighbors (will be processed in reverse order)
        List<Integer> neighbors = List.of(2, 3); // simplified
        for (int n : neighbors) if (!visited.contains(n)) stack.push(n);
    }
}

Deque con capacità limitata e controllo delle dimensioni

ArrayDeque cresce dinamicamente, ma è possibile imporre manualmente una capacità per simulare un buffer di dimensioni limitate:

Deque<Integer> buffer = new ArrayDeque<>();
int MAX = 3;

for (int i = 1; i <= 5; i++) {
    if (buffer.size() >= MAX) {
        buffer.pollFirst(); // drop oldest
    }
    buffer.offerLast(i);
}
System.out.println(buffer); // [3, 4, 5]

Note sulle prestazioni

ArrayDeque utilizza un array circolare che raddoppia quando è pieno. Il costo ammortizzato di tutte le operazioni è O(1). Supera LinkedList nella maggior parte dei benchmark grazie all'efficienza della cache. Non esegua mai la sincronizzazione manualmente: utilizzi ConcurrentLinkedDeque o una coda bloccante per la concorrenza.

Verifica rapida

Quale classe dovrebbe preferire alla classe Stack obsoleta per le operazioni LIFO?

Riepilogo: operazioni Deque

Punti chiave:

  • Deque consente inserimenti e rimozioni O(1) a entrambe le estremità
  • ArrayDeque è preferibile a LinkedList per l'uso esclusivo come stack o coda
  • push/pop → stack LIFO; offer/poll → coda FIFO
  • Usi classici: annullamento/ripristino, BFS/DFS, finestra scorrevole, verifica dei palindromi
  • Eviti le classi Stack e Queue obsolete

Domande Frequenti

La lezione «Operazioni su Deque: stack e queue» è gratuita?

Sì — il testo completo di «Operazioni su Deque: stack e queue» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Java Academy, passa a CoddyKit PRO. Il corso Java Academy include 4 lezioni in totale.

Cosa imparerò in «Operazioni su Deque: stack e queue»?

Utilizzi LinkedList come Deque per implementare il comportamento di stack (push/pop) e queue (offer/poll). Eserciti Java Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare Java Academy?

Non è richiesta alcuna esperienza precedente. Java Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.

Quanto tempo richiede la lezione «Operazioni su Deque: stack e queue»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione Java Academy?

Sì. Ogni lezione Java Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

  1. Internals di LinkedList
  2. Operazioni su Deque: stack e queue
  3. LinkedList e ArrayList a confronto
  4. PriorityQueue per l'elaborazione ordinata
← Torna a Java Academy