Package edu.princeton.cs.algs4

Class Stack<Item>

  • Type Parameters:
    Item - the generic type each item in this stack
    All Implemented Interfaces:
    Iterable<Item>
    public class Stack<Item>
extends Object
implements 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.

    Author:
    Robert Sedgewick, Kevin Wayne

    • 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:
        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

      • toString

        public String toString()
        Returns a string representation of this stack.
        Overrides:
        toString in class Object
        Returns:
        the sequence of items in this stack in LIFO order, separated by spaces

      • 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.
        Parameters:
        args - the command-line arguments