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".
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<Integer> q = new LinkedList<Integer>();
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.
Create a Queue with the two methods
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 7 3 5 -1 6 -1 -1 -1
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.