File ArrayStack.h

↰ Parent directory (ADS/stack)

The STACK of the book [see File ADT.h] realized with a vector of a given capacity: the n items are in the first n places, the top in the place n - 1, so that every operation takes O( 1 ) time.

Definition (ADS/stack/ArrayStack.h)

Detailed Description

The contracts [see File Contract.h] are the preconditions of the book: top() and pop() need a stack that is not empty (size > 0), push() one that is not full (size < capacity); push() ensures one item more and v on top, pop() one item less and the old top returned, which is the constructive form of the axioms :math:` top( push( S , v ) ) = v ` and :math:` pop( push( S , v ) ) = S ` [see File ADT.h]. The invariant is :math:` 0 leq n leq capacity `. A stack is copied item by item and moved in O( 1 ) time, and two stacks are equal if they hold the same items in the same order, whatever their capacities. The operations are defined in ArrayStack.tpp.

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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes