It　is　interesting　and　challenging　to　study　double-ended　queues　with　First-Come-First-Match　discipline　under　customers＇　impatient　behavior　and　non-Poisson　inputs.　The　system　stability　can　be　guaranteed　by　the　customers＇　impatient　behavior,　while　the　existence　of　impatient　customers　makes　analysis　of　such　double-ended　queues　more　difficult　or　even　impossible　to　find　an　explicitly　analytic　solution,　thus　it　becomes　more　and　more　important　to　develop　effective　numerical　methods　in　a　variety　of　practical　matching　problems.　This　paper　studies　a　block-structured　double-ended　queue,　whose　block　structure　comes　from　two　independent　Markovian　arrival　processes　(MAPs),　which　are　non-Poisson　inputs.　We　show　that　such　a　queue　can　be　expressed　as　a　new　bilateral　quasi　birth-and-death　(QBD)　process　which　has　its　own　interest.　Based　on　this,　we　provide　a　detailed　analysis　for　both　the　bilateral　QBD　process　and　the　double-ended　queue,　including　the　system　stability,　the　queue　size　distributions,　the　average　stationary　queue　lengths,　and　the　sojourn　time　of　any　arriving　customers.　Furthermore,　we　develop　three　effective　algorithms　for　computing　the　performance　measures　(i.e.,　the　probabilities　of　stationary　queue　lengths,　the　average　stationary　queue　lengths,　and　the　average　sojourn　times)　of　the　double-ended　queue　with　non-Poisson　inputs.　Finally,　we　use　some　numerical　examples　in　tabular　and　graphical　to　illustrate　how　the　performance　measures　are　influenced　by　some　key　system　parameters.　We　believe　that　the　methodology　and　results　described　in　this　paper　can　be　applicable　to　deal　with　more　general　double-ended　queues　in　practice,　and　develop　some　effective　algorithms　for　the　purpose　of　many　actual　uses.