edu.princeton.cs.algs4

Class Stack<Item>

java.lang.Object

edu.princeton.cs.algs4.Stack<Item>

Type Parameters:

Item - the generic type of an item in this stack

All Implemented Interfaces:

java.lang.Iterable<Item>

public class Stack<Item>
extends java.lang.Object
implements java.lang.Iterable<Item>

The Stack 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 singly linked list with a static nested class for linked-list nodes. See LinkedStack for the version from the textbook that uses a non-static nested class. See ResizingArrayStack for a version that uses a resizing array. The push, pop, peek, size, and is-empty operations all take constant time in the worst case.

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

Constructor Summary

Constructors

Constructor and Description
Stack() Initializes an empty stack.

Method Summary

Modifier and Type	Method and Description
boolean	isEmpty() Returns true if this stack is empty.
java.util.Iterator<Item>	iterator() Returns an iterator to this stack that iterates through the items in LIFO order.
static void	main(java.lang.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 this stack.
java.lang.String	toString() Returns a string representation of this stack.

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

Stack

public Stack()

Initializes an empty stack.

Method Detail

isEmpty

public boolean isEmpty()

Returns true if this stack is empty.

Returns:

true if this stack is empty; false otherwise

size

public int size()

Returns the number of items in this stack.

Returns:

the number of items in this 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:

java.util.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:

java.util.NoSuchElementException - if this stack is empty

toString

public java.lang.String toString()

Returns a string representation of this stack.

Overrides:

toString in class java.lang.Object

Returns:

the sequence of items in this stack in LIFO order, separated by spaces

iterator

public java.util.Iterator<Item> iterator()

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

Specified by:

iterator in interface java.lang.Iterable<Item>

Returns:

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

main

public static void main(java.lang.String[] args)

Unit tests the Stack data type.

Parameters:

args - the command-line arguments