State Pattern C# with previous states

Use internal stack to maintain the previous states:

public class MyClass
{
  private Stack<State> _states;

  private State _currentState;

  public void GoToNextState()
  {
    // If Not last state then
    _states.Push(_currentState);
    _currentState = new NextState();
  }

  public void GoToPrevState()
  {
    // if not the first state
    _currentState = _states.Pop();
   }
}

if you want to maintain forward and backward states then create additional stack:

public class MyClass
{
    private readonly Stack<State> _nextStates = new Stack<State>();
    private readonly Stack<State> _prevStates = new Stack<State>();

    private State _currentState = new SampleState1();

    public State CurrentState { get { return _currentState; } }

    public void GoToNextState()
    {
        if (_currentState.NextState == null)
            return;

        _prevStates.Push(_currentState);

        _currentState = _nextStates.Count > 0 ? _nextStates.Pop() : _currentState.NextState;
    }

    public void GoToPrevState()
    {
        // if not the first state

        _nextStates.Push(_currentState);
        _currentState = _prevStates.Pop();
    }
}

Strictly speaking, if you're implementing the classic GoF State pattern then the State subclasses themselves are responsible for knowing about and performing the State transitions. The holder of the State isn't responsible for managing the transitions and a large part of the intent of the pattern is to encapsulate the state transition behaviour in the State objects and thus for the client to delegate to them. I've introduced a Factory that ensures that there is only ever a single instance of each State subclass to ensure that the same instance is reused when moving back and forth through the states.

public abstract class State
{
   protected StateFactory _factory;
   protected IStateUser _context;

   public State(StateFactory factory, IStateUser context)
   {
      _factory = factory;
      _context = context;
   }

   protected void TransitionTo<T>(Func<T> creator) where T : State
   {
       State state = _factory.GetOrCreate<T>(creator);
       _context.CurrentState = state;
   }

   public abstract void MoveNext();
   public abstract void MovePrevious();
}

public class State1 : State
{
   public State1(StateFactory factory, IStateUser context)
            : base(factory, context)
   {
   }

   public override void MoveNext()
   {
      TransitionTo<State2>(() => new State2(_factory, _context));
   }

   public override void MovePrevious()
   {
      throw new InvalidOperationException();
   }
}

public class State2 : State
{
   public State2(StateFactory factory, IStateUser context)
            : base(factory, context)
   {
   }

   public override void MoveNext()
   {
      TransitionTo<State3>(() => new State3(_factory, _context)); //State 3 is omitted for brevity
   }

   public override void MovePrevious()
   {
      TransitionTo<State1>(() => new State1(_factory, _context));
   }
}

public interface IStateUser
{
   State CurrentState { get; set; }
}

public class Client : IStateUser
{

   public Client()
   {
      var factory = new StateFactory();
      var first = new State1(factory, this);
      CurrentState = factory.GetOrCreate<State1>(() => first);
   }

   public void MethodThatCausesTransitionToNextState()
   {
      CurrentState.MoveNext();
   }

   public void MethodThatCausesTransitionToPreviousState()
   {
      CurrentState.MovePrevious();
   }

   public State CurrentState
   {
      get;
      set;
   }
}

public class StateFactory
{
    private Dictionary<string, State> _states = new Dictionary<string, State>();

    public State GetOrCreate<T>(Func<T> creator) where T : State
    {
        string typeName = typeof(T).FullName;

        if (_states.ContainsKey(typeName))
            return _states[typeName];

        T state = creator();
        _states.Add(typeName, state);

        return state;
    }
}