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.

5 comments:

Andrew Kazyrevich said...

Stack[T].Pop doesn't return all items - it just returns the topmost.

So not sure how "var tmp = m_items.Pop();" would work out.


..Unless I'm missing something! :)



Regards,
Andrew

Dzmitry Huba said...

Enqueue pops topmost item from stack and then makes recursive call. Once base case is reached (stack is empty) it pushes item and returns. Upon return from recursive call it pushes previously popped item. Thus item appears at the bottom of the stack.

Andy said...

Why do you use special function for ThrowIfEmpy()?
This function does not know type of exception that should be thrown. It knows only caller.

Dzmitry Huba said...

Hi Andy.

Peeking or dequeuing from an empty queue must result in InvalidOperationException as there is nothing to return. In both cases the reason and description for the exception is the same so reusing exceptional case condition checking and exception raising code is reasonable.

Ross said...

The system stack (which enables recursive calling) is also a stack. So you have two stacks involved.