Абстрактные типы данных
Теперь, давайте рассмотрим такую тему как абстрактный тип данных или ADT.
Вы сейчас должны быть хорошо знакомы с различными видами типов данных, в том числе примитивными типами данных, такими как int для целых чисел и double для чисел с плавающей точкой.
Мы также обсудили массив, как простую структуру данных, которая облегчает хранение и извлечение данных одного и того же типа.
Когда мы используем тип данных, важно думать не только о данных, которые этот тип представляет, важно также учитывать операции, которые связаны с этими данными.
Например, когда мы используем тип данных int, сами данные были бы не слишком полезны без арифметических операций, таких как сложение, вычитание, умножение и деление.
Когда мы используем тип String, методы, такие как charAt, compareTo и substring часто используются для манипулирования строкой символов, которую этот тип представляет.
В общем, абстрактный тип данных (ADT) представляет собой структуру данных, которая определяет характеристики набора данных и операции, которые можно выполнять с набором данных.
Но подробности о том, как данные представлены, и реализация скрыты от пользователей.
Например, когда мы используем строку символов, мы не должны знать, как строка символов представлена внутренне и как метод charAt реализуется, когда он возвращает char значение выбранной позиции строки, как указано в спецификации метода charAt.
Таким образом, ключевой концепцией ADT является то, что он скрывает детали реализации от пользователей.
Ключевыми преимуществами в использовании ADT является то, что он делает проще программирование и нам не нужно повторно реализовать тип данных каждый раз, когда он нам нужен.
Что еще более важно, любые изменения в конкретной реализации ADT не влияют на использование типа данных, поэтому важно, что, когда используется ADT, мы не должны рассматривать какие-либо специальные функции реализации.
Я буду использовать ADT, известный как стек, чтобы проиллюстрировать полезность ADT.
Можно придумать множество примеров из реальной жизни, которые используют ситуации со стеком.
Например, стопка монет может храниться в денежном разменнике. Или мы можем увидеть штабеля книг в библиотеке или книжных магазинах.
Когда мы идем в столовую, то вынимаем пищевые лотки из стопки. И мы вынимаем корзину для покупок в супермаркете.
Вы можете не знать об этом, но стеки часто используются в компьютерных операциях, когда мы отменяем операции, которые мы сделали в программном приложении, стек используется для хранения последовательности операций, и последняя выполненная операция будут находиться на вершине стека, так что она будет первой для отмены.
Когда мы используем веб-браузер, список сайтов, которые мы посетили, может храниться в стеке, так что, когда нажимаешь на кнопку "назад", можно вернуться к последнему сайту, на котором побывали.
Мы также упоминали, что вызовы методов хранятся в стеке программы таким образом, что могут сохранятся локальные переменные.
Для всех этих примеров можно увидеть, что одна общая характеристика стека – это то, что добавление и удаление записей может осуществляться только в верхней части стека.
Так как добавление и удаление записей может быть сделано только на вершине стека, последняя запись, которая добавляется в стек, всегда будет первой записью, которая должны быть удалена из стека.
Стек часто называют last-in-first out структурой данных (LIFO).
Две важные операции, которые поддерживаются ADT стеком, это операции push и pop.
Операция push добавляет запись на вершину стека и pop является операцией по удалению записи из верхней части стека.
Обратите внимание, что, если задача требует вставки записи в середину набора или удаления записи из нижней части набора, стек не будет соответствующим типом данных для данной задачи.
Другие ADT также часто доступны в большинстве объектно-ориентированных языков программирования.
Другой ADT, похожий на стек, называется очередью.
В отличие от стека, добавление записей в очереди, можно проводить только в хвосте или в конце очереди.
Это похоже на то, когда вы выстраиваетесь купить билет или ждать своей очереди в супермаркете,
Вы должны встать в конец очереди.
Если же вы встанете в начало или в середину очереди, я уверен, что на вас будут кричать все другие, которые уже стоят в очереди.
Удаление же записей, подобно стеку, может быть осуществлено только в начале очереди.
Очередь часто называют структурой данных FIFO, так как элементы, которые должны быть удалены из очереди, будут основываться на их порядке в очереди.
Здесь две широко используемые операции, это add для добавления объекта в конец очереди и remove для удаления объекта из начала очереди.
Пример стека
Рассмотрим некоторые примеры, иллюстрирующие использование 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 цикл завершается, стек должен содержать список остатков в обратном порядке, как они были получены.
Второй while цикл будет удалять остатки по одному, сверху с помощью метода pop для стека S и присваивать bit.
Каждый из остатков, удаленных из стека, будет выводиться с помощью System.out.print.
Опять же, мы преобразовываем объект оболочки целого типа в целый тип, используя метод intValue.
Вот еще один вариант предыдущего примера.
Единственное различие заключается в том, что тип данных для внесения в стек или удаления из стека не был преобразован в объект Integer явно.
Здесь, мы можем просто использовать bit вместо целого объекта в качестве параметра для метода push, потому что механизм Java автоупаковки преобразует bit, параметр push, в "Integer.valueOf (bit)" во время компиляции.
Точно так же, для присвоения s.pop(), которое, как предполагается, возвращает объект Integer, автораспаковка будет конвертировать левую часть в s.pop(). intValue() во время компиляции.
Таким образом, обе программы будут эффективно вычислять то же самое.
