Skip to content

Stack

final class Stack<Type>

Last-in first-out (LIFO) stack. Provides constant-time operations at the top of the stack, and linear-time operations elsewhere.

  • Type Element type. Must be default-constructible.

The data structure is arranged as a singly-linked list:

graph LR this --"top()"--> n[n] --> nm1[n-1] --> nm2[n-2] --> nm3(...)
The member function top() is used to retrieve the top (nth) element, which can be done in O(1) time.

Note

As a recursive and singly-linked data structure, Stack has excellent performance properties under Birch's lazy deep copy mechanism.

Attention

Large recursive data structures can cause an execution stack overflow on destruction that usually manifests as a segmentation fault. Possible solutions include:

  1. Use an array (Type[_]) or Array instead.
  2. Remove items one-by-one before the object goes out of scope.
  3. Increase the execution stack size with the shell command ulimit.

Member Functions

Name Description
size Number of elements.
empty Is this empty?
clear Clear all elements.
top Get the top element.
push Push an element onto the top.
push Push a new default-constructed element onto the top and return it.
pop Pop an element from the top.
walk Obtain an iterator.

Member Function Details

clear

function clear()

Clear all elements.

empty

function empty() -> Boolean

Is this empty?

pop

function pop()

Pop an element from the top.

push

function push(x:Type)

Push an element onto the top.

  • x the element.

function push()

Push a new default-constructed element onto the top and return it.

size

function size() -> Integer

Number of elements.

top

function top() -> Type

Get the top element.

walk

function walk() -> Iterator<Type>

Obtain an iterator.

Returns an iterator across elements from top to bottom.