package com.qiusongde;

import java.util.Iterator;

import java.util.NoSuchElementException;

import edu.princeton.cs.algs4.StdIn;

import edu.princeton.cs.algs4.StdOut;

public class Queue<Item> implements Iterable<Item> {

    private Node first;

    private Node last;

    private int n;

    private class Node {

        Item item;

        Node next;

    }

    public Queue() {

        first = null;

        last = null;

        n = 0;

    }

    public boolean isEmpty() {

        return first == null;

    }

    public int size() {

        return n;

    }

    public void enqueue(Item item) {

        //add item to the end

        Node oldlast = last;

        last = new Node();

        last.item = item;

        last.next = null;//end

        if(isEmpty())

            first = last;

        else

            oldlast.next = last;

        n++;

    }

    public Item dequeue() {

        if(isEmpty())

            throw new NoSuchElementException("Queue is empty");

        Item item = first.item;

        first = first.next;

        if(isEmpty())

            last = null;

        n--;

        return item;

    }

    @Override

    public Iterator<Item> iterator() {

        return new QueueIterator();

    }

    private class QueueIterator implements Iterator<Item> {

        private Node current = first;

        @Override

        public boolean hasNext() {

            return current != null;

        }

        @Override

        public Item next() {

            if(!hasNext())

                throw new NoSuchElementException("Queue is empty");

            Item item = current.item;

            current = current.next;

            return item;

        }

        @Override

        public void remove() {

            throw new UnsupportedOperationException();

        }

    }

    public static void main(String[] args) {

        Queue<String> queue = new Queue<String>();

        StdOut.println("Initialized size:" + queue.size());

        while (!StdIn.isEmpty()) {

            String item = StdIn.readString();

            if (!item.equals("-")) {

                queue.enqueue(item);

                StdOut.println("enqueue success:" + item + " size:" + queue.size());

                StdOut.print("Left on queue: ");

                for (String s : queue) {

                    StdOut.print(s + " ");

                }

                StdOut.println();

            } else {

                if(queue.isEmpty())

                    StdOut.println("dequeue error, queue empty");

                else {

                    StdOut.println("dequeue success:" + queue.dequeue() + " size:" + queue.size());

                    StdOut.print("Left on queue: ");

                    for (String s : queue) {

                        StdOut.print(s + " ");

                    }

                    StdOut.println();

                }

            }

        }

    }

}

package com.qiusongde;

import edu.princeton.cs.algs4.StdIn;

import edu.princeton.cs.algs4.StdOut;

public class Exercise1315 {

    public static void main(String[] args) {

        int k = Integer.parseInt(args[0]);

        Queue<String> queue = new Queue<>();

        while(!StdIn.isEmpty()) {

            String s = StdIn.readString();

            queue.enqueue(s);

        }

        int size = queue.size();

        for(int i = 0; i < size - k; i++) {

            queue.dequeue();

        }

        StdOut.println(queue.dequeue());

    }

}

1 2 3 4 5 6 7

3