Ni boyinsha

Пример стека
Вот некоторые примеры, иллюстрирующие использование push и pop для стека. Предположим, что стек целых чисел уже создан. Фигура здесь, кажется, указывает, что стек фиксированного размера.

Стек может фактически быть реализован с помощью динамического размера.

Операция push 1 разместит значение 1 в пустой стек. push 2 поместит значение 2 сверху 1. Операция pop, которая не принимает никаких аргументов, вернет верхний элемент из стека, который несет значение 2. push 3 добавит 3 на вершину стека. push 4 добавит еще один элемент 4 на вершину стека. Мы можем добавить еще один элемент с тем же самым значением, что и предыдущие элементы в стеке, в этом случае, push 4 поставит 4 поверх другого 4. Операция peek, которая не принимает никаких аргументов, будет возвращать значение на вершине стека, то есть 4, не снимая верхний элемент из стека. pop удаляет, а также возвращает значение на вершину стека, в данном случае, со значением 4. Давайте рассмотрим простой пример с использованием стека для преобразования десятичного числа в двоичное число. Первоначальный подход для проведения конверсии может быть описан следующим образом.
Для данного числа n повторяется процесс:
- Находится остаток от деления на 2.
- Остаток выводится.
- n обновляется до n/2.
Мы хотим сначала найти остаток от деления числа на два. Например, дается число 29, и первый остаток будет 1.
n затем обновляется на n/2 с использованием целочисленного деления, в данном случае, 29/2 приведет к 14. Продолжая процесс, следующий остаток 0, и далее следуют три 1. Результат, полученный данным процессом, будет 10111, если остатки выводятся в порядке их создания.
Но правильный ответ должен быть 11101.
Так или иначе, мы должны хранить промежуточные результаты перед выводом их. После того как мы закончили конверсию, то результаты будут выводиться в обратном порядке. То есть, последний остаток будет выводиться первым, что предполагает, что стек будет соответствующим представлением для этой задачи. Предложенный подход будет push остатки в стек, а затем выводить результат, удаляя запись по одной из вершины стека.

Вот реализация идеи, использования стека для вывода десятичного числа в двоичном виде. Пустой стек целого типа настроен изначально. Двоичное число n, которое должно быть преобразовано, вводится в метод outputBinary в качестве параметра. В этом while цикле, остатки n вычисляются и помещается в переменную bit. Остаток вносится в целочисленный стек s. n затем заменяется на n/2 с использованием целочисленного деления. Обратите внимание, что мы явно обеспечиваем объект Integer как оболочку целого типа с помощью метода valueOf для класса Integer.
Когда while цикл завершается, стек должен содержать список остатков в обратном порядке, как они были получены. 2-й while цикл будет удалять остатки по одному сверху с помощью метода pop для стека s и присваивать bit. Каждый из остатков, удаленных из стека, будет выводиться с помощью System.out.print. Опять же, мы преобразовываем объект оболочки целого типа в целый типа, используя метод intValue. Вот еще один вариант предыдущего примера.

Единственное различие заключается в том, что тип данных для внесения в стек или удаления из стека не был преобразован в объект Integer явно. Здесь, мы можем просто использовать bit вместо целого объекта в качестве параметра, чтобы push потому что Java автоупаковка преобразует bit, параметр push, в "Integer.valueOf (bit)" во время компиляции. Точно так же, для присвоения s.pop(), которое, как предполагается, возвращает объект Integer, автораспаковка будет конвертировать левую часть в s.pop(). intValue() во время компиляции. Таким образом, обе программы будут эффективно вычислять то же самое.