Как работает стек в 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 — стек, очередь и дерево — имеют свои особенности и применения. 

• Стек

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

• Очередь

Очередь — это структура данных, в которой элементы добавляются в один конец — “конец очереди”, и удаляются с другого конца, называемого “началом очереди”. Первый добавленный элемент будет первым, который будет удален. Очередь полезна, когда нужно обрабатывать элементы в порядке их добавления, например, в системах обработки задач, веб-серверах или при обработке событий.

• Дерево

Дерево — это иерархическая структура данных, состоящая из узлов, связанных между собой ребрами. У каждого узла может быть один родитель и ноль или более дочерних узлов. Деревья используются для представления иерархических отношений, таких как файловые системы или иерархии категорий. Они могут иметь различные типы, такие как бинарные деревья или двоичные поисковые деревья.

Давайте рассмотрим их отличия подробнее.

Табличка сравнения:

Как видим, все эти три структуры данных имеют разные принципы работы и применения. Стек используется для управления временными данными и выполнения операций в обратном порядке, очередь — для обработки элементов в порядке добавления, а дерево — для представления иерархических отношений. Выбор структуры данных зависит от конкретной задачи и требований программы.

Заключение

Понимание принципов работы стека позволяет программистам организовывать и структурировать данные таким образом, чтобы удовлетворять требованиям конкретных задач. Это помогает оптимизировать процессы, улучшить производительность и создавать более надежное ПО. Поэтому понимание стека и его применений является неотъемлемой частью навыков программиста и способствует развитию и повышению его профессионализма.