File LinkedQueue.h

↰ Parent directory (ADS/queue)

A QUEUE [see File ADT.h] realized as a singly linked list with a pointer to the first cell, the front, and one to the last cell, the back (Esercizio 4.10 of the book): enqueue() appends a cell after the back and dequeue() removes the front, both in O( 1 ) time, and the queue has no bound on its size, unlike the circular vector of ArrayQueue.

Definition (ADS/queue/LinkedQueue.h)

Detailed Description

The cells come from an ObjectPool [see File ObjectPool.h], the one of a dequeue() serving the next enqueue(), so that a queue in a steady state calls no allocator and its cells stay in the cache.

The contracts [see File Contract.h]: top() and dequeue() need a queue that is not empty; enqueue() ensures that the queue is not empty, and that top() is v if the queue was empty. A queue is copied cell by cell and moved in O( 1 ) time, the one moved from left empty. The operations are defined in LinkedQueue.tpp.

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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes