Как реализовать постоянную очередь на Android

Моему приложению нужна структура данных, подобная очереди: помещать в нее данные, получать данные из нее, как в FIFO. Под данными я сейчас имею в виду простые строки, а позже, возможно, более сложные объекты. Дело в том, что очередь и ее содержимое должны быть постоянными, независимо от того, что делает Android. Если приложение закрывается и открывается повторно (или даже перезагружается Android), очередь должна иметь то же состояние и данные, что и до закрытия приложения.

Я думаю, что очередь должна использовать какое-то внутреннее хранилище, предпочтительно внутреннее хранилище устройства. Может быть, вы могли бы провести мозговой штурм, как это реализовать. Очередь не обязательно должна запускаться в моем приложении, это также может быть какая-то плохо связанная фоновая служба, если это возможно в Android (но только для моего приложения).