Queue
"Queue" (/kjuː/) is an English word with multiple meanings, derived from the French queue ("tail"), ultimately from Latin cauda ("tail").[1][2] It most commonly refers to a line or sequence of people, vehicles, or items arranged in order, especially while waiting to be served or processed on a first-come, first-served basis (first-in, first-out). This usage is particularly prevalent in British English, where "to queue" means to join or stand in such a line, contrasting with "line" or "line up" in American English.[3][2] Historically, "queue" denoted a plait or braid of hair hanging from the back of the head, like a tail, a style associated with 18th- and 19th-century European fashion, particularly men's wigs.[1] In arts and culture, it appears in literature, media, and representations of social behavior, such as crowd management.[2] In mathematics and computing, a queue is an abstract data type modeling ordered collections following the FIFO principle, with applications in algorithms, operating systems, and queueing theory.[4] Specialized uses include railroad operations (e.g., shunting lines) and as a unit of measure in some contexts.[2]Etymology and Language
Word Origin and Evolution
The word "queue" originates from the Latin cauda, meaning "tail," which evolved through Vulgar Latin cōda into Old French cue or coë, also denoting a tail.[1][5] This French form entered English in the late 15th century, initially referring to a tail-like appendage; the sense of a plait of hair, such as a braid hanging from the back of the head, emerged in the 18th century.[1][6] By the 18th century, the term retained its association with hairstyles in English lexicography; for instance, Samuel Johnson's A Dictionary of the English Language (1755) defined it as a "plait of hair" or pigtail, reflecting its primary usage at the time for personal adornment rather than social organization.[1][6] The metaphorical extension to a line of people or objects resembling a tail emerged in the 19th century, with the first recorded use for a waiting line appearing in Thomas Carlyle's The French Revolution: A History (1837), describing crowds forming orderly tails during the upheavals.[3][6][7] The word's adoption in British English for denoting orderly waiting lines gained prominence during and after the Industrial Revolution, as urbanization and factory systems necessitated structured lines for services and goods, solidifying the term's practical connotation.[3][7] English borrowed the French word and adapted its pronunciation to /kjuː/ from the original French /kø/, reflecting the linguistic influence from Norman French on Middle English vocabulary.[3][1] In the 20th century, "queue" further evolved in service and administrative contexts, particularly in Britain, where it became synonymous with everyday waiting in shops, transport, and bureaucracy, often contrasted with the American preference for "line."[3][6] This shift highlighted the word's transition from a literal tail or braid to an abstract representation of sequential order.Linguistic Variations and Usage
In British English, the word "queue" is pronounced /kjuː/, while in American English, it is typically /kjuː/, though the term itself is far less commonly used for a waiting line, with "line" serving as the preferred equivalent.[2] The original French word "queue," meaning "tail," is pronounced [kø]. Spelling variations of the gerund include "queuing" and "queueing," both accepted in standard English, though "queueing" is the preferred form in British usage to maintain the word's etymological double vowels and avoid confusion with other terms.[8][9] Related phrases like "queue up" mean to form or join a line, a usage common in British English since the early 20th century. Regional differences in usage are pronounced: "queue" is the standard term in British and Commonwealth English for a line of people or vehicles waiting, as in "join the queue," reflecting a cultural emphasis on orderly waiting established by the 19th century.[10][11] In American English, "line" predominates for everyday waiting scenarios, such as "get in line," but "queue" persists in technical or formal contexts like computing and mathematics.[6] Idiomatic expressions highlight cultural nuances, such as "jump the queue," meaning to cut in line ahead of others, a phrase that gained prominence in the UK during post-World War II rationing when orderly queuing became a social norm amid shortages.[12][13] Another is "tail end of the queue," referring to the last position in a line, evoking the word's historical association with a tail. In modern global English, "queue" has adapted to digital contexts, particularly internet slang where a "Twitter queue" (now X) denotes a series of scheduled posts that publish automatically over time, a practice that emerged in the 2010s with the rise of social media management tools like Buffer.[14][15]Social and Everyday Contexts
Waiting Lines in Crowd Control
In crowd control, a queue refers to an ordered line of people or vehicles adhering to the first-in, first-out (FIFO) principle, where the first arrival is served first to ensure fairness and orderly progression.[16] This social application of FIFO minimizes conflicts by establishing a clear sequence, commonly seen in public spaces to manage access to limited resources or services.[17] The practice of queuing emerged in early 19th-century Britain amid urbanization and industrialization, particularly in banks and shops where growing customer volumes necessitated structured waiting to replace chaotic scrambles.[13] It became more formalized during World War II in the UK, as rationing of food and goods led to widespread long lines outside shops and public services, enforced by military oversight and civilian compliance to prevent disorder amid shortages.[18] Queues at this time symbolized national resilience, with women often waiting hours for essentials like butter or sugar.[19] Queues in crowd control vary by context, including single-file pedestrian lines for events or services, vehicle queues at toll booths or border crossings to regulate traffic flow, and virtual queues using mobile apps that allow users to join remotely without physical presence.[20] A prominent example of virtual queuing is Disneyland's FastPass system, launched in 1999, which issued timed tickets to bypass standby lines for attractions.[21] Management techniques emphasize prevention of chaos through physical barriers like stanchions and ropes to guide flow, clear signage directing patrons, and dedicated staff to monitor adherence and resolve issues.[22] Key metrics include queue length to assess congestion and average wait time to evaluate efficiency, often tracked via sensors or staff observations.[20] Psychological factors influence queue tolerance, with cultural variations evident in higher patience among Japanese crowds—rooted in values of harmony and respect—compared to more impatient responses in the US, where disruptions like line-cutting are more common.[23] Studies indicate that retail queues typically last 5-10 minutes on average, a duration that balances service without excessive frustration for most patrons.[24] Everyday examples include airport security lines, where passengers form extended pedestrian queues screened by barriers and staff, and supermarket checkouts, managed with multiple lanes to reduce wait times.[20] The COVID-19 pandemic from 2020 prompted spaced queuing protocols, with markings on floors and barriers enforcing 6-foot distances to curb virus transmission in high-traffic areas like stores and airports.[25] This adaptation reduced crowding but extended perceived wait times due to enforced gaps.[26]Social Behaviors and Queue Management
In individualistic cultures, such as those in Western societies, queuing operates under an implicit social norm of first-in, first-out (FIFO) ordering, which promotes equity by ensuring that arrival order determines service sequence. This norm fosters a collective agreement among participants to maintain order without formal oversight, relying instead on mutual respect for personal space and position. Enforcement typically occurs through subtle social pressures, including disapproving glares from those behind the violator or direct verbal corrections to reaffirm the rule, thereby preserving group harmony without escalating to conflict.[27][28] Queue-jumping, the act of bypassing others in line, disrupts this equilibrium and has been examined in sociological research. These studies highlighted how such behaviors provoke immediate backlash, underscoring the queue as a microcosm of social control. Cultural variations further shape responses; for instance, queue-jumping garners stronger disapproval in the UK, where rigid adherence to order is emphasized, compared to Italy, where more permissive social dynamics allow greater flexibility in line formation.[29][30] Prolonged waiting in queues often triggers psychological strain, manifesting as frustration that can escalate to "queue rage," a term describing intense anger or aggression toward the situation or others in line. Research indicates that this response stems from perceived unfairness and loss of control, with extended waits amplifying stress hormones and negative emotions like impatience. To mitigate these effects, service providers have introduced distractions such as queue-side televisions, a practice adopted in banks and similar venues since the 1980s to occupy waiters' attention and reduce perceived duration.[31][32] Effective queue management incorporates strategies like priority queuing, which allocates dedicated lanes or slots for vulnerable groups, such as the elderly and disabled, to enhance accessibility and fairness. In UK supermarkets, this includes reserved entry times or front-of-queue access for these individuals, a policy formalized to comply with equality laws and reduce physical strain. Technological innovations, such as the Qless virtual queuing app launched in 2008, further streamline processes by enabling mobile check-ins, allowing users to join lines remotely and receive wait-time notifications, thereby minimizing on-site congestion.[33][34] Economically, unmanaged queues lead to customer abandonment, with studies showing that 73% of customers abandon their purchases if wait times exceed five minutes, directly impacting revenue through lost sales. Businesses counter this by optimizing queue designs to retain customers, while historical events like the 1980s UK miners' strike illustrate queues' role in broader social disruptions, as striking communities formed long lines for food aid amid shortages, exacerbating tensions during labor protests.[35] Demographic factors influence queue experiences. Children, meanwhile, are introduced to queuing etiquette early in school systems, where structured line-forming activities teach discipline, patience, and respect for others, embedding these behaviors as foundational social skills.[36]Arts, Culture, and Media
Historical Hairstyle
The queue hairstyle, characterized by long hair gathered and tied into a braided ponytail at the nape of the neck, often powdered for a white appearance, emerged as a prominent men's fashion in 17th-century France under King Louis XIV. The Sun King, facing early hair loss around age 17, employed dozens of wigmakers to create elaborate perukes that covered his scalp, with the rear section styled as a queue to manage the length practically while maintaining courtly elegance.[37] This style symbolized aristocratic refinement and hygiene concerns of the era, as wigs allowed frequent cleaning without altering natural hair.[38] In China, the queue held profound cultural and political significance during the Qing Dynasty (1644–1912), where it was originally a traditional Manchu hairstyle adopted as a marker of ethnic identity. Following the Manchu conquest, the 1645 Tifayifu edict mandated its adoption by all male subjects, including Han Chinese, requiring the shaving of the forehead and temples while braiding the remaining back hair—a visible sign of submission to Manchu rule enforced through severe penalties for noncompliance. The style spread to 18th-century Europe via trade and cultural exchange, influencing military uniforms where soldiers tied their hair into queues for neatness during combat and drills, often as part of powdered wigs.[39][40][37] Queues were constructed from human hair or horsehair for durability and texture, frequently powdered with rice starch or flour to achieve the fashionable pale sheen and absorb oils. Common variations included the "club queue," a compact, shortened braid for everyday wear; the "ramillies," featuring front curls and a spiraled queue inspired by military practicality after the 1706 Battle of Ramillies; and the "bagwig," where the queue was enclosed in a black silk pouch to protect clothing from powder residue. These could extend up to two feet in length, though shorter versions predominated in professional settings.[38][41][42] The queue's popularity waned in Europe following the French Revolution of the 1790s, as revolutionaries rejected aristocratic symbols like powdered wigs in favor of cropped, natural haircuts symbolizing equality and simplicity—by 1800, short styles dominated civilian and military fashion. In China, the queue faced growing resistance as a emblem of foreign domination, culminating in mass cuttings during the 1911 Xinhai Revolution, which overthrew the Qing and ushered in republican modernization.[37][38][43] Prominent wearers included George Washington, who eschewed full wigs but powdered and queued his natural hair for formal portraits and military command, aligning with Continental Army standards. Napoleon Bonaparte sported a short queue in his early career portraits from the 1790s, reflecting revolutionary-era transitions before favoring the "Titus cut." Surviving 18th-century examples, such as horsehair wigs with attached queues and protective silk bags, are housed in institutions like London's Victoria & Albert Museum, offering insights into craftsmanship and social norms.[44][45][46] Today, the queue appears sporadically in historical reenactments of 18th-century European battles and Qing-era ceremonies, where participants replicate the style for authenticity using period-inspired materials.[37]Representations in Entertainment and Media
In film and television, the queue hairstyle has been depicted as a symbol of historical and cultural identity in period dramas set during China's Qing dynasty. Bernardo Bertolucci's The Last Emperor (1987) portrays the life of Puyi, the final emperor, including scenes of Manchu courtiers and officials wearing the distinctive queue, highlighting its role in imperial tradition and eventual obsolescence following the dynasty's fall.[47] The film uses these visual elements to underscore themes of modernization and loss, drawing on authentic Qing-era aesthetics for authenticity.[47] Literature has frequently employed the queue as a metaphor for social order, bureaucracy, and oppression. Charles Dickens' Oliver Twist (1838) illustrates the drudgery of Victorian poverty through scenes in the parish workhouse, where orphaned children line up in rigid queues for meager rations of gruel, emphasizing the dehumanizing effects of institutional waiting and class hierarchy.[48] This portrayal critiques the Poor Law system, using the queue to symbolize enforced submission and the erasure of individual agency among the destitute.[48] More contemporarily, Basma Abdel Aziz's The Queue (2013), a dystopian novel set in an unnamed authoritarian society, centers on an endless line of citizens waiting before a cryptic government gate for approvals and services, serving as an allegory for post-revolutionary bureaucracy and surveillance in Egypt.[49] The narrative explores how prolonged queuing erodes personal freedoms, blending Kafkaesque absurdity with real-world political critique.[50] In other media, the concept of queuing appears in interactive formats that simulate social dynamics. The board game Kolejka (English title: Queue, released in 2011 with international editions around 2014) recreates everyday life in late communist Poland, where players manage shopping lists and navigate event cards representing queue disruptions like "This isn't your place" or government interventions, teaching the frustrations of scarcity and informal networks.[51] Video games often incorporate queue mechanics for player matching; League of Legends, launched in 2009 by Riot Games, uses matchmaking queues to pair players of similar skill levels in ranked and normal modes, with typical wait times under 60 seconds to balance fairness and accessibility.[52][53] These systems prioritize team composition and position preferences, reflecting broader computational principles of orderly resource allocation.[53] Publications have also adopted "queue" in their titles to evoke themes of anticipation and technical depth. ACM Queue, a practitioner-focused magazine published by the Association for Computing Machinery since 2003, featured articles on software engineering, distributed systems, and emerging technologies, using the title to suggest a steady flow of innovative insights for developers.[54] Its bimonthly issues, including columns on real-world problem-solving, positioned it as a key resource for bridging theory and practice in computing.[54] The queue motif in media often carries cultural resonance, particularly in satirical contexts that exaggerate waiting as a national trait or societal ill. Abdel Aziz's novel, for instance, amplifies bureaucratic absurdity to comment on authoritarian control, influencing discussions on post-Arab Spring governance.[55]Mathematics and Computing
Abstract Data Type
In computer science, a queue is an abstract data type that represents an ordered collection of elements adhering to the first-in, first-out (FIFO) principle, where elements are inserted at the rear and removed from the front.[56] This structure ensures that the earliest added element is the first to be processed, mimicking real-world line formations.[57] The core operations of a queue include enqueue, which adds an element to the rear in constant time O(1) for efficient implementations; dequeue, which removes and returns the front element, also in O(1) time; peek, which inspects the front element without removal in O(1) time; and checks for emptiness or fullness, both achievable in O(1) time.[58] These operations maintain the integrity of the FIFO order while supporting basic state queries.[59] Queues can be implemented using arrays or linked lists. In an array-based implementation, a fixed-size array of capacity n uses front and rear pointers to track positions; to prevent space wastage from linear shifting, a circular queue wraps around the array ends, enabling amortized O(1) operations for enqueue and dequeue.[60] A linked list-based implementation employs nodes each containing data and a next pointer, allowing dynamic resizing without predefined capacity; enqueue appends to the tail, and dequeue removes from the head, both in O(1) time, with overall space complexity O(n) for n elements.[61] Both approaches achieve amortized O(1) time for standard operations and O(n) space usage.[58] Common variants extend the basic queue. A priority queue modifies the structure to remove elements based on priority rather than FIFO order, often implemented with heaps for O(log n) insertion and removal.[62] A double-ended queue (deque) permits insertions and deletions at both ends, supporting operations like push_front and pop_back in O(1) time via doubly linked lists or specialized arrays.[63] Queues find applications in task scheduling, such as managing print jobs where tasks are enqueued upon submission and dequeued for processing in arrival order.[64] They are also essential in graph algorithms like breadth-first search (BFS), which explores nodes level by level. The BFS pseudocode initializes an empty queue and enqueues the starting node; while the queue is not empty, it dequeues a node, processes it, and enqueues its unvisited neighbors:This ensures all nodes at distance k are processed before those at k+1.[65] The queue concept emerged in the 1940s with early batch-processing computers, where job scheduling required ordered execution to manage limited resources efficiently.[66] It was formalized in Donald Knuth's seminal work The Art of Computer Programming, Volume 1: Fundamental Algorithms (1968), which provided rigorous analysis of queue operations and implementations.[67]initialize queue Q enqueue start node to Q mark start as visited while Q is not empty: dequeue u from Q for each neighbor v of u: if v not visited: enqueue v to Q mark v as visitedinitialize queue Q enqueue start node to Q mark start as visited while Q is not empty: dequeue u from Q for each neighbor v of u: if v not visited: enqueue v to Q mark v as visited