Stacks ( stack )

Definition

An instance S of the parameterized data type stack<E> is a sequence of elements of data type E, called the element type of S. Insertions or deletions of elements take place only at one end of the sequence, called the top of S. The size of S is the length of the sequence, a stack of size zero is called the empty stack.

#include < LEDA/stack.h >

Creation

stack<E>

S

creates an instance S of type stack<E>. S is initialized with the empty stack.

Operations

E	S.top()	returns the top element of S. Precondition S is not empty.
void	S.push(E x)	adds x as new top element to S.
E	S.pop()	deletes and returns the top element of S. Precondition S is not empty.
int	S.size()	returns the size of S.
bool	S.empty()	returns true if S is empty, false otherwise.
void	S.clear()	makes S the empty stack.

Implementation

Stacks are implemented by singly linked linear lists. All operations take time O(1), except clear which takes time O(n), where n is the size of the stack.