File ArrayQueue.h

↰ Parent directory (ADS/queue)

The QUEUE of the book [see File ADT.h] realized with a circular vector of m places, the place 0 following the place m - 1: the queue is in size consecutive places from the one of its front, head, so that its back is in the place :math:` ( head + size - 1 ) bmod m ` and every operation takes O( 1 ) time; the modulo is a comparison and a subtraction, since the sum is below 2 m, instead of a division.

Definition (ADS/queue/ArrayQueue.h)

Detailed Description

The contracts [see File Contract.h] are the preconditions of the book: top() and dequeue() need a queue that is not empty, enqueue() one that is not full; enqueue() ensures one item more, dequeue() one less, and the invariant is :math:` 0 leq size leq m ` with the front inside the vector. The operations are defined in ArrayQueue.tpp.

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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes