net.datastructures
Class ArrayStack<E>

java.lang.Object
  net.datastructures.ArrayStack<E>

All Implemented Interfaces:

Stack<E>

public class ArrayStack<E>
extends Object
implements Stack<E>

Implementation of the stack ADT 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. This class includes the main methods of the built-in class java.util.Stack. //end#fragment ArrayStack

Author:

Natasha Gelfand, Roberto Tamassia

See Also:

//begin#fragment ArrayStack

Field Summary

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

Constructor Summary

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

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

Method Summary

boolean	isEmpty() Testes whether the stack is empty.
static void	main(String[] args) Test our program by performing a series of operations on stacks, printing the operations performed, the returned elements and the contents of the stack involved, after each operation.
E	pop() Removes the top element from the stack.
void	push(E element) Inserts an element at the top of the stack.
int	size() Returns the number of elements in the stack.
void	status(String op, Object element) Prints status information about a recent operation and the stack.
E	top() Inspects the element at the top of the stack.
String	toString() Returns a string representation of the stack as a list of elements, with the top element at the end: [ ... , prev, top ].

Methods inherited from class java.lang.Object

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

Field Detail

capacity

protected int capacity

Length of the array used to implement the stack.

CAPACITY

public static final int CAPACITY

Default array capacity.

See Also:

Constant Field Values

S

protected E[] 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()

Initializes the stack to use an array of default length.

ArrayStack

public ArrayStack(int cap)

Initializes the stack to use an array of given length.

Parameters:

cap - length of the array.

Method Detail

size

public int size()

Returns the number of elements in the stack. This method runs in O(1) time.

Specified by:

size in interface Stack<E>

Returns:

number of elements in the stack.

isEmpty

public boolean isEmpty()

Testes whether the stack is empty. This method runs in O(1) time.

Specified by:

isEmpty in interface Stack<E>

Returns:

true if the stack is empty, false otherwise.

push

public void push(E element)
          throws FullStackException

Inserts an element at the top of the stack. This method runs in O(1) time.

Specified by:

push in interface Stack<E>

Parameters:

element - element to be inserted.

Throws:

FullStackException - if the array storing the elements is full.

top

public E top()
      throws EmptyStackException

Inspects the element at the top of the stack. This method runs in O(1) time.

Specified by:

top in interface Stack<E>

Returns:

top element in the stack.

Throws:

EmptyStackException - if the stack is empty.

pop

public E pop()
      throws EmptyStackException

Removes the top element from the stack. This method runs in O(1) time.

Specified by:

pop in interface Stack<E>

Returns:

element removed.

Throws:

EmptyStackException - if the stack is empty.

toString

public String toString()

Returns a string representation of the stack as a list of elements, with the top element at the end: [ ... , prev, top ]. This method runs in O(n) time, where n is the size of the stack.

Overrides:

toString in class Object

Returns:

textual representation of the stack.

status

public void status(String op,
                   Object element)

Prints status information about a recent operation and the stack.

Parameters:

op - operation performed

element - element returned by the operation

main

public static void main(String[] args)

Test our program by performing a series of operations on stacks, printing the operations performed, the returned elements and the contents of the stack involved, after each operation.