Java for Beginner

Stack, особенности и примеры использования

Stack — это класс из пакета java.util, который реализует структуру данных "стек" (stack). Стек работает по принципу LIFO (Last In, First Out), что означает, что последний добавленный элемент будет первым, который удаляется. Эта структура данных полезна в случаях, когда требуется обратный порядок обработки данных, например, в алгоритмах обхода графов или в реализации операций отмены (undo).

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();

        // Добавление элементов в стек
        stack.push("Element 1");
        stack.push("Element 2");
        stack.push("Element 3");

        // Чтение верхнего элемента стека без его удаления
        System.out.println("Top element: " + stack.peek());

        // Удаление верхнего элемента стека
        System.out.println("Popped element: " + stack.pop());

        // Чтение элементов после удаления
        System.out.println("Top element after pop: " + stack.peek());
    }
}

Особенности Stack

Синхронизация: Stack является синхронизированным классом, что делает его безопасным для использования в многопоточной среде. Однако, как и Vector, это может привести к снижению производительности в однопоточных приложениях.
Наследование от Vector: Stack наследует все методы от класса Vector и добавляет свои методы, специфичные для работы с LIFO структурой.
Устаревший класс: В современных приложениях предпочтительнее использовать Deque интерфейс и его реализации (ArrayDeque или LinkedList), которые предлагают более гибкие и эффективные способы работы с данными, чем Stack.

Примеры использования
Обратный порядок строки:

public static String reverseString(String input) {
    Stack<Character> stack = new Stack<>();
    for (char c : input.toCharArray()) {
        stack.push(c);
    }
    StringBuilder reversed = new StringBuilder();
    while (!stack.isEmpty()) {
        reversed.append(stack.pop());
    }
    return reversed.toString();
}

Проверка корректности скобок:

public static boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

Перевод инфиксного выражения в постфиксное:

public static String infixToPostfix(String expression) {
    Stack<Character> stack = new Stack<>();
    StringBuilder result = new StringBuilder();
    for (char c : expression.toCharArray()) {
        if (Character.isLetterOrDigit(c)) {
            result.append(c);
        } else if (c == '(') {
            stack.push(c);
        } else if (c == ')') {
            while (!stack.isEmpty() && stack.peek() != '(') {
                result.append(stack.pop());
            }
            stack.pop();
        } else {
            while (!stack.isEmpty() && precedence(c) <= precedence(stack.peek())) {
                result.append(stack.pop());
            }
            stack.push(c);
        }
    }
    while (!stack.isEmpty()) {
        result.append(stack.pop());
    }
    return result.toString();
}

public static int precedence(char ch) {
    switch (ch) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '^':
            return 3;
    }
    return -1;
}

Ссылки на полезные статьи (спасибо авторам за проделанную работу) :
https://www.baeldung.com/java-stack

#Java #Training #Medium #Stack

Baeldung

Quick Guide to Java Stack | Baeldung

A quick and practical guide to common operations of the java.util.Stack.

179 viewsДен, 05:38

Java for Beginner

Внутреннее устройство и методы Stack

Stack в Java наследует класс Vector, что означает, что он использует динамический массив для хранения своих элементов. Это позволяет Stack автоматически изменять свой размер по мере добавления или удаления элементов.

public class Stack<E> extends Vector<E> {
    public Stack() {
    }

    public E push(E item) {
        addElement(item);
        return item;
    }

    public synchronized E pop() {
        E obj;
        int len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

    public synchronized E peek() {
        int len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

    public boolean empty() {
        return size() == 0;
    }

    public synchronized int search(Object o) {
        int i = lastIndexOf(o);

        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }
}

Основные методы Stack

push(E item):
Добавляет элемент на вершину стека.
Возвращает добавленный элемент.

Stack<Integer> stack = new Stack<>();
stack.push(10); // Добавляет элемент 10 на вершину стека

pop():
Удаляет и возвращает элемент с вершины стека.
Бросает EmptyStackException, если стек пуст.

int element = stack.pop(); // Удаляет и возвращает элемент 10

peek():
Возвращает элемент с вершины стека без его удаления.
Бросает EmptyStackException, если стек пуст.

int topElement = stack.peek(); // Возвращает элемент 10, но не удаляет его

isEmpty():
Проверяет, пуст ли стек.
Возвращает true, если стек пуст, и false в противном случае.

boolean isEmpty = stack.isEmpty(); // Возвращает false, так как стек не пуст

search(Object o):
Ищет элемент в стеке и возвращает его позицию относительно вершины.
Возвращает -1, если элемент не найден.

int position = stack.search(10); // Возвращает 1, так как элемент 10 на вершине стека

#Java #Training #Medium #Stack

196 viewsДен, 13:43

About

Blog

Apps

Platform