Implement a Queue using two Stacks

using System;
using System.Collections.Generic;

class QueueWithStacks<T>
{
    private Stack<T> enqueueStack;
    private Stack<T> dequeueStack;

    public QueueWithStacks()
    {
        enqueueStack = new Stack<T>();
        dequeueStack = new Stack<T>();
    }

    public int Count => enqueueStack.Count + dequeueStack.Count;

    public void Enqueue(T item)
    {
        enqueueStack.Push(item);
    }

    public T Dequeue()
    {
        if (Count == 0)
            throw new InvalidOperationException("The queue is empty.");

        if (dequeueStack.Count == 0)
            MoveItemsToDequeueStack();

        return dequeueStack.Pop();
    }

    public T Peek()
    {
        if (Count == 0)
            throw new InvalidOperationException("The queue is empty.");

        if (dequeueStack.Count == 0)
            MoveItemsToDequeueStack();

        return dequeueStack.Peek();
    }

    private void MoveItemsToDequeueStack()
    {
        while (enqueueStack.Count > 0)
        {
            dequeueStack.Push(enqueueStack.Pop());
        }
    }
}

In this implementation, the QueueWithStacks<T> class uses two stacks, enqueueStack and dequeueStack, to mimic the behavior of a queue. Here’s how it works:

  • The Enqueue method adds an item to the enqueueStack, representing the back of the queue.
  • The Dequeue method removes and returns the front item from the dequeueStack. If the dequeueStack is empty, it first moves the items from the enqueueStack to the dequeueStack by calling the MoveItemsToDequeueStack method.
  • The Peek method retrieves the front item from the dequeueStack without removing it. If the dequeueStack is empty, it also moves the items from the enqueueStack to the dequeueStack using the MoveItemsToDequeueStack method.
  • The MoveItemsToDequeueStack method transfers items from the enqueueStack to the dequeueStack, ensuring the correct order for dequeuing.

This implementation allows for efficient enqueue and dequeue operations with a time complexity of O(1) amortized. It provides the same functionality as a standard queue using two stacks.

error: Content is protected !!