FlexOr.container
Class Stack

java.lang.Object
  FlexOr.container.Stack

All Implemented Interfaces:

Container, java.lang.Cloneable

public class Stack
extends java.lang.Object
implements Container

The stack implements container which has the basic add and remove methods that a stack needs. Storage can be implemented by any Sequence type with the default being a singly linked list. The choice of storage model is made at stack creation time. The front of the sequence is the top of the stack.

Note that using Vector (not possible until Vector implements Sequence) gives O(n) gives O(n) performance for remove() (pop) as the entire contents of the Vector is shifted. For a Vector it would be better to use the tail end but this would give poor performance for a singly linked list implement for pop as it would be O(n) due needing to find the predecessor. For an array implementation of stack storage it would be best to use a CircularArray -- element[0] follows element[size-1] creating a ring-like structure.

Version:

1.0 1999 Jan 16

Author:

Gunnar Gotshalks

See Also:

SLList, Sequence, Container

Constructor Summary

Stack()
The default constructor selects a singly linked list as the storage container.

Stack(Sequence container)
The constructor permits the user to specify the type of storage container.

Method Summary

void	add(java.lang.Object obj) Adds obj to the top of the stack.
java.lang.Object	clone() Return a shallow copy of the stack.
boolean	contains(java.lang.Object obj) Determines whether an element is in the stack.
java.util.Enumeration<java.lang.Object>	elements() Returns an enumerator over the whole stack.
boolean	equals(java.lang.Object obj) Check for equality of contents of two stacks.
boolean	isEmpty() Check if the stack is empty.
boolean	isFull() Check if the stack is full.
java.lang.Object	remove() Return the top element in the stack.
void	removeAll() Empty the stack.
int	size() Returns the number of elements in the stack.
java.lang.String	toString() Return a string representation of the contents.

Methods inherited from class java.lang.Object

getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

Stack

public Stack()

The default constructor selects a singly linked list as the storage container.

Stack

public Stack(Sequence container)

The constructor permits the user to specify the type of storage container.

The input container is cloned to minimize side effects of sharing.

Requires: container is empty
Ensures: the stack uses the input storage type.

Throws:

NotEmptyException - thrown when expecting an empty container but getting a non empty container.

Method Detail

contains

public boolean contains(java.lang.Object obj)

Determines whether an element is in the stack. Not really a stack operation but useful for testing and debugging.

Specified by:

contains in interface Container

elements

public java.util.Enumeration<java.lang.Object> elements()

Returns an enumerator over the whole stack.

Specified by:

elements in interface Container

Throws:

NoSuchElementException - when nextElement is called with an empty enumeration sequence.

isEmpty

public boolean isEmpty()

Check if the stack is empty.

Specified by:

isEmpty in interface Container

isFull

public boolean isFull()

Check if the stack is full.

Specified by:

isFull in interface Container

size

public int size()

Returns the number of elements in the stack.

Specified by:

size in interface Container

add

public void add(java.lang.Object obj)

Adds obj to the top of the stack.

Requires: True
Ensures: sequence = obj ^ old sequence

Specified by:

add in interface Container

removeAll

public void removeAll()

Empty the stack.

Requires: True
Ensures: sequence = null // the empty sequence.

Specified by:

removeAll in interface Container

remove

public java.lang.Object remove()

Return the top element in the stack. If the stack is empty, return null. Should not store null in the list but can disambiguate with a check on not empty before the remove.

Requires: isEmpty = false
Ensures: old sequence = obj ^ sequence

Specified by:

remove in interface Container

clone

public java.lang.Object clone()

Return a shallow copy of the stack.

Requires: True
Ensures: result = copy of stack

Specified by:

clone in interface Container

Overrides:

clone in class java.lang.Object

toString

public java.lang.String toString()

Return a string representation of the contents.

Requires: True
Ensures: result = string representation of contents

Specified by:

toString in interface Container

Overrides:

toString in class java.lang.Object

equals

public boolean equals(java.lang.Object obj)

Check for equality of contents of two stacks. By equality we mean an equal sequence of elements as returned by the Enumerator for each stack.

Requires: True
Ensures: result = true => contents are equal
                result = false => contents are not equal

Specified by:

equals in interface Container

Overrides:

equals in class java.lang.Object