Главная » Java, Структуры данных и алгоритмы » Абстрактный тип данных «дек»

0

Рассмотрим структуры данных, напоминающие очереди, но в которых добавление и удаление элементов может осуществляться как в начало, так и в конец. Подобный усовершенствованный вариант очереди называется двунаправленной очередью, или деком (deque — double-ended queue — очередь с двумя концами).

обладает большими возможностями, чем стек или очередь. Этот АТД поддерживает следующие базовые методы (D обозначает дек):

insertFirst (е): помещает новый элемент е в начало D. Input: объект; Output: нет.

insertLast (е): помещает новый элемент е в конец D. Input: объект; Output: нет.

removeFirst (): удаляет и возвращает первый элемент D\ если D пуст, выдается сообщение об ошибке. Input: нет; Output: объект.

removeLast (): удаляет и возвращает последний элемент D\ если D пуст, выдается сообщение об ошибке. Input: нет; Output: объект.

Кроме того, дек выполняет следующие дополнительные методы:

first(): возвращает первый элемент D\ если D пуст, выдается сообщение об ошибке. Input: нет; Output: объект. last(): возвращает последний элемент D; если D пуст, выдается сообщение об ошибке. Input: нет; Output: объект, size (): возвращает число элементов D. Input: нет; Output: целое число. isEmpty (): определяет, является ли D пустым.

Input: нет; Output: логическое значение.

Ниже приводится пример выполнения различных операций над изначально пустым деком.

Пример 4.5. В таблице представлены операции над изначально пустым деком D целочисленных объектов S ц их результаты. Для простоты в качестве аргументов операций используются целые числа, а не целочисленные объекты.

Операция

Output

D

, insertFirst(3)

-

(3)

insertFirst(5)

-

(5,3)

removeFirst()

5

(3)

insertLast(7)

-

(3,7)

removeFirst()

3

(7)

removel_ast()

7

0

removeFirst()

«error»

0

isEmpty()

true

0

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии