late 15c., "band attached to a letter with seals dangling on the free end," from French queue "a tail," from Old French cue, coe, queue, "tail" (12c., also "penis"), from Latin coda (dialectal variant or alternative form of cauda) "tail" (see coda, and compare cue (n.2)).
Also in literal use in 16c. English, "tail of a beast," especially in heraldry. A metaphoric extension to "line of dancers" (c. 1500) perhaps led to the extended sense of "line of people, etc." (1837), but this use in English is perhaps directly from French (queue à queue, "one after another" appears in early 19c. English and American military dictionaries).
If we look now at Paris one thing is too evident: that the Baker's shops have got their Queues, or Tails ; their long strings of purchasers arranged in tail, so that the first come be the first served,—were the shop once open! This waiting in tail, not seen since the early days of July, again makes its appearance in August. In time, we shall see it perfected, by practice to the rank almost of an art ; and the art, or quasi-art, of standing in tail become one of the characteristics of the Parisian People, distinguishing them from all other Peoples whatsoever. [Carlyle, "The French Revolution," 1837]
Also used 18c. in sense of "braid of hair hanging down behind" (attested by 1748), originally part of the wig, in later 18c. of the hair of the head.
QUEUE. From the French, which signifies tail; an appendage that every British soldier is directed to wear in lieu of a club. Regimental tails were ordered be nine inches long. [William Duane, "A Military Dictionary," Philadelphia, 1810]
"to stand in or join a line" (intransitive), by 1924, from queue (n.). Transitive sense of "arrange in or cause to form a line" is by 1928. Earlier "tie or fasten the hair in a braided pigtail" (1777). Related: Queued; queueing. Churchill is said to have coined Queuetopia (1950), to describe Britain under Labour or Socialist rule.