Освой Arduino играючи

Сайт Александра Климова

Шкодим

/* Моя кошка замечательно разбирается в программировании. Стоит мне объяснить проблему ей - и все становится ясно. */
John Robbins, Debugging Applications, Microsoft Press, 2000

Класс Stack

Современные программисты сейчас практически не используют Stack, который слишком прост и не очень гибок. Тем не менее, изучить его стоит, может именно он вам и пригодится.

Stack является подклассом класса Vector, который реализует простой механизм типа "последний вошёл - первый вышел" (LIFO). Можно представить процесс в виде детской пирамидки, когда вы по одному нанизываете диск на колышек. И снять диски вы сможете только по порядку, начиная с верхнего.

Stack Cat

Взять элемент, который положили первым, вам никто не позволит. Даже не пытайтесь сделать так.

Напишем простейший пример применения стека.


Stack<Integer> stack = new Stack<>();
stack.push(0);
stack.push(1);
stack.push(2);

System.out.println("Текущий стек: " + stack);
System.out.println("Удаляем: " + stack.pop());
System.out.println("Удаляем: " + stack.pop());
System.out.println("Удаляем: " + stack.pop());
System.out.println("Текущий стек: " + stack);

Получим результат.


I/System.out: Текущий стек: [0, 1, 2]
I/System.out: Удаляем: 2
I/System.out: Удаляем: 1
I/System.out: Удаляем: 0
I/System.out: Текущий стек: []

Метод push() помещает объект в стек, а метод pop(), наоборот, вытаскивает объект из стека.

Пример с числами слишком скучный. Давайте позовём на помощь котов. Создадим простой класс Cat:


package ru.alexanderklimov.expresscourse;

public class Cat {
    private String mName;
    private int mAge;

    public Cat(String name, int age) {
        mName = name;
        mAge = age;
    }

    @Override
    public String toString() {
        return this.mName;
    }
}

Представьте себе, что имеется длинная узкая труба, запаянная с одного конца. Мы заталкиваем в трубу пушистого друга, поэтому метод называется "пуш" (push()). А чтобы вытащить кота, хватаем его за попу (метод pop()). Давайте запихаем в трубу трёх котов, а потом вытащим их.


Cat barsik = new Cat("Барсик", 4);
Cat murzik = new Cat("Мурзик", 6);
Cat vaska = new Cat("Васька", 9);

Stack<Cat> catStack = new Stack<>();
catStack.push(barsik);
catStack.push(murzik);
catStack.push(vaska);

Log.i(TAG, "Текущий стек: " + catStack);
Log.i(TAG, "Брысь " + catStack.pop());
Log.i(TAG, "Кто последний? " + catStack.peek().toString());
Log.i(TAG, "Брысь " + catStack.pop());
Log.i(TAG, "Кто последний? " + catStack.peek().toString());
Log.i(TAG, "Брысь " + catStack.pop());
Log.i(TAG, "Никого? " + catStack.empty());
try {
    Log.i(TAG, "Кто последний? " + catStack.peek().toString());
}catch (EmptyStackException e)
{
    Log.i(TAG, "Пустой стек. Некого прогонять");
}
Log.i(TAG, "Текущий стек: " + catStack);

У нас есть три кота - Барсик, Мурзик и Васька. В такой последовательности мы их запихнули в трубу и проверяем текущий стек.


I/ExpressCourse: Текущий стек: [Барсик, Мурзик, Васька]

Вызываем метод pop() первый раз. Как видите, мы не указываем позицию элемента, так стек работает только с последним элементом. Последним был Васька. Чтобы узнать, кто теперь последний в стеке, не удаляя его оттуда, нужно вызвать метод peek().


I/ExpressCourse: Брысь Васька
I/ExpressCourse: Кто последний? Мурзик

Повторяем этот шаг ещё раз и вытаскиваем кота Мурзика. Затем и Барсика.


I/ExpressCourse: Брысь Мурзик
I/ExpressCourse: Кто последний? Барсик
I/ExpressCourse: Брысь Барсик

Чтобы убедиться, что в трубе никого не осталось, вызываем метод empty(), который возвращает булево значение.


I/ExpressCourse: Никого? true

Если при пустом стеке вызвать методы pop() или peek(), то программа закроется с ошибкой. Чтобы избежать подобной ситуации, нужно обработать исключение EmptyStackException. Тогда программа будет работать без сбоев.


I/ExpressCourse: Пустой стек. Некого прогонять

В конце выводим информацию о пустом стеке.


I/ExpressCourse: Текущий стек: []

У класса также есть метод int search(Object o), который ищет заданный элемент в стеке, возвращая количество операций pop(), которые требуются для того чтобы перевести искомый элемент в вершину стека. Если заданный элемент в стеке отсутствует, этот метод возвращает -1.

Надеюсь, вы поняли что такое стек. Пожалуйста, не загоняйте котов в трубу.

Дополнительные материалы

Используем стек для создания лабиринта

Реклама