Абстрактный тип данных “деꔶ
Абстрактный тип данных дека определяется следующими структурой и операциями. Как было описано выше, он имеет структуру упорядоченной коллекции элементов, которые могут добавляться и удаляться с любого конца - и с головы, и с хвоста. Операции для дека представлены ниже:
- Deque() создаёт новый пустой дек. Не нуждается в параметрах и возвращает пустой дек.
- addFront(item) добавляет новый элемент в голову дека. Параметр (элемент) необходим; ничего не возвращает.
- addRear(item) добавляет новый элемент в хвост дека. Параметр (элемент) необходим; ничего не возвращает.
- removeFront() удаляет первый элемент из дека. Не нуждается в параметрах и возвращает элемент. Дек модифицируется.
- removeRear() удаляет последний элемент из дека. Не нуждается в параметрах и возвращает элемент. Дек модифицируется.
- isEmpty() проверяет дек на пустоту. Не нуждается в параметрах и возвращает булево значение.
- size() возвращает количество элементов в деке. Не нуждается в параметрах и возвращает целое число.
В качестве примера, если мы предположим, что d - это дек, который был создан и всё ещё пуст, то таблица 1 демонстрирует результаты серии операций над ним. Обратите внимание, что содержимое головы располагается справа. Очень важно отслеживать, где голова, а где хвост дека, когда вы перемещаете элементы в и из коллекции, поскольку эти вещи могут быть несколько запутанными.
| Операция | Содержимое дека | Возвращаемое значение |
|---|---|---|
| d.isEmpty() | [] | True |
| d.addRear(4) | [4] | |
| d.addRear('dog') | ['dog',4,] | |
| d.addFront('cat') | ['dog',4,'cat'] | |
| d.addFront(True) | ['dog',4,'cat',True] | |
| d.size() | ['dog',4,'cat',True] | 4 |
| d.isEmpty() | ['dog',4,'cat',True] | False |
| d.addRear(8.4) | [8.4,'dog',4,'cat',True] | |
| d.removeRear() | ['dog',4,'cat',True] | 8.4 |
| d.removeFront() | ['dog',4,'cat'] | True |