This paper studies a block-structured double-ended queue, whose block structure comes from two independent Markovian arrival processes (MAPs), while its stability is guaranteed by customers’ impatient behavior. We show that such a queue can be expressed as a new bilateral quasi birth-and-death (QBD) process. For this purpose, we provide a detailed analysis for the bilateral QBD process, including the system stability, the stationary probability vector, the sojourn time, and so forth. Furthermor