Реализация структуры данных Stack

Реализация структуры данных Stack

Стек — это одна из фундаментальных структур данных в компьютерной науке. Он используется везде: от обработки выражений и алгоритмов рекурсии до undo-функций в текстовых редакторах. Рассмотрим две основных реализации: на основе массива и на основе связного списка.

Stack на основе массива (ArrayList)

import java.util.ArrayList;

public class StackArray<T> {
    private ArrayList<T> elements;
    
    public StackArray() {
        elements = new ArrayList<>();
    }
    
    // Добавить элемент на вершину стека
    public void push(T element) {
        elements.add(element);
    }
    
    // Удалить и вернуть элемент с вершины
    public T pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return elements.remove(elements.size() - 1);
    }
    
    // Вернуть элемент с вершины без удаления
    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return elements.get(elements.size() - 1);
    }
    
    // Проверить, пуст ли стек
    public boolean isEmpty() {
        return elements.isEmpty();
    }
    
    // Вернуть количество элементов
    public int size() {
        return elements.size();
    }
    
    @Override
    public String toString() {
        return elements.toString();
    }
}

Stack на основе LinkedList

public class StackLinkedList<T> {
    
    // Вспомогательный класс для узла
    private class Node {
        T data;
        Node next;
        
        Node(T data) {
            this.data = data;
        }
    }
    
    private Node top;
    private int size;
    
    public StackLinkedList() {
        top = null;
        size = 0;
    }
    
    // Добавить элемент на вершину стека
    public void push(T element) {
        Node newNode = new Node(element);
        newNode.next = top;
        top = newNode;
        size++;
    }
    
    // Удалить и вернуть элемент с вершины
    public T pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        T data = top.data;
        top = top.next;
        size--;
        return data;
    }
    
    // Вернуть элемент с вершины без удаления
    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return top.data;
    }
    
    // Проверить, пуст ли стек
    public boolean isEmpty() {
        return top == null;
    }
    
    // Вернуть количество элементов
    public int size() {
        return size;
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        Node current = top;
        while (current != null) {
            sb.append(current.data);
            if (current.next != null) {
                sb.append(", ");
            }
            current = current.next;
        }
        sb.append("]");
        return sb.toString();
    }
}

Использование встроенного Stack Java

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        
        // push() — добавить элемент
        stack.push(10);
        stack.push(20);
        stack.push(30);
        
        System.out.println("Stack: " + stack); // [10, 20, 30]
        
        // peek() — просмотр вершины
        System.out.println("Top: " + stack.peek()); // 30
        
        // pop() — удаление и возврат
        System.out.println("Popped: " + stack.pop()); // 30
        
        // isEmpty() — проверка
        System.out.println("Is empty: " + stack.isEmpty()); // false
        
        // size() — размер
        System.out.println("Size: " + stack.size()); // 2
    }
}

Примеры тестирования

public class StackTest {
    
    public static void testStackArray() {
        StackArray<String> stack = new StackArray<>();
        
        // Тест push и pop
        stack.push("A");
        stack.push("B");
        stack.push("C");
        
        assert stack.size() == 3;
        assert stack.peek().equals("C");
        assert stack.pop().equals("C");
        assert stack.size() == 2;
        
        // Тест isEmpty
        while (!stack.isEmpty()) {
            stack.pop();
        }
        assert stack.isEmpty();
        
        // Тест исключения
        try {
            stack.pop();
            assert false; // Не должно достичь сюда
        } catch (IllegalStateException e) {
            assert e.getMessage().contains("empty");
        }
    }
    
    public static void testStackLinkedList() {
        StackLinkedList<Integer> stack = new StackLinkedList<>();
        
        stack.push(100);
        stack.push(200);
        stack.push(300);
        
        assert stack.size() == 3;
        assert stack.peek() == 300;
        assert stack.pop() == 300;
        assert !stack.isEmpty();
    }
    
    public static void main(String[] args) {
        testStackArray();
        testStackLinkedList();
        System.out.println("All tests passed!");
    }
}

Сравнение реализаций

Реальные применения Stack

1. Обработка выражений — проверка скобок, вычисление постфиксных выражений
2. Управление памятью — call stack для функций, хранение локальных переменных
3. Backtracking — лабиринты, проблема N королев
4. Undo/Redo — в текстовых редакторах
5. DFS (Depth-First Search) — обход графов
6. Преобразование инфиксной нотации в постфиксную

Обработка исключений

Выбросить исключение при попытке pop() из пустого стека — правильный подход:

if (isEmpty()) {
    throw new IllegalStateException("Stack is empty");
}

Это лучше, чем возвращать null, так как явно сигнализирует об ошибке и предотвращает NullPointerException позже в коде.