edu.princeton.cs.algorithms

Class ResizingArrayStack<Item>

java.lang.Object

edu.princeton.cs.algorithms.ResizingArrayStack<Item>

All Implemented Interfaces:

Iterable<Item>

public class ResizingArrayStack<Item>
extends Object
implements Iterable<Item>

The ResizingArrayStack class represents a last-in-first-out (LIFO) stack of generic items. It supports the usual push and pop operations, along with methods for peeking at the top item, testing if the stack is empty, and iterating through the items in LIFO order.

This implementation uses a resizing array, which double the underlying array when it is full and halves the underlying array when it is one-quarter full. The push and pop operations take constant amortized time. The size, peek, and is-empty operations takes constant time in the worst case.

For additional documentation, see Section 1.3 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors

Constructor and Description
ResizingArrayStack() Initializes an empty stack.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	isEmpty() Is this stack empty?
Iterator<Item>	iterator() Returns an iterator to this stack that iterates through the items in LIFO order.
static void	main(String[] args) Unit tests the Stack data type.
Item	peek() Returns (but does not remove) the item most recently added to this stack.
Item	pop() Removes and returns the item most recently added to this stack.
void	push(Item item) Adds the item to this stack.
int	size() Returns the number of items in the stack.

Methods inherited from class java.lang.Object

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

Constructor Detail

ResizingArrayStack

public ResizingArrayStack()

Initializes an empty stack.

Method Detail

isEmpty

public boolean isEmpty()

Is this stack empty?

Returns:

true if this stack is empty; false otherwise

size

public int size()

Returns the number of items in the stack.

Returns:

the number of items in the stack

push

public void push(Item item)

Adds the item to this stack.

Parameters:

item - the item to add

pop

public Item pop()

Removes and returns the item most recently added to this stack.

Returns:

the item most recently added

Throws:

NoSuchElementException - if this stack is empty

peek

public Item peek()

Returns (but does not remove) the item most recently added to this stack.

Returns:

the item most recently added to this stack

Throws:

NoSuchElementException - if this stack is empty

iterator

public Iterator<Item> iterator()

Returns an iterator to this stack that iterates through the items in LIFO order.

Specified by:

iterator in interface Iterable<Item>

Returns:

an iterator to this stack that iterates through the items in LIFO order.

main

public static void main(String[] args)

Unit tests the Stack data type.