Пишем стек на java — Программирование на Java, Android

Сегодня рассмотрю такую простую, но нужную структуру, как Стек (Stack). Эта структура данных имеет несколько реализаций (простейшая — реализация на базе одномерного массива или односвязного списка). Остановлюсь на первом варианте.

Теория. Стек в java

Для начала ознакомимся с небольшой теоретической базой. При использовании стека, есть доступ только к последнему добавленного элемента. Удалив этот элемент, пользователь получает доступ к предпоследнему элемента и тд. Таким образом эта структура данных реализует принцип LIFO (Last In First Out). Для удобства можно провести аналогию со стопкой тарелок или магазином пистолета (последний заряженный патрон, будет подан в патронник первым). Многие микропроцессоров имеют стековую архитектуру. Когда происходит вызов метода, адрес возврата и аргументы заносятся в стек, а при выходе изымаются из него.

Пример стека

Здесь 5 — элемент на вершине стека (назовем последний элемент — top) — рисунок 1.

Рисунок 1 — Пример стека, который будет реализован на java

Таким образом, чтобы получить из стека элемент «3», для начала нам нужно удалить «5» и «4». На этом небольшая теоретическая часть заканчивается. Добавлю, что элемент TOP, иногда еще называют «головой» (head).

Реализация стека в java

Итак, я предлагаю реализовать следующие методы для нашего стека:

1) addElement — метод, который обеспечит добавление элемента (в top позиции)

2) deleteElement — метод, которых обеспечит удаление элемента (с top позиции)

3) readTop — метод, который вернет значение элемента, который находится в позиции top

4) isEmpty — метод, который будет проверять стек на пустоту

5) isFull — метод, который будет проверять, не переполнен наш массив, в котором мы сохраняем стек

Для начала создадим в нашем проекте, класс Stack, объявим нужные для работы поля, а далее инициализируем их в конструкторе.

class Stack {
    private int mSize; //mSize - максимальный размер
    private int[] stackArray;
    private int top;

    public Stack(int m) {
        this.mSize = m;
        stackArray = new int[mSize];
        top = -1;
    }

class Stack {

private int mSize; //mSize - максимальный размер

private int[] stackArray;

private int top;

public Stack(int m) {

this.mSize = m;

stackArray = new int[mSize];

top = -1;

}

Конструктор имеет параметр m, он позволит пользователю ввести максимальный размер стека с клавиатуры. Также, необходимо понимать разницу между синтаксисом top++ и ++top. В первом случае, сначала выполняется определенное действие, а затем инкрементируется (увеличивается) счетчик. Во втором, сначала инкрементируется счетчик, а затем выполняется действие.

Реализуем упомянутые методы взаимодействия со стеком.

1) addElement

public void addElement(int element) {
        stackArray[++top] = element;
    }

public void addElement(int element) {

stackArray[++top] = element;

}

Увеличиваем индекс массива и добавляем на указанную позицию переданный элемент.

2) deleteElement

public int deleteElement() {
        return stackArray[top--];
    }

public int deleteElement() {

return stackArray[top--];

}

Для удаления существующего top элемента достаточно уменьшить индекс массива. Таким образом нашей вершиной стека станет предпоследней элемент, а последний элемент будет удален с помощью Garbage Collector (встроенный в Java машину механизм для удаления определенных элементов).

Графическая иллюстрация процесса удаления представлена на рисунке 2

Рисунок 2 — Процесс удаления со стека

3) readTop

public int readTop() {
        return stackArray[top];
    }

public int readTop() {

return stackArray[top];

}

Метод возвращает пользователю элемент, который находится на вершине стека.

4) IsEmpty

public boolean isEmpty() {
        return (top == -1);
    }

public boolean isEmpty() {

return (top == -1);

}

Возвращает true (если массив данных пустой, индекс элемента top = 1, именно для этого мы задавали в конструкторе такое начальное значение для данной переменной).

5) isFull

public boolean isFull() {
        return (top == mSize - 1);
    }

public boolean isFull() {

return (top == mSize - 1);

}

Метод возвращает значение true (в той ситуации, когда наш массив данных полностью заполнен и нет возможности добавить еще один элемент). Кстати, может возникнуть вопрос, почему именно mSize-1? Если мы задаем максимальное количество элементов массива 10, то максимальный индекс будет 9, так как индексы идут от 0 до 9.

В методе main реализуем введения четырех элементов, удаление одного и дальнейший вывод стека на экран.

public class AwesomeStack {

    public static void main(String[] args) {
        Stack mStack = new Stack(10);

        mStack.addElement(79);
        mStack.addElement(59);
        mStack.addElement(35);
        mStack.addElement(24);

        mStack.deleteElement();

        System.out.print("Стек: ");
        while (!mStack.isEmpty()) {
            int value = mStack.deleteElement();
            System.out.print(value);
            System.out.print(" ");
        }
            System.out.println("");
    }

public class AwesomeStack {

public static void main(String[] args) {

Stack mStack = new Stack(10);

mStack.addElement(79);

mStack.addElement(59);

mStack.addElement(35);

mStack.addElement(24);

mStack.deleteElement();

System.out.print("Стек: ");

while (!mStack.isEmpty()) {

int value = mStack.deleteElement();

System.out.print(value);

System.out.print(" ");

}

System.out.println("");

}

Обратите внимание, что стек выдает элементы в порядке, обратном к вводу. То есть если мы вводили в стек 79, 59, 35, 24, то он вернет нам 24, 35, 59, 79. Именно поэтому эту структуру данных удобно применять для решения задачи реверса букв в слове или формирования префиксного записи алгебраических выражений (Reverse Polish Notation ).

Листинг программы:

class Stack {
    private int mSize;
    private int[] stackArray;
    private int top;

    public Stack(int m) {
        this.mSize = m;
        stackArray = new int[mSize];
        top = -1;
    }

    public void addElement(int element) {
        stackArray[++top] = element;
    }

    public int deleteElement() {
        return stackArray[top--];
    }

    public int readTop() {
        return stackArray[top];

    }

    public boolean isEmpty() {
        return (top == -1);
    }

    public boolean isFull() {
        return (top == mSize - 1);
    }
}

public class AwesomeStack {

    public static void main(String[] args) {
        Stack mStack = new Stack(10);

        mStack.addElement(79);
        mStack.addElement(59);
        mStack.addElement(35);
        mStack.addElement(24);

        mStack.deleteElement();

        System.out.print("Стек: ");
        while (!mStack.isEmpty()) {
            int value = mStack.deleteElement();
            System.out.print(value);
            System.out.print(" ");
        }
            System.out.println("");
    }
}