Главная » Java, Структуры данных и алгоритмы » Реализация очереди на основе однонаправленного связного списка

0

АТД «очередь» также осуществляется на основе однонаправленного связного списка. Для наибольшей эффективности поместим начало очереди, где можно только удалять элементы, в начало списка, а конец очереди, где можно добавлять элементы, — в хвост списка (что плохого в добавлении элементов в начале списка и их удалении в конце?). Не следует забывать о необходимости сохранения ссылок на начальный и конечный узлы списка. Вместо описания всех подробностей представим во фрагменте кода 4.12 Java-реализацию базовых методов работы с очередями.

public void enqueue(Object obj) { Node node = new Node(); node.setElement(obj);

node.setNext(null); // узел будет новым концевым узлом if (size == 0)

head = node; //особый случай, если до этого очередь была пуста else

tail.setNext(node); // добавляет узел в конец списка tail = node; // перенаправляет ссылку к концевому узлу size++;

}

public Object dequeue() throws QueueEmptyException { Object obj; if (size == 0)

throw new QueueEmptyExceptionfQueue is empty."); obj = head.getElement(); head = head.getNext();

size————————— ;

if (size == 0)

tail = null; // сейчас очередь пуста return obj;

}

Фрагмент кода 4.12. Методы enqueue и dequeue при реализации очереди на основе однонаправленного связного списка

Каждый метод при реализации очереди на основе однонаправленного связного списка выполняется за время 0(1). Кроме того, не нужно указывать максимальный размер очереди, как в случае реализации на основе массива, и это достигается за счет уменьшения пространства, выделяемого для каждого элемента. В то же время методы, используемые при реал и- зации очереди на основе однонаправленного связного списка, являются более сложными, так как необходимо следить за обработкой особых случаев, например, пустая очередь перед операцией enqueue или очередь становится пустой после операции dequeue.

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

По теме:

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