Stos, kolejka i lista jednokierunkowa w Javie

Stos (stack) działa według zasady LIFO, Last In, First Out: co położysz na wierzch jako ostatnie, zdejmujesz jako pierwsze. Operacje nazywają się push (połóż na wierzch), pop (zdejmij) i peek (tylko podejrzyj). Stosy są wszędzie tam, gdzie coś się cofa albo zagnieżdża: przycisk Wstecz w przeglądarce, Ctrl+Z, sprawdzanie nawiasów, wywołania metod w rekurencji.

Kolejka (queue) działa według zasady FIFO, First In, First Out: kto pierwszy przyszedł, ten pierwszy obsłużony. Operacje nazywają się enqueue (ustaw się na końcu) i dequeue (wyjmij z początku). Przykłady to zadania drukowania albo zapytania do serwera.

ArrayDeque z java.util potrafi jedno i drugie. W przykładzie te same trzy litery wychodzą raz w odwrotnej kolejności, a raz w kolejności dodania.

1import java.util.ArrayDeque;2import java.util.Deque;3
4public class Main {5    public static void main(String[] args) {6        Deque<String> stack = new ArrayDeque<>();7        stack.push("A");8        stack.push("B");9        stack.push("C");10        System.out.print("Stack: ");11        while (!stack.isEmpty()) {12            System.out.print(stack.pop() + " ");13        }14        System.out.println();15
16        Deque<String> queue = new ArrayDeque<>();17        queue.offer("A");18        queue.offer("B");19        queue.offer("C");20        System.out.print("Queue: ");21        while (!queue.isEmpty()) {22            System.out.print(queue.poll() + " ");23        }24        System.out.println();25    }26}

Do własnego stosu wystarczą tablica i licznik size. size jest jednocześnie indeksem następnego wolnego miejsca, a element na wierzchu leży pod data[size - 1].

• push: zapisz do data[size], potem size++.
• pop: size--, potem zwróć data[size]. Nic nie jest usuwane, miejsce po prostu uznaje się za wolne.

Żadna z tych operacji nie potrzebuje pętli, bez względu na to, ile elementów leży na stosie. Ich złożoność to O(1), czyli stała. Co dzieje się przy pustym albo pełnym stosie, musisz ustalić sam: tutaj rzucany jest wyjątek IllegalStateException.

1public class Main {2    static int[] data = new int[10];3    static int size = 0;4
5    static void push(int value) {6        if (size == data.length) {7            throw new IllegalStateException("Stack is full");8        }9        data[size] = value;10        size++;11    }12
13    static int pop() {14        if (size == 0) {15            throw new IllegalStateException("Stack is empty");16        }17        size--;18        return data[size];19    }20
21    public static void main(String[] args) {22        push(1);23        push(2);24        push(3);25        System.out.println(pop());26        System.out.println(pop());27        push(9);28        System.out.println(pop());29        System.out.println("Size: " + size);30    }31}

W kolejce na tablicy elementy dochodzą na końcu i odchodzą z początku. Gdybyś po każdym dequeue przesuwał wszystkie elementy o jedno miejsce do przodu, kosztowałoby to O(n). Zamiast tego przesuwa się początek: head wskazuje na pierwszy element, a count liczy elementy.

Gdy indeks dojdzie do końca tablicy, wraca do 0. Załatwia to operator modulo:

1int tail = (head + count) % data.length;   // next free slot2head = (head + 1) % data.length;           // after dequeue

W ten sposób tablica staje się buforem cyklicznym (ring buffer), a zarówno enqueue, jak i dequeue pozostają O(1). W przykładzie 40 i 50 trafiają z powrotem na indeksy 0 i 1, bo tam zwolniło się już miejsce.

1public class Main {2    static int[] data = new int[3];3    static int head = 0;4    static int count = 0;5
6    static void enqueue(int value) {7        if (count == data.length) {8            throw new IllegalStateException("Queue is full");9        }10        int tail = (head + count) % data.length;11        data[tail] = value;12        count++;13        System.out.println("enqueue " + value + " at index " + tail);14    }15
16    static int dequeue() {17        if (count == 0) {18            throw new IllegalStateException("Queue is empty");19        }20        int value = data[head];21        head = (head + 1) % data.length;22        count--;23        return value;24    }25
26    public static void main(String[] args) {27        enqueue(10);28        enqueue(20);29        enqueue(30);30        System.out.println("dequeue " + dequeue());31        System.out.println("dequeue " + dequeue());32        enqueue(40);33        enqueue(50);34        while (count > 0) {35            System.out.println("dequeue " + dequeue());36        }37    }38}

Lista jednokierunkowa składa się z węzłów. Każdy węzeł zna swoją wartość i następny węzeł (next), a ostatni wskazuje na null. Sama lista pamięta tylko head, czyli pierwszy węzeł.

Przechodzi się ją zawsze tak samo:

1Node current = head;2while (current != null) {3    // use current.value4    current = current.next;5}

Tablica i lista wiązana w porównaniu:

• Odczyt elementu o indeksie i: tablica O(1), lista O(n), bo musisz iść węzeł po węźle.
• Wstawianie na początek: tablica O(n), bo wszystko trzeba przesunąć, lista O(1) z nowym head.
• Wstawianie na koniec: tablica O(1), dopóki jest miejsce, lista O(n), a z referencją tail O(1).
• Rozmiar: tablica ma stały rozmiar, lista rośnie dowolnie.

Stos da się zbudować na jednym i na drugim. W kolejce na węzłach pamięta się dodatkowo tail, żeby enqueue nie musiało iść aż do końca.

1public class Main {2    static class Node {3        int value;4        Node next;5
6        Node(int value) {7            this.value = value;8        }9    }10
11    public static void main(String[] args) {12        Node head = new Node(3);13        head.next = new Node(5);14        head.next.next = new Node(8);15
16        Node node = new Node(1);17        node.next = head;18        head = node;19
20        int sum = 0;21        Node current = head;22        while (current != null) {23            System.out.print(current.value + " -> ");24            sum += current.value;25            current = current.next;26        }27        System.out.println("null");28        System.out.println("Sum: " + sum);29    }30}