There are many different implementations and variations but I find the following works like a charm:
You would have your StateManager class. This would control the overall FSM. Then you have a state interface. Each state would implement after this interface.
// The manager that controls the whole FSM.
// The interface class. Would provide mostly virtual methods for use in sub classes.
// Every state would extend the interface and
// inherit it's default members.
SomeState : public IState
You could have the following methods in each state to begin with:
Your Manager Class would have these methods to start:
Takes a state's instance and stores it into an array. Remember that this would not be the fsm stack, only the registration stack. It would map the class to a string that you could identity the state as.
Removes a state from the registration stack.
Takes a string (from the registration stack) and takes the stack from the registration array and pushes it to the top of the state stack.
Replaces the current level state in the stack with one from the registration stack.
Pops an item from the state stack.
Would enable the next state under the current one.
This would enable the previous state, and disable the current one.
This is the secret. You will want to store a queue for all the current operations. CreateOperation would add a new operation to the queue. Each operation would link to the appropriate method. (e.g Push operation would call the Push(); method)
You would call this after the update methods. Since you want to wait until the game has been updated before messing around with the states. This method would go through the queue starting with the first and handle the operation.
You could implement a delay event system. To where the handleOperation would wait so many seconds or start a custom timer of some sort. This could provide you with additional functionality and methods such as OnDelayStart, OnDelayFinish. Animations are a great result of this.
Every time you call the Push method (through an operation) the OnExit method for the currently active state would also be called just before the switch. The same would be true for Pop(), Next(), and Back(). OnEnter would be called right when you switch to that state.
You might want sub-states(states under the top-most state in the stack) to be able to draw but not update. But some states might restrict lower states in the stack to draw. You could implement an opacity meter. 1 = Drawable() and 0 = Can't Draw().
You can also extend this use methods such as OnPause(), and OnResume(). When sub-states are allowed to draw but cannot update; you would call the OnPause() right when that occurs. When they are allowed to update again you could call OnResume().
There are many different ways of achieving a good FSM but imo this has the greatest flexibility. You could even extend this even more to suite your needs.
Note: The states themselves handle the transition to the next states. Since the manager does not know when or how each state ends and then switches to the next state. Only the states themselves know when or how to move on.