Feb
8
2013
Interesting Programming Challenge–FIFO Queue
I recently came across an interesting programming challenge, which I can summarise here.
Develop a first-in/first-out (FIFO) queue in a programming language of your choice. The following constraints apply:
- You must use a linked-list, and can’t use arrays, hashes or other sophisticated enumerations;
- The queue must be able to accept and store arbitrary objects;
- If the queue is empty, popping should raise an exception
- Each method/function can only be one line long (and using multi-statement separators such as ‘;’ is cheating);
- Each line can be at most 80 characters long;
- You can’t use an external or additional libraries – core language features only.
The queue should implement the following public interface:
size()–> returns an integer representing the number of elements in the queuepush(object o)–> pushes an arbitrary objectoonto the end of the queuepop()–> returns the next object from the head of the queue; raises an exception if there are no objects on the queue
While implementing a FIFO queue as a linked list is a fairly typical first year CS undergraduate problem, the additional constraints, in particular #4, make it much more interesting.
I chose to implement the solution in Ruby. Here’s the test spec for the solution:
As an added challenge, although it’s almost dictated by the problem statement, I tried to minimise (or indeed, ideally, eliminate) the use of ‘if’ statements.
Check-out my solution by clicking through.