Package edu.princeton.cs.algs4

Class ResizingArrayQueue<Item>

  • All Implemented Interfaces:
    Iterable<Item>
    public class ResizingArrayQueue<Item>
extends Object
implements Iterable<Item>
    The ResizingArrayQueue class represents a first-in-first-out (FIFO) queue of generic items. It supports the usual enqueue and dequeue operations, along with methods for peeking at the first item, testing if the queue is empty, and iterating through the items in FIFO 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 enqueue and dequeue 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 Detail

      • ResizingArrayQueue

        public ResizingArrayQueue()
        Initializes an empty queue.

    • Method Detail

      • isEmpty

        public boolean isEmpty()
        Is this queue empty?
        Returns:
        true if this queue is empty; false otherwise

      • size

        public int size()
        Returns the number of items in this queue.
        Returns:
        the number of items in this queue

      • enqueue

        public void enqueue​(Item item)
        Adds the item to this queue.
        Parameters:
        item - the item to add

      • dequeue

        public Item dequeue()
        Removes and returns the item on this queue that was least recently added.
        Returns:
        the item on this queue that was least recently added
        Throws:
        NoSuchElementException - if this queue is empty

      • peek

        public Item peek()
        Returns the item least recently added to this queue.
        Returns:
        the item least recently added to this queue
        Throws:
        NoSuchElementException - if this queue is empty

      • iterator

        public Iterator<Item> iterator()
        Returns an iterator that iterates over the items in this queue in FIFO order.
        Specified by:
        iterator in interface Iterable<Item>
        Returns:
        an iterator that iterates over the items in this queue in FIFO order

      • main

        public static void main​(String[] args)
        Unit tests the ResizingArrayQueue data type.
        Parameters:
        args - the command-line arguments