Challenge: Build the Train

Lab Java Beginner 10 points

Build a train as a linked list of coach numbers using your own Node class. Each command is front x (add coach x at the front) or back x (add at the back). Keep a tail reference so back is O(1). Print the train as a-b-c, or empty.

Input

Line 1: q. Then q commands.

Output

The coaches from front to back joined by -.

Example

Input

5
back 2
back 3
front 1
back 4
front 0

Output

0-1-2-3-4

Sample input available Sample output available

Editor

Java

Hints

Keep both head and tail. The very first coach is both.

front: new node points to head. back: tail.next = new node, then tail moves.

Solution explanation

With a tail reference, adding at either end is O(1). Without it, back would walk the whole train every time: O(n).

Show solution

import java.util.Scanner;

class Node {
    int value;
    Node next;
    Node(int value) { this.value = value; }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();
        Node head = null, tail = null;
        for (int i = 0; i < q; i++) {
            String cmd = sc.next();
            Node n = new Node(sc.nextInt());
            if (head == null) {
                head = tail = n;
            } else if (cmd.equals("front")) {
                n.next = head;
                head = n;
            } else {
                tail.next = n;
                tail = n;
            }
        }
        if (head == null) {
            System.out.println("empty");
            return;
        }
        StringBuilder sb = new StringBuilder();
        for (Node c = head; c != null; c = c.next) {
            if (c != head) sb.append('-');
            sb.append(c.value);
        }
        System.out.println(sb);
    }
}

Output

Answer