Como colocar sentenças no meio da pilha

Preciso separar essa sentença “aSb” numa pilha e depois substituir o ‘S’ por ab, nesse caso tem que fica assim no final:
Antes:
a
S
b
Depois:
a
a
b
b