Reference

std/collections/stack

std/collections/src/stack.trb

LIFO: Stack, with ArrayStack and the persistent ConsStack as its implementations.

push, pop and peek all work on the top. There is no index: the only way to see an item below the top is to pop down to it or to iterate the whole stack.

Related

trait Stack

trait Stack<Item> with Iterate<Item>, Length

LIFO stack. Iterates from top to bottom, which is the order it hands items out in.

The words everybody knows for a stack: push puts an item on top, pop takes the top one off, and peek looks at it without taking it.

Examples

var pending = Stack.of 1, 2, 3
pending.push 4
print pending.pop()
print pending.peek()
print pending.toList()

Related

  • Queue - the FIFO sibling.
  • Iterate - the pipeline vocabulary (map, filter, fold, ...), from the top down.

fn of

static fn of(...items: Item): Self where Self: From<Iterate<Item>>

Builds a stack from its arguments. The last item ends up on top. Answers Self.

fn push

var fn push(value: Item)

Puts value on top, in place.

fn pop

var fn pop(): Item?

Takes the top item off and answers it, or None if the stack is empty.

fn clear

var fn clear()

Removes every item, in place.

fn compact

var fn compact()

Hands back storage held beyond the length. The default does nothing: a storage without spare room has none.

fn peek

fn peek(): Item?

The item pop would take, without taking it, or None if the stack is empty.

fn count

fn count(): Int

How many items there are. A stack knows its size, so counting it does not walk it.

extend Stack<Item> with From<Iterate<Item>>

extend<Item> Stack<Item> with From<Iterate<Item>>

The factory picks the default implementation: what Stack.of and a pipeline's to<Stack<Item>>() build.

fn from

static fn from(items: Iterate<Item>): Self

extend Stack<Item> with Equals

extend<Item: Equals> Stack<Item> with Equals

Equal when they hold the same items in the same order, which for a stack is from the top down - the order it iterates in, and the only order a reader of one can see.

A collection is Equals when its items are, exactly as a tuple is: values compare structurally, and which implementation carries the items is nobody's business.

fn equals

fn equals(other: Self): Bool

extend Stack<Item> with Hash

extend<Item: Hash> Stack<Item> with Hash

Order-dependent, like List.hash and unlike Set.hash: two stacks with the same items in a different order are not equal, so they need not hash alike.

Hash requires Equals, and the Equals implementation above satisfies that: Item: Hash implies Item: Equals.

fn hash

fn hash(): Int

type ArrayStack

type ArrayStack<Item> with Stack<Item>, From<Iterate<Item>>

The only implementation of Stack: a List used from the end. A value, because it consists of values - nothing had to be done for that.

fn from

static fn from(items: Iterate<Item>): Self

Builds the stack from items, with the last one on top.

fn push

var fn push(value: Item)

Puts value on top, in place.

fn pop

var fn pop(): Item?

Takes the top item off and answers it, or None if empty.

fn peek

fn peek(): Item?

The top item, or None if empty: the end of the list underneath, without walking it.

fn clear

var fn clear()

Removes every item, in place.

fn compact

var fn compact()

Hands back what the list underneath holds beyond its length; see List.compact.

fn length

fn length(): Int

How many items there are.

fn iterate

fn iterate(): Iterator<Item>

A cursor from top to bottom: the reverse of insertion order.

type ConsStackIterator

type ConsStackIterator<Item> with Iterator<Item>

The cursor over a ConsStack: it holds the cell it stands on, which keeps that cell and everything below alive, so a change to the stack while it is iterated is never seen here.

fn next

var fn next(): Item?

The item of the cell the cursor stands on, or None once it is past the bottom.

type ConsStack

type ConsStack<Item> with Stack<Item>, From<Iterate<Item>>

A persistent stack: a cons list of cells, each holding an item and the stack below it. A copy of a ConsStack is the reference to its top cell and nothing else, so var rest = stack shares the whole tail, and pushing or popping on either one builds or drops one cell without touching the other.

Cost

Operation Cost
push, pop, peek, length, clear O(1), nothing is copied
copy (var rest = stack) O(1), the tail is shared
iterate, equals, hash O(n), top to bottom

The price against ArrayStack is one allocation per push and no contiguous storage; the gain is keeping many versions of one stack at the price of one cell each. It fits backtracking, undo and a parser's context.

Examples

var history = ConsStack.of 1, 2, 3
const saved = history
history.push 4
print history.toList()
print saved.toList()

fn from

static fn from(items: Iterate<Item>): Self

Builds the stack from items, with the last one on top.

fn push

var fn push(value: Item)

Puts value on top, in place: one new cell over the old top, which the stack below shares.

fn pop

var fn pop(): Item?

Takes the top item off and answers it, or None if empty. The cell is dropped; the tail stays where it is.

fn peek

fn peek(): Item?

The top item, or None if empty.

fn clear

var fn clear()

Removes every item, in place. Cells that another copy still holds stay alive for that copy.

fn length

fn length(): Int

How many items there are, without walking the cells.

fn iterate

fn iterate(): Iterator<Item>

A cursor from top to bottom.