Як працює стек у Java

Програмування — це не тільки про те, як створювати функціональні додатки, а й про те, як ефективно управляти даними. І одним із ключових інструментів, які допомагають нам із цим, є структура даних під назвою “стек”. Давайте більш детально розберемося в його суті і тому, як він працює. Уявіть, що у вас є набір книг, які ви зберігаєте у вигляді стопки. Щойно ви кладете нову книгу, вона автоматично стає на вершину стопки, і єдиний спосіб дістати книгу — це зняти її з вершини. Саме так працює стек java.

У програмуванні — останній доданий елемент завжди буде першим, який буде видалено. Розглянемо принципи його роботи, щоб зрозуміти, як він може бути корисний нам у розробці ПЗ.

Опис структури даних 

Стек — це така структура даних, яка працює за принципом “останній увійшов, перший вийшов” (LIFO – Last In, First Out). Ви напевно бачили стопку книжок або тарілок у кафе, де нові елементи кладуть зверху, а щоб дістати потрібний, ви знімаєте його саме з верхівки стопки.

У Java стек можна представити за допомогою класу Stack. Основні операції, які можна виконувати зі стеком, включають додавання елемента на вершину стека (push) і видалення елемента з вершини (pop). Якщо ви хочете покласти новий елемент на стек, використовуйте операцію push, а якщо хочете витягти елемент, то використовуйте операцію pop.

Реалізація стека в Java досить проста і зручна. Ви можете створити об’єкт класу Stack, а потім використовувати методи push і pop для керування елементами стека. Важливо пам’ятати, що при використанні стека потрібно стежити за порядком операцій, щоб не порушити принцип LIFO.

Наприклад, ось як ви можете створити стек у Java:

import java.util.Stack;

public class Main {

    public static void main(String[] args) {

        Stack<Integer> stack = new Stack<>();

        stack.push(1); // Додаємо елемент 1 на вершину стека

        stack.push(2); // Додаємо елемент 2 на вершину стека

        stack.push(3); // Додаємо елемент 3 на вершину стека

        int top = stack.pop(); // Витягаємо елемент з вершини стека (3)

        System.out.println(top); // Виводимо: 3

    }

}

У цьому прикладі ми створюємо стек цілих чисел (Stack<Integer>) і додаємо в нього три елементи. Потім ми витягуємо елемент з вершини стека і виводимо його значення на екран.

Реалізація стека в Java надає зручні методи для управління даними і може бути корисною в багатьох ситуаціях програмування.

Приклади використання стека в Java

Давайте уявимо, що ми пишемо програму, яка перевіряє правильність розміщення дужок у математичному виразі. Наприклад, у нас є вираз: “(2 + 3) * (4 – 1)”. Ми можемо використати стек, щоб перевірити, що всі дужки у виразі збалансовані (дужка, що відкриває, має відповідну дужку, що закриває). Ось як це можна зробити:

import java.util.Stack;

public class BracketChecker {

    public static boolean isBalanced(String expression) {

        Stack<Character> stack = new Stack<>();

        for (char c : expression.toCharArray()) {

            if (c == '(') {

                stack.push(c);  // Якщо зустріли дужку, що відкриває, кладемо її в стек

            } else if (c == ')') {

                if (stack.isEmpty()) {

                    return false;  // Якщо зустріли дужку, що закриває, але стек порожній, значить дужки незбалансовані

                }

                stack.pop();  // Якщо зустріли дужку, що закриває, видаляємо відповідну дужку, що відкриває, зі стека

            }

        }

        return stack.isEmpty();  // Якщо стек порожній, то всі дужки збалансовані

    }

    public static void main(String[] args) {

        String expression = "(2 + 3) * (4 - 1)";

        boolean isBalanced = isBalanced(expression);

        System.out.println("Вираз збалансований? " + isBalanced);

    }

}

У цьому прикладі ми створюємо стек символів (Stack<Character>) і проходимо по кожному символу у виразі. Якщо зустрічаємо відкриваючу дужку, кладемо її в стек. Якщо зустрічаємо дужку, що закриває, перевіряємо, чи є відповідна дужка, що відкриває, у стеку. Якщо стек порожній або відкриваюча дужка невідповідна, то вираз незбалансований. Наприкінці перевіряємо, що стек порожній, щоб переконатися у збалансованості дужок.

Але розглянемо приклад складніший:

Припустимо, у вас є завдання реалізації системи відкату (undo) для текстового редактора. Ви хочете, щоб користувач міг виконувати операції над текстом (наприклад, вставка, видалення, заміна) і мати можливість скасувати ці операції у зворотному порядку.

