next up previous contents index
Next: Queues ( queue ) Up: Basic Data Types Previous: Two Dimensional Arrays (   Contents   Index


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/core/stack.h >

Creation

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

Operations

const E& S.top() returns the top element of S.
Precondition S is not empty.

void S.push(const 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.


next up previous contents index
Next: Queues ( queue ) Up: Basic Data Types Previous: Two Dimensional Arrays (   Contents   Index
Christian Uhrig 2017-04-07