Stapels en wachtrijen uitgelegd: LIFO, FIFO en gelinkte lijsten

Een stapel (stack) en een wachtrij (queue) zijn de twee eenvoudigste datastructuren die er bestaan, en tegelijk twee van de meest gebruikte. Elke keer dat je op Ctrl+Z drukt, gebruikt je editor een stapel. Elke keer dat je iets naar de printer stuurt, komt het in een wachtrij. En elke functieaanroep in je programma belandt op de aanroepstapel (call stack).

Op het tentamen krijg je meestal een reeks operaties en moet je de toestand erna opschrijven, of moet je uitleggen welke structuur bij een probleem past. In sollicitatiegesprekken is "controleer of de haakjes kloppen" een klassieker. Allebei komen hieronder aan bod.

Stapel: last in, first out

Een stapel werkt als een stapel borden: je legt een nieuw bord bovenop en je pakt ook altijd het bovenste weer weg. Wat het laatst erop kwam, gaat er het eerst af: LIFO (last in, first out).

De operaties:

• push(x): leg x bovenop de stapel.
• pop(): haal het bovenste element weg en geef het terug.
• peek() (of top()): bekijk het bovenste element zonder het weg te halen.
• isEmpty(): is de stapel leeg?

We noteren de toestand van een stapel altijd van onder naar boven: het meest rechtse element is de bovenkant.

Wachtrij: first in, first out

Een wachtrij werkt als de rij bij de kassa: wie het eerst aansluit, wordt het eerst geholpen: FIFO (first in, first out).

• enqueue(x): zet x achteraan in de rij.
• dequeue(): haal het voorste element weg en geef het terug.
• front(): bekijk het voorste element.

De toestand noteren we van voor naar achter: het meest linkse element is als eerste aan de beurt. Dezelfde reeks als hierboven, maar nu met een wachtrij:

Zelfde invoer, totaal ander resultaat: de stapel eindigt met 4, 5, de wachtrij met 9, 5.

Een stapel met een array of lijst

Een stapel is eenvoudig te bouwen op een dynamische array (Python list, Java ArrayList). De bovenkant is het einde van de lijst: toevoegen en weghalen aan het einde kost O(1) (bij een dynamische array gemiddeld, omdat de array af en toe moet groeien).

class Stapel:
    def __init__(self):
        self.data = []

    def push(self, x):
        self.data.append(x)  # bovenkant = einde van de lijst

    def pop(self):
        if not self.data:
            raise IndexError("pop op lege stapel")
        return self.data.pop()

    def peek(self):
        return self.data[-1]

    def is_empty(self):
        return len(self.data) == 0

import java.util.ArrayList;

class Stapel {
    private final ArrayList<Integer> data = new ArrayList<>();

    void push(int x) {
        data.add(x); // bovenkant = einde van de lijst
    }

    int pop() {
        if (data.isEmpty()) {
            throw new IllegalStateException("pop op lege stapel");
        }
        return data.remove(data.size() - 1);
    }

    int peek() {
        return data.get(data.size() - 1);
    }

    boolean isEmpty() {
        return data.isEmpty();
    }
}

Voor een wachtrij werkt een gewone lijst slecht: dequeue haalt het eerste element weg, en dan moeten alle andere elementen een plek opschuiven. In Python is list.pop(0) daarom O(n). Gebruik voor een wachtrij collections.deque (Python) of ArrayDeque (Java), of bouw er een met een gelinkte lijst.

Gelinkte lijsten

Een gelinkte lijst (linked list) bestaat uit losse knopen (nodes). Elke knoop bevat een waarde en een verwijzing naar de volgende knoop. In een enkel gelinkte lijst (singly linked list) wijst elke knoop alleen naar zijn opvolger; de lijst zelf onthoudt alleen de eerste knoop, de head.

head → [4 | •] → [7 | •] → [1 | •] → null

Het grote voordeel: vooraan invoegen of verwijderen kost O(1), want je verandert alleen een paar verwijzingen. Niets hoeft op te schuiven.

• Vooraan invoegen: maak een nieuwe knoop, laat hem naar de oude head wijzen, maak hem de nieuwe head.
• Vooraan verwijderen: maak head.next de nieuwe head.

Het nadeel: je kunt niet direct naar index i springen. Om het i-de element te vinden, loop je vanaf head de verwijzingen af: O(n). Daarom werkt binair zoeken niet op een gelinkte lijst.

Stapel en wachtrij met een gelinkte lijst

Een stapel is een gelinkte lijst waarbij je alleen vooraan werkt: push voegt vooraan in, pop verwijdert vooraan. De head is de bovenkant van de stapel.

Een wachtrij houdt twee verwijzingen bij: head (voorkant) en tail (achterkant). enqueue hangt een knoop achter tail, dequeue haalt head weg. Allebei O(1).

class Knoop:
    def __init__(self, waarde, volgende=None):
        self.waarde = waarde
        self.volgende = volgende


