Абстрактные типы данных — это способ классификации структур данных на основе того, как они используются и какое поведение они обеспечивают. Они не определяют, как должна быть реализована структура данных, а просто обеспечивают минимальный ожидаемый интерфейс и набор поведений.

ADT – это теоретическое понятие в информатике, используемое при разработке и анализе алгоритмов, структур данных и программных систем, и оно не соответствует специфическим особенностям компьютерных языков.

Почему ADT?

Для управления сложностью проблем и процессом их решения используются абстракции, позволяющие пользователю сосредоточиться на общей картине, не теряясь в деталях.

— Список АТД

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

В программировании список будет описан вам как набор элементов, которые имеют линейную связь друг с другом.

  • элементы в списке имеют позицию (индекс).
  • списки имеют размер
  • списки могут увеличиваться и уменьшаться
  • списки не имеют пробелов.

следующие методы можно использовать для списка.

— Стек АТД

Стек представляет собой структуру данных LIFO (Last In First Out). Элементы стека могут быть вставлены и удалены с одной стороны списка, называемой вершиной.

Вставка элемента называется отправкой, а удаление элемента из стека — извлечением. В стеках последний элемент в списке отслеживается указателем с именем top.

следующие методы могут быть использованы для стека

  1. Object push(Object element): помещает элемент в верхнюю часть стека.
  2. Object pop(): удаляет и возвращает верхний элемент стека. Исключение «EmptyStackException» возникает, если мы вызываем pop(), когда вызывающий стек пуст.
  3. Object peek(): возвращает элемент на вершину стека, но не удаляет его.
  4. boolean empty(): возвращает true, если на вершине стека ничего нет. В противном случае возвращает ложь.
  5. int search(Object element): определяет, существует ли объект в стеке. Если элемент найден, он возвращает позицию элемента с вершины стека. В противном случае он возвращает -1.

— Очередь АДТ

Очередь — это структура данных FIFO (первым пришел — первым обслужен). Первый элемент, помещенный в очередь, является первым из нее.

Элементы можно вставлять только с одной стороны списка, называемой задней. иэлементы могут быть удалены только с другой стороны, называемой передней. Вставка элемента в очередь называется операцией постановка в очередь, а удаление элемента называется операцией удаление из очереди.

Операции с очередью приведены ниже.

  1. Queue() : создает новую пустую очередь. Ему не нужны параметры, и он возвращает пустую очередь.
  2. enqueue(item): добавляет новый элемент в конец очереди. Он нуждается в элементе и ничего не возвращает.

3. dequeue(): удаляет первый элемент из очереди. Он не нуждается в параметрах и возвращает элемент. Очередь изменена.

4. isEmpty(): проверяет, пуста ли очередь. Ему не нужны параметры, и он возвращает логическое значение.

5. size() : R возвращает количество элементов в очереди. Ему не нужны параметры, и он возвращает целое число.