Queues

Queues are similar to stacks, but instead of returning items in Last-In-First-Out Order (LIFO) they return them in First-In-First-Out Order (FIFO).

These are the 2 methods a Queue supports:

• Add an item to the end of the Queue. (a.k.a "push" or "enqueue")
• Remove an item from the front of the Queue. (a.k.a. "pop", "dequeue" or "poll")

Note that a Queue supports the same 2 methods as a Stack, but the 'pop' or 'remove' method is defined differently. remove returns the items that were 'waiting' the longest in the queue, i.e. it takes items from the opposite side of where they get placed in. You can see a Queue in action below by adding numbers with "enqueue" and removing the first number with "dequeue".

Credit: Galles

Implementation

A queue needs to keep track of both its head and its tail (the end), since they can both change. Like a Stack, a Queue can be implemented with an Array or a LinkedList, but its simplest to use a LinkedList. Adding is the same as with a Stack, and removing just pops off the head instead of the tail.

Queue Classes

Java comes with the Queue interface, which is implemented by the LinkedList class. This means you can create a Queue for numbers with the following code:

Queue<Integer> q = new LinkedList<Integer>();

In Ruby and Javascript the standard Array class comes with push for adding items and shift for removing items in FIFO order like a Queue.

Uses of a Queue

Just like people wait in a queue in the physical world, programs often wait in queues in the digital world. Programs are placed in queue to use a limited resource, such as the CPU or printer. Queues are also used in other areas where FIFO order makes sense, such as Breadth-First-Search or other challenges.

Challenge

Create a Queue with the two methods add and remove. Use your LinkedList class to keep track of the elements internally.

The input will consist of the number t followed by t test cases. Each test case will consist of a number n, followed by n numbers of actual input.

For each number of actual input: If the number is -1, remove the first number in the queue and print it. Otherwise, push the number onto your queue.

In this challenge, there's one more detail: If you get a -1 and there's nothing left in the queue, print -1.

Sample Input

1
7
3 5 -1 6 -1 -1 -1

Sample Output

3 5 6 -1

The numbers come out in the order they went in, and the final -1 returns a -1 since the queue is empty.