First-in first-out (FIFO) queues are ubiquitous building blocks in modern system-on-chips. Big FIFOs are often realized as static random access memories (SRAMs), and in many cases account for a significant portion of the area and power consumption of integrated circuits (ICs). Gain-cell embedded DRAM (GC-eDRAM) technology is an embedded memory alternative to the pervasive SRAM technology in ICs. It consumes less silicon area and less power than SRAM, but has the drawback of access blockage caused by its periodic data refreshing. In this paper we leverage the unique access patterns implied by the FIFO scheme to design a FIFO realized with GC-eDRAM. We show that such a FIFO is functionally indistinguishable from a FIFO realized with SRAM. The proposed FIFO has no access blockage time due to refresh, and no data integrity issues, and so can be used as an out-of-the-box replacement for FIFOs in existing and future designs, while providing as much as a 2× reduction in both area and power as compared to SRAM.