File MultiStack.h

↰ Parent directory (ADS/stack)

k STACKs in one structure [see File ADT.h], beyond the book: the items of all the stacks are cells of a single vector, each linked to the cell below it in its stack, and the free cells form a further list, so that the stacks share the space and none is full while the others have room (the vector doubles when all the cells are used).

Definition (ADS/stack/MultiStack.h)

Detailed Description

push(), pop() and top() on the stack i take O( 1 ) amortized time; the stacks are numbered from 0. It generalizes the two stacks in one vector of exercise 4.7.

The contracts [see File Contract.h]: k > 0, a stack i in [ 0 , k ), and a stack that is not empty for top() and pop(); the invariant is that each cell is in exactly one stack or in the free list, and that the sizes count the cells of each stack. The operations are defined in MultiStack.tpp.

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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes