import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class ReversingHalf {
    public static void main(String[] args){
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        q.add(8);
        q.add(7);
        q.add(2);
        q.add(9);
        q.add(18);
        q.add(12);
        q.add(0);
        reverseHalf(q);
        System.out.println(q);
    }

    public static void reverseHalf(Queue<Integer> q){
        Stack<Integer> storage = new Stack<>();
        int origSize = q.size();

        for (int i = 0; i < origSize; i++){
            if (i % 2 == 1){
                storage.push(q.remove());
            } else {
                q.add(q.remove());
            }
        }
        while (!storage.isEmpty()){
            q.add(q.remove());
            q.add(storage.pop());
        }
        if (origSize % 2 == 1){
            q.add(q.remove());
        }
    }
}