Alice Project

The Stack structure

________ Synopsis ____________________________________________________

    signature STACK
    structure Stack : STACK

An imperative stack abstraction.

________ Import ______________________________________________________

    import signature STACK from "x-alice:/lib/data/STACK-sig"
    import structure Stack from "x-alice:/lib/data/Stack"

________ Interface ___________________________________________________

    signature STACK =
	eqtype 'a stack
	type t = stack

	exception Empty

	val stack :    unit -> 'a stack
	val clone :    'a stack -> 'a stack
	val push :     'a stack * 'a -> unit
	val pop :      'a stack -> 'a
	val peek :     'a stack -> 'a option
	val purge :    'a stack -> unit
	val isEmpty :  'a stack -> bool
	val size :     'a stack -> int

________ Description _________________________________________________

eqtype 'a stack
type 'a t = 'a stack

The type of polymorphic stacks. Like ref and array, the stack type always admits equality, independently from its argument.

exception Empty

Used to indicate invalid accesses to an empty stack. Equal to List.Empty.

stack ()

Creates a new stack that is initially empty.

clone st

Creates a copy of the stack st.

push (st, x)

Pushes the value x onto the stack st.

pop st

Removes and returns the value last pushed onto st. Raises Empty if st is empty.

peek st

Returns NONE if st is empty, otherwise SOME x, where x is the value last pushed onto st.

purge st

Removes all elements from the stack st, leaving it empty.

isEmpty st

Returns true if the stack st is empty, false otherwise. Equivalent to (size st = 0) and Option.isNone (peek st).

size st

Returns the number of values that have been pushed but not yet popped from the stack st.

last modified 2007/Mar/30 17:10