scranton.stack
Class StackViaArray

java.lang.Object
  scranton.stack.StackViaArray

All Implemented Interfaces:

Stack

public class StackViaArray

extends java.lang.Object

implements Stack

An implementation of the Stack interface using an array via composition.

Specifications:

A stack S is

• Empty, S = () - maps to count == 0
• Otherwise, S = (a₀, a₁, ..., a_n-1), a_n-1 is the top of the stack and a₀ is the bottom - maps to the array, actual, with actual[0] containing the bottom object and actual[count-1] containing the top object

Initial Value:

Initial value: S=() - maps to count == 0

Field Summary

protected java.lang.Object[]	actual This field contains the array that holds the stack, actual[0] holds the bottom, actual[count-1] holds the top.
protected int	count This field contains the count of the number of objects in the stack.

Constructor Summary

StackViaArray()
Constructs a stack, the client does not specify an intial size.

StackViaArray(int size)
Constructs a stack of a size determined by the client.

Method Summary

java.lang.Object	clone()
private java.lang.Object[]	doubler(java.lang.Object[] inArray) Creates an array that is twice the size of the array passed as a parameter, actual, returns an array that is twice the size and the contents of the parameter are placed in the first half of the new array.
Stack	factory()
boolean	isEmpty() Stack does not change, returns true iff the stack is empty.
java.lang.Object	pop() Decrease the size of the stack by one by removing and returning the object at the top.
void	push(java.lang.Object item) Increase the size of the stack by one by placing item as the new top of the stack.
java.lang.Object	topOf() Stack does not change, returns the reference to the top object in the stack.
java.lang.String	toString() Returns a string representation of the stack.

Methods inherited from class java.lang.Object

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

Field Detail

actual

protected java.lang.Object[] actual

This field contains the array that holds the stack, actual[0] holds the bottom, actual[count-1] holds the top.

count

protected int count

This field contains the count of the number of objects in the stack.

Constructor Detail

StackViaArray

public StackViaArray()

Constructs a stack, the client does not specify an intial size.

StackViaArray

public StackViaArray(int size)

Constructs a stack of a size determined by the client.

Method Detail

isEmpty

public boolean isEmpty()

Stack does not change, returns true iff the stack is empty.

Specifications:

S'=S
Return S==() - maps to count == 0

Timing:

O(constant)

Specified by:

isEmpty in interface Stack

Returns:

boolean this==().

topOf

public java.lang.Object topOf()

Stack does not change, returns the reference to the top object in the stack.

Specifications:

S!=() - maps to checking if count != 0S'=S
Return a_n-1 - maps to actual[count-1], the position of the top of the stack

Timing:

O(constant)

Specified by:

topOf in interface Stack

Returns:

Object Top of stack.

Throws:

Assertion - When stack is empty

doubler

private java.lang.Object[] doubler(java.lang.Object[] inArray)

Creates an array that is twice the size of the array passed as a parameter, actual, returns an array that is twice the size and the contents of the parameter are placed in the first half of the new array.

Timing:

O(#(inArray))

Parameters:

inArray - The current array containing the stack.

Returns:

Object[] A new array that is twice the size of the original array.

push

public void push(java.lang.Object item)

Increase the size of the stack by one by placing item as the new top of the stack.

Specifications:

S'=(S, obj) - maps to count' == count+1, actual'[count'-1]==item, actual'[0..count-1]==actual[0..count-1]

Timing:

O(constant)

Specified by:

push in interface Stack

Parameters:

item - The new top of stack

pop

public java.lang.Object pop()

Decrease the size of the stack by one by removing and returning the object at the top. Note: that the stack cannot be empty.

Specifications:

S!=() - maps to checking if count != 0 S = (S', a_n-1) - maps to count'=count-1, actual'[0..count'-1]==actual[0..count'-1]
Return: a_n-1 - maps to returning actual[count-1]

Timing:

O(constant)

Specified by:

pop in interface Stack

Returns:

Object Top of stack.

Throws:

Assertion - When stack is empty

factory

public Stack factory()

clone

public java.lang.Object clone()

toString

public java.lang.String toString()

Description copied from interface: Stack

Returns a string representation of the stack. The format is, "TOP[O_top\t...\tO_bottom]BOTTOM"

Specified by:

toString in interface Stack