Simulazione reciproca di stack e coda

Implementare una coda usando due pile e una pila usando due code sono classiche domande di progettazione nei colloqui tecnici. Verificano la comprensione degli invarianti di entrambe le strutture dati e la capacità di mantenere la garanzia di una struttura usando le primitive dell'altra. Sono anche un punto di partenza per discutere la complessità ammortizzata.

L'idea fondamentale è questa: le pile sono LIFO e le code sono FIFO. Per effettuare la conversione è necessario invertire l'ordine; trasferire una pila in un'altra pila ripristina l'ordine di inserimento originale, che è FIFO.

L'approccio lazy utilizza una pila inbox per le operazioni di inserimento e una pila outbox per le operazioni di rimozione. Quando viene chiamato dequeue, se outbox è vuota, trasferisca tutti gli elementi da inbox a outbox: questa inversione ripristina l'ordine FIFO. Se outbox non è vuota, estragga direttamente da essa. I trasferimenti avvengono lazy, ammortizzando il costo O(n) del trasferimento su molte operazioni.

Ogni elemento viene trasferito da inbox a outbox al massimo una volta. Quando l'estrazione da outbox è O(1) e i trasferimenti avvengono solo quando outbox è vuota, il lavoro totale per n inserimenti e n rimozioni è al massimo di 2n operazioni sulle pile: O(n) complessivo, ovvero O(1) ammortizzato per operazione. Ciò significa che nel caso peggiore le singole operazioni possono essere O(n), ma la media è O(1).

Implementare una pila con due code è meno naturale, perché le code sono FIFO. L'approccio lazy per la rimozione mantiene una coda principale e una coda temporanea. Durante push, inserisca l'elemento nella coda principale (O(1)). Durante pop o peek, rimuova dalla coda tutti gli elementi tranne l'ultimo e li inserisca nella coda temporanea, salvi l'ultimo elemento, quindi scambi le due code. Il costo è O(n) per ogni rimozione, ma O(1) per ogni inserimento.

Un'implementazione elegante con una sola coda: durante push, inserisca il nuovo elemento, quindi ruoti la coda in modo che il nuovo elemento si trovi all'inizio. Ruotare significa rimuovere e reinserire tutti gli elementi presenti prima dell'inserimento. In questo modo pop e peek hanno costo O(1) (basta rimuovere o consultare l'elemento iniziale). push ha costo O(n): è il compromesso opposto rispetto alla versione con due code.

Per una coda ottenuta da due pile: push O(1), pop/peek O(1) ammortizzato; la preferisca quando le operazioni di pop sono frequenti. Per una pila ottenuta da due code: push O(1), pop O(n); la preferisca quando le operazioni di push sono molto più frequenti delle operazioni di pop. Per una pila ottenuta da una sola coda: push O(n), pop O(1); la preferisca quando prevalgono le operazioni di pop. Esponga chiaramente questi compromessi durante un colloquio per dimostrare di considerare più del semplice fatto che la soluzione funzioni.

Quando gli elementi 1, 2, 3 vengono inseriti in una pila (inbox), si dispongono dal fondo verso la cima nell'ordine 1, 2, 3. Estraendoli tutti e inserendoli in una seconda pila (outbox), l'ordine si inverte: outbox contiene 3 in fondo e 1 in cima. Estraendo gli elementi da outbox si ottengono 1, poi 2, poi 3, esattamente nell'ordine di inserimento FIFO. Ecco perché esattamente due inversioni (due pile) ripristinano il FIFO, mentre una sola pila produrrebbe il comportamento LIFO.

LeetCode 232 è il problema diretto della «coda ottenuta da due pile». La soluzione prevista è il trasferimento lazy in outbox. Durante un colloquio, dichiari che ogni elemento si sposta da inbox a outbox al massimo una volta, rendendo tutte le operazioni O(1) ammortizzato. Precisi che le singole chiamate a pop possono avere costo O(n) nel caso peggiore, quando outbox è vuota, ma la media su n operazioni è O(1).

LeetCode 225 è il problema della «pila ottenuta da code». La soluzione più chiara è quella con una sola coda e rotazione durante l'inserimento. Dopo aver inserito l'elemento x, ruoti la coda spostando dietro x tutti gli elementi che erano già presenti. Questa operazione costa O(n) per ogni push, ma rende top e pop O(1). Esponga il compromesso e verifichi che sia compatibile con i vincoli, ad esempio un carico di lavoro con poche operazioni di push o con molte operazioni di pop.

Una sfida progettuale correlata consiste nell'implementare tre pile usando un singolo array. Un approccio divide l'array in tre sezioni fisse di uguali dimensioni. Un approccio più flessibile usa una memorizzazione intercalata con puntatori: ogni pila cresce nella propria area e gli elementi vengono copiati quando i confini si incontrano. Questo mette alla prova la gestione dinamica degli array ed è un argomento proposto nei colloqui per posizioni senior. L'approccio con sezioni fisse è più semplice, ma spreca spazio se le pile crescono in modo non uniforme.

I problemi di simulazione reciproca insegnano un principio più generale: con una quantità sufficiente di memoria intermedia e di inversioni, è possibile costruire qualsiasi struttura dati a partire da un'altra. Il costo della simulazione dipende dalle operazioni che si ottimizzano: è sempre possibile rendere push O(1) oppure pop O(1), ma per rendere entrambe O(1) sono necessarie l'ammortizzazione o più strutture ausiliarie.

Durante un colloquio, chieda sempre: «Quali operazioni vengono eseguite più spesso?». Questa domanda guida la scelta della variante di implementazione e dimostra una mentalità da senior nei confronti dei requisiti operativi.

Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.

In questa lezione ha imparato che: una coda costruita con due pile raggiunge un'operazione pop ammortizzata in O(1) trasferendo gli elementi da inbox a outbox solo quando necessario, una pila costruita con una coda raggiunge un'operazione pop in O(1) ruotando la coda a ogni push (push in O(n)) e la scelta dell'operazione da rendere O(1) dipende dal modello di utilizzo. Nella prossima lezione esploreremo i meccanismi interni delle hash map e la gestione delle collisioni.