net.datastructures
Class NodeStack<E>

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

All Implemented Interfaces:

Stack<E>

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

Implementation of the stack ADT by means of a singly linked list.

Author:

Natasha Gelfand, Roberto Tamassia

See Also:

Node

Field Summary

protected int	size
protected Node<E>	top

Constructor Summary

NodeStack()
Creates an empty stack.

Method Summary

boolean	isEmpty() Return whether the stack is empty.
static void	main(String[] args) Test program that performs a series of operations on on a stack and prints the operation performed, the returned element and the content of the stack after each operation.
E	pop() Remove the top element from the stack.
void	push(E elem) Insert an element at the top of the stack.
int	size() Return the number of elements in the stack.
static void	status(Stack S, String op, Object element) Prints information about an operation and the stack.
E	top() Inspect 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

top

protected Node<E> top

size

protected int size

Constructor Detail

NodeStack

public NodeStack()

Creates an empty stack.

Method Detail

size

public int size()

Description copied from interface: Stack

Return the number of elements in the stack.

Specified by:

size in interface Stack<E>

Returns:

number of elements in the stack.

isEmpty

public boolean isEmpty()

Description copied from interface: Stack

Return whether the stack is empty.

Specified by:

isEmpty in interface Stack<E>

Returns:

true if the stack is empty, false otherwise.

push

public void push(E elem)

Description copied from interface: Stack

Insert an element at the top of the stack.

Specified by:

push in interface Stack<E>

Parameters:

elem - to be inserted.

top

public E top()
      throws EmptyStackException

Description copied from interface: Stack

Inspect the element at the top of the stack.

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

Description copied from interface: Stack

Remove the top element from the stack.

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 static void status(Stack S,
                          String op,
                          Object element)

Prints information about an operation and the stack.

Parameters:

op - operation performed

element - element returned by the operation

main

public static void main(String[] args)

Test program that performs a series of operations on on a stack and prints the operation performed, the returned element and the content of the stack after each operation.