class Wachtrij:
    def __init__(self):
        self.head = None  # voorkant: hier gaat het eruit
        self.tail = None  # achterkant: hier komt het erbij

    def enqueue(self, x):
        knoop = Knoop(x)
        if self.tail is None:  # lege wachtrij
            self.head = self.tail = knoop
        else:
            self.tail.volgende = knoop
            self.tail = knoop

    def dequeue(self):
        if self.head is None:
            raise IndexError("dequeue op lege wachtrij")
        x = self.head.waarde
        self.head = self.head.volgende
        if self.head is None:  # wachtrij is nu leeg
            self.tail = None
        return x

class Wachtrij {
    private static class Knoop {
        int waarde;
        Knoop volgende;

        Knoop(int waarde) {
            this.waarde = waarde;
        }
    }

    private Knoop head; // voorkant: hier gaat het eruit
    private Knoop tail; // achterkant: hier komt het erbij

    void enqueue(int x) {
        Knoop knoop = new Knoop(x);
        if (tail == null) { // lege wachtrij
            head = tail = knoop;
        } else {
            tail.volgende = knoop;
            tail = knoop;
        }
    }

    int dequeue() {
        if (head == null) {
            throw new IllegalStateException("dequeue op lege wachtrij");
        }
        int x = head.waarde;
        head = head.volgende;
        if (head == null) { // wachtrij is nu leeg
            tail = null;
        }
        return x;
    }
}

Let op de randgevallen: bij de eerste enqueue moeten head én tail naar de nieuwe knoop wijzen, en als de laatste knoop eruit gaat moet tail weer null worden. Vergeet je dat, dan wijst tail naar een knoop die niet meer in de lijst zit.

Toepassing: haakjes controleren

Klopt {[()()]}? En ([)]? Elk sluithaakje moet passen bij het laatst geopende haakje dat nog open staat. "Laatst geopend, eerst gesloten": dat is LIFO, dus een stapel.

Het algoritme: openingshaakje → push. Sluithaakje → pop en controleer of het bijbehorende openingshaakje eruit komt. Aan het eind moet de stapel leeg zijn.

De stapel is leeg aan het einde: {[()()]} klopt. Bij ([)] gaat het mis bij het derde teken: ) komt binnen, maar pop levert [ op. Fout. En bij (() blijft er aan het eind een ( op de stapel staan: ook fout.

def haakjes_kloppen(s):
    paren = {")": "(", "]": "[", "}": "{"}
    stapel = []
    for c in s:
        if c in "([{":
            stapel.append(c)  # openingshaakje: push
        elif c in paren:
            # sluithaakje: de bovenkant moet het juiste openingshaakje zijn
            if not stapel or stapel.pop() != paren[c]:
                return False
    return not stapel  # alles moet gesloten zijn

static boolean haakjesKloppen(String s) {
    java.util.ArrayDeque<Character> stapel = new java.util.ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stapel.push(c); // openingshaakje: push
        } else if (c == ')' || c == ']' || c == '}') {
            char verwacht = c == ')' ? '(' : c == ']' ? '[' : '{';
            // sluithaakje: de bovenkant moet het juiste openingshaakje zijn
            if (stapel.isEmpty() || stapel.pop() != verwacht) {
                return false;
            }
        }
    }
    return stapel.isEmpty(); // alles moet gesloten zijn
}

Meer toepassingen

Wil je in plaats van "eerst binnen" juist "kleinste eerst" verwerken, dan heb je een prioriteitswachtrij nodig. Die bouw je met een heap.

Complexiteit

"Gemiddeld" (amortized) bij de array: meestal is er nog plek, maar af en toe moet de array verdubbelen en wordt alles gekopieerd. Verdeeld over alle operaties is dat nog steeds O(1) per operatie.

Veelgemaakte fouten op het tentamen

1. De stapel in de verkeerde richting opschrijven. Wij noteren van onder naar boven: na push(4), push(7) is het 4, 7, niet 7, 4. Het meest rechtse element gaat er als eerste af.
2. Bij de wachtrij aan de verkeerde kant weghalen. dequeue haalt het element weg dat het langst wacht, dus het meest linkse in de notatie voor → achter.
3. Een gewone lijst als wachtrij gebruiken en denken dat pop(0) of remove(0) O(1) is. Het is O(n), want alles schuift op.
4. Bij haakjes controleren vergeten te kijken of de stapel aan het eind leeg is. Dan keur je (() ten onrechte goed.
5. tail niet bijwerken in een gelinkte wachtrij als de laatste knoop verdwijnt, of head vergeten bij de eerste enqueue.

Samenvatting

• Stapel = LIFO: push en pop aan dezelfde kant; noteer van onder naar boven.
• Wachtrij = FIFO: enqueue achteraan, dequeue vooraan; noteer van voor naar achter.
• Alle kernoperaties zijn O(1), mits je de juiste implementatie kiest (geen pop(0) op een lijst).
• Een enkel gelinkte lijst kan vooraan invoegen en verwijderen in O(1), maar indexeren kost O(n).
• Stapel: haakjes, undo, call stack, DFS. Wachtrij: printer, BFS, verzoeken verwerken.