Even just a higher constitution should help with your stamina. Playing a warrior, at the start of the game I fairly frequently ran out of stamina from either running or using the spin attack special move repeatedly, but once I got up a few levels and raised my constitution, stamina became much less of a problem (usually only if I had to run a long distance, which wasn't too often, between the teleporter stones and pads). I always hit 'R' to toggle on the 'always run' mode, rather than walk/run based on how far you clicked from your character.