Ви можете використовувати стек для зберігання виконаних операцій. Кожна операція буде представлена об’єктом, що містить інформацію про тип операції та її параметри. При виконанні операції ви будете додавати її в стек, а при скасуванні операції — видаляти зі стека і виконувати зворотну операцію. Це дає нам змогу скасовувати попередні дії користувача і відновлювати попередній стан тексту.

Ось приклад коду для реалізації системи відкату з використанням стека:

import java.util.Stack;

public class TextEditor {

    private StringBuilder text;

    private Stack<Operation> operationStack;

    public TextEditor() {

        text = new StringBuilder();

        operationStack = new Stack<>();

    }

    public void insertText(String newText) {

        Operation operation = new InsertOperation(newText);

        operation.execute(text);

        operationStack.push(operation);

    }

    public void deleteText(int startIndex, int endIndex) {

        String deletedText = text.substring(startIndex, endIndex);

        Operation operation = new DeleteOperation(startIndex, deletedText);

        operation.execute(text);

        operationStack.push(operation);

    }

    public void undo() {

        if (!operationStack.isEmpty()) {

            Operation operation = operationStack.pop();

            operation.undo(text);

        }

    }

    private abstract class Operation {

        public abstract void execute(StringBuilder text);

        public abstract void undo(StringBuilder text);

    }

    private class InsertOperation extends Operation {

        private String newText;

        public InsertOperation(String newText) {

            this.newText = newText;

        }

        public void execute(StringBuilder text) {

            text.append(newText);

        }

        public void undo(StringBuilder text) {

            int startIndex = text.length() - newText.length();

            text.delete(startIndex, text.length());

        }

    }

    private class DeleteOperation extends Operation {

        private int startIndex;

        private String deletedText;

        public DeleteOperation(int startIndex, String deletedText) {

            this.startIndex = startIndex;

            this.deletedText = deletedText;

        }

        public void execute(StringBuilder text) {

            text.delete(startIndex, startIndex + deletedText.length());

        }

        public void undo(StringBuilder text) {

            text.insert(startIndex, deletedText);

        }

    }

}

У цьому прикладі ми використовуємо стек operationStack для зберігання виконаних операцій;

Сподіваємося, цей приклад допоміг вам краще зрозуміти складні застосування стека в Java!

Порівняння стека з іншими структурами даних 

Структури даних є важливою частиною програмування і дають змогу ефективно зберігати й організовувати дані. Три популярні структури даних у Java – стек, черга та дерево — мають свої особливості та застосування.

• Стек

Стек — це структура даних, у якій елементи додаються і видаляються тільки з одного кінця, званого вершиною. Останній доданий елемент завжди буде першим, який буде видалено. Приклад використання стека включає управління тимчасовими даними, скасування дій і виконання операцій у зворотному порядку.

• Черга

Черга — це структура даних, у якій елементи додаються в один кінець – “кінець черги” – і видаляються з іншого кінця, який називається “початком черги”. Перший доданий елемент буде першим, який буде видалено. Черга корисна, коли потрібно обробляти елементи в порядку їхнього додавання, наприклад, у системах опрацювання завдань, веб-серверах або під час опрацювання подій.

• Дерево

Дерево — це ієрархічна структура даних, що складається з вузлів, пов’язаних між собою ребрами. У кожного вузла може бути один батько і нуль або більше дочірніх вузлів. Дерева використовуються для представлення ієрархічних відносин, таких як файлові системи або ієрархії категорій. Вони можуть мати різні типи, такі як бінарні дерева або двійкові пошукові дерева.

Давайте розглянемо їхні відмінності докладніше.

Табличка порівняння:

Як бачимо, усі ці три структури даних мають різні принципи роботи та застосування. Стек використовується для управління тимчасовими даними та виконання операцій у зворотному порядку, черга — для опрацювання елементів у порядку додавання, а дерево — для представлення ієрархічних відносин. Вибір структури даних залежить від конкретного завдання і вимог програми.

Висновок

Розуміння принципів роботи стека дає змогу програмістам організовувати та структурувати дані таким чином, щоб задовольняти вимоги конкретних завдань. Це допомагає оптимізувати процеси, поліпшити продуктивність і створювати більш надійне ПЗ. Тому розуміння стека та його застосувань є невід’ємною частиною навичок програміста і сприяє розвитку та підвищенню його професіоналізму.