net.datastructures
Class ArrayStack

java.lang.Object
  net.datastructures.ArrayStack

All Implemented Interfaces:

Stack

public class ArrayStack

extends Object

implements Stack

Implementation of the Stack interface using a fixed-length array. An exception is thrown if a push operation is attempted when the size of the stack is equal to the length of the array.

Author:

Natasha Gelfand, Roberto Tamassia

See Also:

FullStackException

Field Summary

protected int	capacity Length of the array used to implement the stack.
static int	CAPACITY Default length of the array used to implement the stack.
protected Object[]	S Array used to implement the stack.
protected int	top Index of the top element of the stack in the array.

Constructor Summary

ArrayStack()
Initialize the stack to use an array of default length CAPACITY.

ArrayStack(int cap)
Initialize the stack to use an array of given length.

Method Summary

boolean	isEmpty() O(1) time.
Object	pop() O(1) time.
void	push(Object obj) O(1) time.
int	size() O(1) time.
Object	top() O(1) time.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

CAPACITY

public static final int CAPACITY

Default length of the array used to implement the stack.

See Also:

Constant Field Values

capacity

protected int capacity

Length of the array used to implement the stack.

S

protected Object[] S

Array used to implement the stack.

top

protected int top

Index of the top element of the stack in the array.

Constructor Detail

ArrayStack

public ArrayStack()

Initialize the stack to use an array of default length CAPACITY.

ArrayStack

public ArrayStack(int cap)

Initialize the stack to use an array of given length.

Parameters:

cap - length of the array.

Method Detail

size

public int size()

O(1) time.

Specified by:

size in interface Stack

Returns:

number of elements in the stack.

isEmpty

public boolean isEmpty()

O(1) time.

Specified by:

isEmpty in interface Stack

Returns:

true if the stack is empty, false otherwise.

push

public void push(Object obj)
          throws FullStackException

O(1) time.

Specified by:

push in interface Stack

Parameters:

obj - element to be inserted.

Throws:

FullStackException - if the array is full.

top

public Object top()
           throws EmptyStackException

O(1) time.

Specified by:

top in interface Stack

Returns:

top element in the stack.

Throws:

EmptyStackException - if the stack is empty.

pop

public Object pop()
           throws EmptyStackException

O(1) time.

Specified by:

pop in interface Stack

Returns:

element removed.

Throws:

EmptyStackException - if the stack is empty.