We present an analytical and numerical study of the competition between double and super-exchange (SE) interactions with classical localized spins interacting with itinerant electrons in a one-dimensional (1D) model. A phase separation between ferromagnetic (F) and anti-ferromagnetic (AF) phases was found at low SE interaction energy. The F–AF phase separation consists of a large F polaron within an AF background. For large SE interaction energy, the conduction electrons are self-trapped within separate small magnetic polarons. These magnetic polarons contain a single electron inside two or three sites forming a Wigner crystal. A new phase separation is found between these small polarons and the AF phase.