import java.util.Scanner;
public class LinkedQueue<T>
    implements Queue<T> {
    private Node<T> head ;
    private Node<T> tail ;
    private int  length;

    public LinkedQueue(){
        head = null;
        tail = null;
        length = 0;
    }

    public int size() {
        return length;
    }
    public boolean isEmpty() {
        return (length == 0);
    }

    public void enqueue (T data) {
        Node<T> newNode = new Node<T>(data);

        if (isEmpty())
            head = tail = newNode;
        else {
            tail.setNext(newNode);
            tail = newNode;
        }
        length++;
    }
    public T front()
        throws QueueEmptyException{
        if (isEmpty())
            throw new QueueEmptyException(
                  "FRONT from empty queue");
        return head.getData();
    }
    public T dequeue()
        throws QueueEmptyException {
        if (isEmpty())
            throw new QueueEmptyException(
                  "DEQUEUE from empty queue");
        T data = head.getData();
        head = head.getNext();
        length--;
        return data;
    }
    public void flush() {
        while (!isEmpty())
            dequeue();
    }

    public void print() {
        Node p = head;
        while (p!=null) {
            if (p !=head)
                System.out.print(", ");
            System.out.print(p.getData());
            p = p.getNext();
        }
        System.out.println();
    }

    public void concatenate(LinkedQueue<T> q) {
        if (isEmpty()) {
            head = q.head;
            tail = q.tail;
            length = q.length;
        }
        else if (!q.isEmpty()) {
            tail.setNext(q.head);
            tail = q.tail;
            length += q.length;
        }
    }
    public static void main(String[] args){
        String sentence = "Shooby doo wop she bop" ;
        Scanner words =new Scanner(sentence);
        LinkedStack<String> stack=
            new LinkedStack<String>();
        Queue<String> queue=
            new LinkedQueue<String>();
        while(words.hasNext()){
            String word=words.next();
            stack.push(word); queue.enqueue(word);
        }
        while (!stack.isEmpty()){
            System.out.println(stack.pop()+
                               " "+queue.dequeue());
        }
    }

}
//