Queues

A Queue is a lot like the Stack data structure, but the order in which you pull elements out is different. In a Queue you enqueue to put something in the Queue and you dequeue to pull something out. The first thing in to the data structure is the first thing that will be dequeued. In other words, this is a first-in, first-out data structure, aka FIFO.

To recap:

• Stacks — The last element added to the list is the first to be removed with pop, so a stack if a LIFO data structure
• Queues - The first element added to the list is the first to be removed with dequeue, so a Queue is a FIFO data structure.

Why is this important?

Queues are the natural complement to Stacks. Some algorithms work with Queues or Stacks to help maintain state. The same algorithm using a Queue vs a Stack can produce wildly different results.

Release 1: Implement the Queue

Write and test a Queue class that conforms to the following interface:

Interface

• Queue#new(): Instantiate a new Queue
• Queue#enqueue(element): Add a new element to the queue
• Queue#dequeue: Remove and return the first element in the queue
• Queue#peel: Return (but do not remove) the first element in the queue
• Queue#empty?: Answer whether or not the queue is empty

Do not use any Ruby data structures in your implementation. Instead, pick one of your own to use in your implementation:

• FixedArray
• ArrayList
• LinkedList

Resources

• Wikipedia: Queue