Linked queue

1/******************************************************************************2 *  Compilation:  javac LinkedQueue.java3 *  Execution:    java LinkedQueue < input.txt4 *  Dependencies: StdIn.java StdOut.java5 *  Data files:   https://algs4.cs.princeton.edu/13stacks/tobe.txt6 *7 *  A generic queue, implemented using a singly linked list.8 *9 *  % java Queue < tobe.txt10 *  to be or not to be (2 left on queue)11 *12 ******************************************************************************/13 14//package edu.princeton.cs.algs4;15 16import java.util.Iterator;17import java.util.NoSuchElementException;18 19/**20 *  The {@code LinkedQueue} class represents a first-in-first-out (FIFO)21 *  queue of generic items.22 *  It supports the usual <em>enqueue</em> and <em>dequeue</em>23 *  operations, along with methods for peeking at the first item,24 *  testing if the queue is empty, and iterating through25 *  the items in FIFO order.26 *  <p>27 *  This implementation uses a singly linked list with a non-static nested class28 *  for linked-list nodes.  See {@link Queue} for a version that uses a static nested class.29 *  The <em>enqueue</em>, <em>dequeue</em>, <em>peek</em>, <em>size</em>, and <em>is-empty</em>30 *  operations all take constant time in the worst case.31 *  <p>32 *  For additional documentation, see <a href="https://algs4.cs.princeton.edu/13stacks">Section 1.3</a> of33 *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.34 *35 *  @author Robert Sedgewick36 *  @author Kevin Wayne37 */38public class LinkedQueue<Item> implements Iterable<Item> {39    private int n;         // number of elements on queue40    private Node first;    // beginning of queue41    private Node last;     // end of queue42 43    // helper linked list class44    private class Node {45        private Item item;46        private Node next;47    }48 49    /**50     * Initializes an empty queue.51     */52    public LinkedQueue() {53        first = null;54        last  = null;55        n = 0;56        assert check();57    }58 59    /**60     * Is this queue empty?61     * @return true if this queue is empty; false otherwise62     */63    public boolean isEmpty() {64        return first == null;65    }66 67    /**68     * Returns the number of items in this queue.69     * @return the number of items in this queue70     */71    public int size() {72        return n;73    }74 75    /**76     * Returns the item least recently added to this queue.77     * @return the item least recently added to this queue78     * @throws java.util.NoSuchElementException if this queue is empty79     */80    public Item peek() {81        if (isEmpty()) throw new NoSuchElementException("Queue underflow");82        return first.item;83    }84 85    /**86     * Adds the item to this queue.87     * @param item the item to add88     */89    public void enqueue(Item item) {90        Node oldlast = last;91        last = new Node();92        last.item = item;93        last.next = null;94        if (isEmpty()) first = last;95        else           oldlast.next = last;96        n++;97        assert check();98    }99 100    /**101     * Removes and returns the item on this queue that was least recently added.102     * @return the item on this queue that was least recently added103     * @throws java.util.NoSuchElementException if this queue is empty104     */105    public Item dequeue() {106        if (isEmpty()) throw new NoSuchElementException("Queue underflow");107        Item item = first.item;108        first = first.next;109        n--;110        if (isEmpty()) last = null;   // to avoid loitering111        assert check();112        return item;113    }114 115    /**116     * Returns a string representation of this queue.117     * @return the sequence of items in FIFO order, separated by spaces118     */119    public String toString() {120        StringBuilder s = new StringBuilder();121        for (Item item : this)122            s.append(item + " ");123        return s.toString();124    }125 126    // check internal invariants127    private boolean check() {128        if (n < 0) {129            return false;130        }131        else if (n == 0) {132            if (first != null) return false;133            if (last  != null) return false;134        }135        else if (n == 1) {136            if (first == null || last == null) return false;137            if (first != last)                 return false;138            if (first.next != null)            return false;139        }140        else {141            if (first == null || last == null) return false;142            if (first == last)      return false;143            if (first.next == null) return false;144            if (last.next  != null) return false;145 146            // check internal consistency of instance variable n147            int numberOfNodes = 0;148            for (Node x = first; x != null && numberOfNodes <= n; x = x.next) {149                numberOfNodes++;150            }151            if (numberOfNodes != n) return false;152 153            // check internal consistency of instance variable last154            Node lastNode = first;155            while (lastNode.next != null) {156                lastNode = lastNode.next;157            }158            if (last != lastNode) return false;159        }160 161        return true;162    }163 164 165    /**166     * Returns an iterator that iterates over the items in this queue in FIFO order.167     * @return an iterator that iterates over the items in this queue in FIFO order168     */169    public Iterator<Item> iterator()  {170        return new LinkedIterator();171    }172 173    // a linked-list iterator174    private class LinkedIterator implements Iterator<Item> {175        private Node current = first;176 177        public boolean hasNext() {178            return current != null;179        }180 181        public Item next() {182            if (!hasNext()) throw new NoSuchElementException();183            Item item = current.item;184            current = current.next;185            return item;186        }187    }188 189 190    /**191     * Unit tests the {@code LinkedQueue} data type.192     *193     * @param args the command-line arguments194     */195    public static void main(String[] args) {196        LinkedQueue<String> queue = new LinkedQueue<String>();197        while (!StdIn.isEmpty()) {198            String item = StdIn.readString();199            if (!item.equals("-"))200                queue.enqueue(item);201            else if (!queue.isEmpty())202                StdOut.print(queue.dequeue() + " ");203        }204        StdOut.println("(" + queue.size() + " left on queue)");205    }206}207 208/******************************************************************************209 *  Copyright 2002-2022, Robert Sedgewick and Kevin Wayne.210 *211 *  This file is part of algs4.jar, which accompanies the textbook212 *213 *      Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,214 *      Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.215 *      http://algs4.cs.princeton.edu216 *217 *218 *  algs4.jar is free software: you can redistribute it and/or modify219 *  it under the terms of the GNU General Public License as published by220 *  the Free Software Foundation, either version 3 of the License, or221 *  (at your option) any later version.222 *223 *  algs4.jar is distributed in the hope that it will be useful,224 *  but WITHOUT ANY WARRANTY; without even the implied warranty of225 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the226 *  GNU General Public License for more details.227 *228 *  You should have received a copy of the GNU General Public License229 *  along with algs4.jar.  If not, see http://www.gnu.org/licenses.230 ******************************************************************************/231