Get in line
Ruby
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
Gemfile
README.md
queue.rb
queue_spec.rb

README.md

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 into the Queue and you dequeue to pull something out. In other words, this is a first-in, first-out data structure, aka FIFO.

To recap:

  • Stacks are LIFO. The last item added to the list is the first to be pulled out, so a stack if a LIFO data structure.
  • Queues are FIFO. The first item added to the list is the first to be pulled out, so a Queue is a FIFO data structure.

Why is this important?

Queues are the natural complement to Stacks. Some algorithms work with Queues, others work with Stacks. For example, the difference between a depth-first-search and a breadth-first-search is whether they use a stack or a queue.

Release 1: Implement the Queue

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

Interface

  • MyQueue#new(): Instantiate a new MyQueue
  • MyQueue#enqueue(element): Add a new element to the queue
  • MyQueue#dequeue: Remove and return the first element in the queue
  • MyQueue#peel: Return (but do not remove) the first element in the queue
  • MyQueue#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