Class LinkedStack<Item>

java.lang.Object

LinkedStack<Item>

All Implemented Interfaces:

java.lang.Iterable<Item>

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

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

For additional documentation, see algs4.cs.princeton.edu/13stacks/ or Section 1.3, page 120, of "Algorithms, 4th Edition", by Robert Sedgewick and Kevin Wayne.

Constructor Summary

Constructors

Constructor and Description
LinkedStack() Initializes an empty stack.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	isEmpty() Is this stack empty? Returns true if this stack is empty; false otherwise.
java.util.Iterator<Item>	iterator() Returns an iterator that iterates through the items of this stack in LIFO order.
static void	main(java.lang.String[] args) Unit test of this LinkedStack 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 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

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

Constructor Detail

LinkedStack

public LinkedStack()

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 this stack.

push

public void push(Item item)

Adds item to this stack.

pop

public Item pop()

Removes and returns the item most recently added to this stack. 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. Throws java.util.NoSuchElementException if the stack is empty.

toString

public java.lang.String toString()

Returns a string representation of this stack. Returns the sequence of items in the stack in LIFO order, separated by spaces.

Overrides:

toString in class java.lang.Object

iterator

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

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

Specified by:

iterator in interface java.lang.Iterable<Item>

main

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

Unit test of this LinkedStack data type. Builds a stack of strings from the strings given on standard input; each item entered is pushed onto the stack, unless item is "-", in which case an item is popped from the stack. After input stream ends (this is signaled by typing Ctrl-z if you are using Windows or Ctrl-d if you are using Unix), prints the number of items left on the stack.