File Dequeue.h

↰ Parent directory (ADS/queue)

The DEQUEUE (double ended queue) of exercise 4.9, a sequence changed at both ends, which is a STACK when used at one end and a QUEUE when used at both [see File ADT.h]: realized with a LIST with pointers, every operation takes O( 1 ) time.

Definition (ADS/queue/Dequeue.h)

Detailed Description

It is the structure of the algorithm of Pape-D’Esopo (section 11.8).

The contracts [see File Contract.h]: removeHead(), removeTail(), head() and tail() need a dequeue that is not empty, and the insertions ensure one that is not, with the item at the end where it was put. The operations are defined in Dequeue.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, exercise 4.9, https://algoritmicamente.it/materiali/libro/capitoli/cap04.pdf

  1. Pape, Implementation and efficiency of Moore-algorithms for the shortest route problem, Mathematical Programming 7(1), 212-222, 1974, doi:10.1007/BF01585517

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes