Sachverhalt:
A.
A._ reiste am 27. März 2017 zusammen mit einer weiteren Person am Grenzübergang Ramsen in die Schweiz ein. Bei der Kontrolle seines Autos wurden unter anderem 200 g einer weissen Substanz und ca. 1'600 Pillen gefunden. A._ wurde festgenommen und am 30. März 2017 vom Zwangsmassnahmengericht Schaffhausen in Untersuchungshaft versetzt. Die Haft wurde in der Folge mehrmals verlängert.
Mit Urteil vom 1. Juni 2018 sprach das Kantonsgericht Schaffhausen A._ der einfachen und qualifizierten Widerhandlung gegen das Betäubungsmittelgesetz, der Förderung der rechtswidrigen Einreise und des rechtswidrigen Aufenthalts sowie der mehrfachen Übertretung des Betäubungsmittelgesetzes schuldig. Es verurteilte ihn, als Zusatzstrafe zu einer mit Urteil des Tribunal de police de Lausanne vom 9. August 2017 verhängten Freiheitsstrafe von 6 Monaten, zu 26 Monaten Freiheitsstrafe und einer Busse von Fr. 300.--. Die Ersatzfreiheitsstrafe für die Busse setzte es auf 3 Tage fest. Zudem verwies es A._ für 5 Jahre des Landes.
A._ wurde am 17. September 2018 der vorzeitige Strafvollzug bewilligt. Am 9. April 2019 wies das Obergericht des Kantons Schaffhausen seine Berufung gegen das Urteil des Kantonsgerichts ab. Mit Eingabe vom 24. Juni 2019 erhob er gegen das Berufungsurteil Beschwerde an das Bundesgericht. Nachdem er in den vergangenen Monaten bereits mehrfach ein Entlassungsgesuch gestellt hatte, verlangte er mit Eingabe vom 3. Juli 2019 erneut, er sei aus dem vorzeitigen Strafvollzug zu entlassen. Mit Verfügung vom 12. Juli 2019 wies das Obergericht das Gesuch ab.
B.
Mit Beschwerde in Strafsachen an das Bundesgericht vom 16. Juli 2019 beantragt A._, die Verfügung des Obergerichts sei insoweit aufzuheben, als damit sein Gesuch abgewiesen worden sei, und er selbst aus dem vorzeitigen Strafvollzug zu entlassen. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
Das Obergericht beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Staatsanwaltschaft hat auf eine Vernehmlassung verzichtet.

Erwägungen:
1.
Gegen den angefochtenen Entscheid ist die Beschwerde in Strafsachen nach <ref-law> gegeben. Der Beschwerdeführer ist nach <ref-law> zur Beschwerde berechtigt. Auf sein Rechtsmittel ist einzutreten.
2.
2.1. Der Beschwerdeführer befindet sich im vorzeitigen Strafvollzug. Dies hindert ihn nicht daran, ein Gesuch um Haftentlassung zu stellen. Auf Gesuch um Entlassung aus dem vorzeitigen Strafvollzug hin ist zu prüfen, ob die Haftvoraussetzungen gegeben sind (<ref-ruling> E. 2.3 S. 163 f.; <ref-ruling> E. 4.1 f. S. 194; <ref-ruling> E. 1d S. 79 f.; je mit Hinweisen).
2.2. Nach <ref-law> sind Untersuchungs- und Sicherheitshaft unter anderem zulässig, wenn die beschuldigte Person eines Verbrechens oder Vergehens dringend verdächtig ist und ernsthaft zu befürchten ist, dass sie sich durch Flucht dem Strafverfahren oder der zu erwartenden Sanktion entzieht (Abs. 1 lit. a). An ihrer Stelle sind Ersatzmassnahmen anzuordnen, wenn sie den gleichen Zweck wie die Haft erfüllen (Art. 212 Abs. 2 lit. c und Art. 237 ff. StPO).
2.3. Der Beschwerdeführer bestreitet das Vorliegen eines dringenden Tatverdachts nicht. Er macht jedoch geltend, die Fluchtgefahr sei zu verneinen (E. 3 hiernach) und es liege Überhaft vor (E. 4 hiernach).
3.
3.1. Zur Fluchtgefahr bringt der Beschwerdeführer vor, er habe mittlerweile 27,5 Monate Haft erstanden. Er verfüge über eine Arbeitsplatzofferte und könnte nach der Haftentlassung bei seiner Mutter oder Freundin wohnen. Dass die Beziehung zu seiner Mutter vor der Verhaftung schwierig gewesen sei, spiele keine Rolle. Massgeblich sei vielmehr, dass diese mittlerweile sehr gut sei. Aufgrund schwerwiegender Vorfälle habe er zudem seine Beziehungen zu Serbien abgebrochen. Das Obergericht habe aus diesen Gründen die Fluchtgefahr zu Unrecht bejaht. Zudem habe es seinen Anspruch auf rechtliches Gehör (<ref-law>) verletzt, indem es sich mit der Arbeitsplatzofferte und mit möglichen Ersatzmassnahmen nicht auseinandergesetzt habe.
3.2. Das Obergericht hat sich mit den Vorbringen des Beschwerdeführers, die er in seiner Beschwerde vom 3. Juli 2019 in äusserst knapper, teils gar nur stichwortartiger Weise formulierte, hinreichend auseinandergesetzt. Es legte die hauptsächlichen Gründe dar, aus denen es die Fluchtgefahr bejahte, und verwies im Übrigen auf frühere Haftentscheide. Daraus geht hervor, dass im vorliegenden Fall weder die Arbeitsplatzofferte noch mögliche Ersatzmassnahmen die Verweigerung der Entlassung aus dem vorzeitigen Strafvollzug in Frage stellen. Die Ausführungen im angefochtenen Entscheid genügen vor diesem Hintergrund der Begründungspflicht ohne Weiteres. Der Beschwerdeführer war denn auch problemlos in der Lage, den angefochtenen Entscheid sachgerecht anzufechten (vgl. <ref-ruling> E. 5.2 S. 70 f. mit Hinweisen).
3.3. Auch das Bundesgericht hat sich in einem früheren Urteil bereits mit der Frage der vom Beschwerdeführer ausgehenden Fluchtgefahr auseinandergesetzt (Urteil 1B_348/2018 vom 9. August 2018 E. 6). Auf diese Erwägungen kann grundsätzlich verwiesen werden. Was der Beschwerdeführer in seiner Beschwerde vorträgt, führt nicht zu einem anderen Ergebnis. Zwar nimmt die Fluchtgefahr im Allgemeinen zusammen mit der voraussichtlich noch zu verbüssenden Freiheitsstrafe ab, doch droht dem Beschwerdeführer neben einer Freiheitsstrafe eine Landesverweisung von 5 Jahren. Insgesamt ist deshalb nach wie vor ein erheblicher Fluchtanreiz gegeben. Zu Recht berücksichtigte das Obergericht weiter, dass der Beschwerdeführer die Beziehung zu seiner Mutter vor der Verhaftung als schwierig bezeichnet hatte, selbst wenn zutreffen mag, dass diese unter den mit der Haft einhergehenden speziellen Umständen besser funktioniert. Die Beziehung zu seiner gegenwärtigen Freundin begann der Beschwerdeführer gemäss dem angefochtenen Entscheid zudem erst nach dem Haftantritt. Sie musste sich somit bisher nicht unter normalen Umständen, d. h. ausserhalb des Haftregimes, bewähren. Vor diesem Hintergrund erscheint die vorinstanzliche Feststellung, der Beschwerdeführer habe in der Schweiz keine gefestigten familiären und sozialen Beziehungen, nicht als willkürlich. Insgesamt durfte das Obergericht, ohne Bundesrecht zu verletzen, von einer weiterhin bestehenden Fluchtgefahr sowie davon ausgehen, dass diese mit Ersatzmassnahmen nicht hinreichend gebannt werden kann.
4.
4.1. Gemäss <ref-law> und Art. 5 Ziff. 3 EMRK hat eine in strafprozessualer Haft gehaltene Person Anspruch darauf, innerhalb einer angemessenen Frist richterlich abgeurteilt oder während des Strafverfahrens aus der Haft entlassen zu werden. Eine übermässige Haftdauer stellt eine unverhältnismässige Beschränkung dieses Grundrechts dar. Nach <ref-law> dürfen deshalb Untersuchungs- und Sicherheitshaft nicht länger dauern als die zu erwartende Freiheitsstrafe, wobei nach ständiger Praxis bereits zu vermeiden ist, dass die Haftdauer in grosse Nähe zur zu erwartenden Freiheitsstrafe rückt. Diese Grenze ist insbesondere deshalb bedeutsam, weil das erkennende Gericht dazu neigen könnte, die Dauer der erstandenen Haft bei der Strafzumessung mitzuberücksichtigen (zum Ganzen: <ref-ruling> E. 3.1 S. 180 f. mit Hinweisen).
4.2. Ausschlaggebend für die Beurteilung der Verhältnismässigkeit der Haftdauer sind die konkreten Umstände des Falls (<ref-ruling> E. 3.5 S. 183). Liegt bereits ein richterlicher Entscheid über das Strafmass vor, stellt dieser ein wichtiges Indiz für die mutmassliche Dauer der tatsächlich zu verbüssenden Strafe dar. Nach der Rechtsprechung ist zudem bei der Prüfung der zulässigen Haftdauer der Umstand, dass die in Aussicht stehende Freiheitsstrafe bedingt oder teilbedingt ausgesprochen werden kann, wie auch die Möglichkeit einer bedingten Entlassung aus dem Strafvollzug im Grundsatz nicht zu berücksichtigen. Dass im vorliegenden Fall gestützt auf die Akten kein Anlass besteht, von diesem Grundsatz ausnahmsweise abzuweichen, hat das Bundesgericht bereits in einem früheren, den Beschwerdeführer betreffenden Urteil festgestellt (zum Ganzen: <ref-ruling> E. 3.4 S. 182 mit Hinweisen). Droht wie hier neben einer freiheitsentziehenden Sanktion zusätzlich eine Landesverweisung, darf zudem auch noch ein angemessener behördlicher Zeitbedarf für die Vorbereitung des Vollzugs der Landesverweisung (Art. 66c-d StGB) bei der Prüfung der Verhältnismässigkeit der Haftdauer mitberücksichtigt werden (Urteil 1B_262/2018 vom 20. Juni 2018 E. 3.2 mit Hinweis). Ob angesichts der Mittellosigkeit des Beschwerdeführers konkrete Anhaltspunkte für eine drohende Umwandlung der Busse in eine Ersatzfreiheitsstrafe bestehen, kann dagegen offenbleiben (vgl. Urteil 1B_262/ 2018 vom 20. Juni 2018 E. 3.2 und <ref-law>). Die dem Beschwerdeführer in erster und zweiter Instanz auferlegte Busse beträgt lediglich Fr. 300.-- und die dafür festgesetzte Freiheitsstrafe drei Tage, weshalb sie für die Beurteilung der Verhältnismässigkeit der Haftdauer unter den gegebenen Umständen ohnehin nicht ins Gewicht fallen würde.
4.3. Der Beschwerdeführer wurde durch das Kantons- und das Obergericht zu einer Freiheitsstrafe von 26 Monaten als Zusatzstrafe zu einer noch nicht verbüssten Freiheitsstrafe von 6 Monaten verurteilt. Insgesamt drohen ihm deshalb 32 Monate Freiheitsentzug. Da die Staatsanwaltschaft keine Berufung erhoben hat, kann die Strafe im Rechtsmittelverfahren nicht erhöht werden. Zum Zeitpunkt der Beurteilung durch das Obergericht am 12. Juli 2019 hatte sich der am 27. März 2019 verhaftete Beschwerdeführer 27,5 Monate in Haft befunden und es verblieb damit bei einer zu erwartenden Freiheitsstrafe von 32 Monaten ein Rest von 4,5 Monaten. Im jetzigen Zeitpunkt beträgt die erstandene Haftdauer 28 Monate.
4.4. Im Urteil 1B_238/2012 vom 16. Mai 2012 verneinte das Bundesgericht die Überhaft in einem Fall, in dem 17-18 Monate Freiheitsstrafe zu erwarten waren und die erstandene Haftdauer 9 Monate (im Zeitpunkt des angefochtenen Entscheids) bzw. 10 Monate (im Zeitpunkt der bundesgerichtlichen Beurteilung) betrug. Es betonte jedoch, dass es sich um einen Grenzfall handle (a.a.O., E. 2.5.2 f.). Im Urteil 1B_234/2008 vom 8. September 2008 bejahte es die Überhaft bei einer erstandenen Haftdauer von ca. 14 Monaten und einer zu erwartenden Freiheitsstrafe von 18 Monaten (a.a.O., E. 4). Auch im Urteil 1B_280/2008 vom 6. November 2008 erwies sich die erstandene Haftdauer von knapp fünf Monaten im Zeitpunkt der bundesgerichtlichen Beurteilung bei einer zu erwartenden Freiheitsstrafe von 6 Monaten nicht mehr als verhältnismässig (a.a.O., E. 2.6). Eine Landesverweisung stand in diesen Fällen nicht zur Diskussion.
4.5. Im vorliegenden Strafverfahren hat das Bundesgericht bereits in seinem Urteil vom 11. April 2019 (<ref-ruling> E. 3.7 S. 183) darauf hingewiesen, dass der Verhältnismässigkeit der Haft besonderes Augenmerk zu schenken sein werde. Mittlerweile sind mehr als drei weitere Monate vergangen. Selbst unter Berücksichtigung eines angemessenen behördlichen Zeitbedarfs für die Vorbereitung des Vollzugs der Landesverweisung rückt die bisherige Haftdauer vor dem Hintergrund der erwähnten Rechtsprechung damit in grosse Nähe zu der zu erwartenden Freiheitsstrafe. Die Rüge der Überhaft erweist sich damit als begründet und es ist die unverzügliche Entlassung anzuordnen. Dass Fluchtgefahr besteht, ändert daran nichts (<ref-ruling> E. 2a S. 258 und E. 3b S. 260).
5.
Die Beschwerde ist aus diesen Gründen gutzuheissen, der angefochtene Entscheid aufzuheben und der Beschwerdeführer umgehend aus dem vorzeitigen Strafvollzug zu entlassen.
Bei diesem Ausgang des Verfahrens sind keine Gerichtskosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Der Kanton Schaffhausen ist zu verpflichten, dem Vertreter des Beschwerdeführers eine angemessene Parteientschädigung auszurichten (Art. 68 Abs. 1 und 2 BGG). Damit erweist sich dessen Gesuch um unentgeltliche Rechtspflege als gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen und der angefochtene Entscheid des Obergerichts des Kantons Schaffhausen vom 12. Juli 2019 aufgehoben. Der Beschwerdeführer ist umgehend aus dem vorzeitigen Strafvollzug zu entlassen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Schaffhausen hat dem Vertreter des Beschwerdeführers, Rechtsanwalt Eric Stern, für das Verfahren vor Bundesgericht eine Entschädigung von Fr. 1'000.-- zu bezahlen.
4.
Dieses Urteil wird dem Beschwerdeführer, der Staatsanwaltschaft und dem Obergericht des Kantons Schaffhausen schriftlich mitgeteilt.
Lausanne, 26. Juli 2019
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Chaix
Der Gerichtsschreiber: Dold