File StackAlgorithms.h

↰ Parent directory (ADS/stack)

Algorithms that use a STACK [see File ADT.h] only through its operations, beyond the book:

Definition (ADS/stack/StackAlgorithms.h)

Detailed Description

  • isPalindrome(), the characters pushed and then popped against the string from its start, O( n );

  • sortStack(), which sorts a stack with its own operations and the recursion: a pass pops two items, pushes back the larger, sorts the rest recursively and pushes the smaller on top, so that the least item rises to the top; n passes sort the stack, the least on top, in :math:` O( n^2 ) `;

  • removeGreater(), which removes the items larger than k keeping the order of the others, with an auxiliary stack;

  • forEachBottomUp(), which visits the items from the bottom to the top and leaves the stack as it was: the top is popped, the rest visited recursively, then the top visited and pushed back, in O( n ) time and O( n ) space for the recursion.

The contracts [see File Contract.h]: sortStack() ensures a sorted stack with the same number of items, and removeGreater() a stack with no item larger than k, and forEachBottomUp() the stack as it was; all are audits, checked by popping the stack and pushing it back. The algorithms are defined in StackAlgorithms.tpp.

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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions