Sunday, January 17, 2010

Queue based on a single stack

Looking at things from different perspectives allows to understand them better. On the other hand mind bending practice improves your ability to find solutions.

Previously we were Disposing sequence of resources with Reactive Extensions. This time we will build FIFO (first in, first out) collection based on single LIFO (last in, first out) collection with no additional explicit storage.

It is not that insane as it looks. Assume that items come out of stack in the order they must appear in the queue (FIFO). Choosing the opposite order is also possible however is not practical (see below). To make it happen we simply need to make sure that items in the stack (LIFO) are placed in the opposite order. Items queued first must appear at the top of the stack. This basically means that in order to queue item all items must be popped, the item  pushed and then existent items pushed inversely to pop order. But we have no additional explicit storage requirement. Then store items implicitly through recursion.

public class StackBasedQueue<T> : IEnumerable<T>
{
  private readonly Stack<T> m_items;

  public StackBasedQueue()
    : this(Enumerable.Empty<T>())
  {
  }

  public StackBasedQueue(IEnumerable<T> items)
  {
    // Items must be reversed as we want first 
    // item to appear on top of stack
    m_items = new Stack<T>(items.Reverse());
  }

  public int Count
  {
    get { return m_items.Count; }
  }

  public void Enqueue(T item)
  {
    // If stack is empty then simply push item
    // as it will be the first and the last item 
    // in the queue
    if (m_items.Count == 0)
    {
      m_items.Push(item);
      return;
    }

    // The item must be placed at the bottom of the stack
    // To do this existent items must be popped, the item  
    // pushed and then existent items pushed inversely to 
    // pop order
    var tmp = m_items.Pop();
    Enqueue(item);
    m_items.Push(tmp);
  }

  public T Dequeue()
  {
    ThrowIfEmpy();
    // If stack is not empty item on top of it 
    // is next to be dequeued or peeked
    return m_items.Pop();
  }

  public T Peek()
  {
    ThrowIfEmpy();
    return m_items.Peek();
  }

  public IEnumerator<T> GetEnumerator()
  {
    // As items queued first must appear at the top of the
    // stack we can enumerate items directly
    return m_items.GetEnumerator();
  }

  IEnumerator IEnumerable.GetEnumerator()
  {
    return GetEnumerator();
  }

  private void ThrowIfEmpy()
  {
    if (Count == 0)
    {
      throw new InvalidOperationException("The queue is empty.");
    }
  }
}

Enqueue is a O(n) operation (where n is the number items in the stack). Dequeue and Peek is a O(1) operation. Enumerating through all items is a O(n) operation. Choosing the opposite order will make enumerating through all items O(n^2) operation which is not practical.

It is just an exercise so it must not be used in real world scenarios (otherwise at some point queue size may become big enough so that next attempt to enqueue an item will result in StackOverflowException) but standard Queue<T> instead.