Bounded Stacks (b_stack)

Definition

An instance S of the parameterized data type b_stack<E> is a stack (see section Stacks) of bounded size.

Creation

b_stack<E>	S(int n);	creates an instance S of type b_stack<E> that can hold up to n elements. S is initialized with the empty stack.

Operations

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

Implementation

Bounded stacks are implemented by C++vectors. All operations take time O(1). The space requirement is O(n).