Продолжается набор новой группы на курс Enterprise Patterns! Старт курса 02.12.2024. Регистрируйтесь со скидкой 30% до 31.10.2024!
Узнать больше
06.11.2023
9 минут чтения

Как работает стек в Java

Программирование — это не только о том, как создавать функциональные приложения, но и о том, как эффективно управлять данными. И одним из ключевых инструментов, которые помогают нам с этим, является структура данных под названием «стек». Давайте более подробно разберемся в его сути и том, как он работает. Представьте, что у вас есть набор книг, которые вы храните в виде стопки. Как только вы кладете новую книгу, она автоматически становится на вершину стопки, и единственный способ достать книгу — это снять ее с вершины. Именно так работает стек java.

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

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

Стек — это такая структура данных, которая работает по принципу «последний вошел, первый вышел» (LIFO — Last In, First Out). Вы наверняка видели стопку книг или тарелок в кафе, где новые элементы кладут сверху, а чтобы достать нужный, вы снимаете его именно с верхушки стопки.

В Java стек можно представить с помощью класса Stack. Основные операции, которые можно выполнять со стеком, включают добавление элемента на вершину стека (push) и удаление элемента с вершины (pop). Если вы хотите положить новый элемент на стек, используйте операцию push, а если хотите извлечь элемент, то используйте операцию pop.

Определение стека в Java

Реализация стека в 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>) и проходим по каждому символу в выражении. Если встречаем открывающую скобку, кладем ее в стек. Если встречаем закрывающую скобку, проверяем, есть ли соответствующая открывающая скобка в стеке. Если стек пуст или открывающая скобка несоответствующая, то выражение несбалансированно. В конце проверяем, что стек пуст, чтобы убедиться в сбалансированности скобок.

🚀 Java Start: Ваш путь в программирование!

🎯 Условия:

  • Онлайн курс
  • Неограниченный доступ к лекциям и видео-урокам
  • Без проверки заданий
  • Помощь в чате Slack

Срок обучения:

Проходите курс за 2-4 недели.

👆👆👆

Но рассмотрим пример посложнее:

Предположим, у вас есть задача реализации системы отката (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 — стек, очередь и дерево — имеют свои особенности и применения. 

  • Стек

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

📢 Подпишись на наш Ютуб-канал! 💡Полезные видео для программистов уже ждут тебя!

🔍 Выбери свой курс программирования! 🚀 Путь к карьере программиста начинается здесь!

  • Очередь

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

  • Дерево

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

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

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

Структура данныхОсновной принципПримеры применения
СтекLIFO (последний вошел, первый вышел)Управление временными данными, отмена действий, выполнение операций в обратном порядке
ОчередьFIFO (первый вошел, первый вышел)Системы обработки задач, веб-серверы, обработка событий
ДеревоИерархическая структура данных с родительскими и дочерними узламиФайловые системы, иерархии категорий, поисковые структуры

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

Заключение

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

FAQ
Что такое стек в Java?

В Java стек — это область памяти, где хранятся локальные переменные методов и где происходит управление вызовом методов.

Как работает стек в Java?

Когда метод вызывается, создается новый блок в стеке, называемый стековым фреймом, для хранения локальных переменных и данных о вызове. Когда метод завершается, его стековый фрейм удаляется.

Чем стек отличается от кучи в Java?

Стек используется для хранения локальных переменных и управления вызовами методов, в то время как куча используется для хранения объектов.

Что происходит при переполнении стека?

Переполнение стека приводит к исключению StackOverflowError.

Могу ли я управлять размером стека в Java?

Да, можно использовать параметры JVM, такие как -Xss, чтобы установить размер стека.

Остались вопросы по стеку в Java? Спросите в комментариях ниже.

Добавить комментарий

Ваш имейл не будет опубликован. Обязательные поля отмечены *

Сохранить моё имя, имейл и адрес сайта в этом браузере для будущих комментариев