343:, but it does admittedly slow things down a little, because the array indices must be compared to zero and the array size, which is comparable to the time taken to check whether an array index is out of bounds, which some languages do, but this will certainly be the method of choice for a quick and dirty implementation, or for any high-level language that does not have pointer syntax. The array size must be declared ahead of time, but some implementations simply double the declared array size when overflow occurs. Most modern languages with objects or
36:
485:
2783:
102:
2940:
2563:
334:
Fixed-length arrays are limited in capacity, but it is not true that items need to be copied towards the head of the queue. The simple trick of turning the array into a closed circle and letting the head and tail drift around endlessly in that circle makes it unnecessary to ever move items stored in
246:
of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence. By convention, the end of the sequence at which elements are added is called the back, tail, or rear of the queue,
330:
Theoretically, one characteristic of a queue is that it does not have a specific capacity. Regardless of how many elements are already contained, a new element can always be added. It can also be empty, at which point removing an element will be impossible until a new element has been added again.
275:. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed. A queue is an example of a
2417:
2422:
2327:
2015:
2944:
1933:
286:
A queue has two ends, the top, which is the only position at which the push operation may occur, and the bottom, which is the only position at which the pop operation may occur. A queue may be implemented as
1681:
1545:
2332:
2193:
2089:
2881:
1329:
2558:{\displaystyle \operatorname {rotate} (\operatorname {CONS} (x,f),\operatorname {CONS} (y,r),a)=\operatorname {Cons} (x,\operatorname {rotate} (f,r,\operatorname {CONS} (y,a)))}
1749:
1489:
2245:
2149:
1847:
279:, or more abstractly a sequential collection. Queues are common in computer programs, where they are implemented as data structures coupled with access routines, as an
2761:
2691:
2645:
2040:
1625:
1583:
1381:
247:
and the end at which elements are removed is called the head or front of the queue, analogously to the words used when people line up to wait for goods or services.
314:
where various entities such as data, objects, persons, or events are stored and held to be processed later. In these contexts, the queue performs the function of a
2592:
1237:
1177:
1108:
1039:
1010:
722:
693:
656:
1775:
1427:
1287:
1795:
1257:
1200:
1148:
1128:
1079:
1059:
978:
958:
938:
918:
898:
878:
858:
834:
814:
794:
774:
3430:
2955:
2262:
369:
There are several efficient implementations of FIFO queues. An efficient implementation is one that can perform the operations—en-queuing and de-queuing—in
3106:
1852:
1938:
3400:
389:
A regular singly linked list only has efficient insertion and deletion at one end. However, a small modification—keeping a pointer to the
57:
3339:
3061:
3043:
3024:
2992:
79:
626:
272:
107:
3129:
2979:
340:
243:
3134:
344:
3099:
2697:
is the empty list. This counter allows us to ensure that the rear is never longer than the front list. Furthermore, using
3079:
464:
458:
3464:
2412:{\displaystyle \operatorname {rotate} ({\text{NIL}},\operatorname {Cons} (y,{\text{NIL}}),a)=\operatorname {Cons} (y,a)}
3213:
3196:
2859:
2788:
1630:
1494:
420:
50:
44:
2154:
452:
3412:
3174:
3015:
2817:
2056:
260:
2594:, but, since lazy evaluation is used, the computation is delayed until the results are forced by the computation.
3169:
733:
443:
315:
3074:
1296:
1202:
had to be inserted and we can assign a constant cost for each element in the reverse to when it was inserted.
61:
3208:
3203:
3162:
3092:
3443:
3420:
2771:
could be some append of append of... of append, and forcing would not be a constant time operation anymore.
450:" templated class which is restricted to only push/pop operations. Since J2SE5.0, Java's library contains a
280:
3425:
3225:
1777:
must then be called for the invariant to be satisfied. Two cases must be considered, depending on whether
484:
3351:
3306:
3268:
276:
1239:
time for all operations, without amortization. This discussion will be technical, so recall that, for
3291:
3002:
473:
319:
1686:
311:
3334:
3049:
3031:
3319:
3184:
3144:
1432:
1179:
880:
is not empty, it is easy to remove from the end of the queue by removing the node at the head of
663:
412:
399:
383:
2838:
2198:
2151:, since it is the case when this function is called. More precisely, we define a lazy function
2102:
1800:
3253:
3152:
3057:
3039:
3020:
2988:
2720:
2650:
2604:
1592:
1550:
1348:
3276:
3006:
2998:
2915:
2907:
303:
235:
199:
2898:
Hood, Robert; Melville, Robert (November 1981). "Real-time queue operations in pure Lisp".
411:
Queues may be implemented as a separate data type, or maybe considered a special case of a
3296:
3238:
2812:
2568:
1213:
1153:
1084:
1015:
986:
737:
736:
with operations in O(1) worst-case time. It is a more complex implementation and requires
698:
669:
632:
288:
268:
operation that returns the value of the next element to be dequeued without dequeuing it.
120:
1754:
1402:
1262:
2020:
335:
the array. If n is the size of the array, then computing indices modulo n will turn the
3388:
3366:
3191:
3115:
3010:
2807:
2322:{\displaystyle \operatorname {reverse} (f,r)=\operatorname {rotate} (f,r,{\text{NIL}})}
1780:
1242:
1185:
1133:
1113:
1064:
1044:
963:
943:
923:
903:
883:
863:
843:
819:
799:
779:
759:
370:
348:
124:
2950:
17:
3458:
3361:
3258:
3243:
2911:
2802:
339:
into a circle. This is still the conceptually simplest way to construct a queue in a
296:
840:. It is easy to insert into the front of the queue by adding a node at the head of
2974:
386:
has O(1) insertion and deletion at both ends, so it is a natural choice for queues.
1391:
is the rear of the queue in reverse order. The invariant of the structure is that
469:
393:
node in addition to the first one—will enable it to implement an efficient queue.
3356:
3281:
2782:
1343:
753:
741:
377:
351:
may have not specified a fixed capacity limit besides memory constraints. Queue
292:
728:
is the number of elements in the queue. The second implementation is called a
3344:
3248:
2796:
2778:
496:
1928:{\displaystyle \operatorname {aux} (f,r,\operatorname {Cons} (\_,s))=(f,r,s)}
3286:
3233:
307:
2010:{\displaystyle \operatorname {aux} (f,r,{\text{NIL}})=(f',{\text{NIL}},f')}
3383:
2767:
is totally forced. If it was not the case, the internal representation of
2601:
in the data structure has two purposes. This list serves as a counter for
3329:
3157:
456:
interface that specifies queue operations; implementing classes include
250:
The operation of adding an element to the rear of the queue is known as
3378:
3324:
477:
101:
254:, and the operation of removing an element from the front is known as
3373:
3314:
2920:
431:
functions to enqueue and dequeue a list (or, in reverse, one can use
3084:
3080:
VBScript implementation of stack, queue, deque, and Red-Black Tree
1342:
The data structure used to implement our queues consists of three
423:
allow pushing and popping an array from both ends, so one can use
355:
results from trying to add an element onto a full queue and queue
336:
3395:
2995:. Section 2.2.1: Stacks, Queues, and Dequeues, pp. 238–243.
2960:
416:
3088:
439:), although in some cases these operations are not efficient.
359:
happens when trying to remove an element from an empty queue.
29:
836:
holds the remaining elements (a.k.a., the rear of the queue)
629:. There are two implementations. The first one only achieves
347:
can implement or come with libraries for dynamic lists. Such
258:. Other operations may also be allowed, often including a
3046:. Chapter 8: Queues and Priority Queues, pp. 386–390.
1683:. It is said almost, because in both of those results,
2705:, forces the computation of a part of the (lazy) list
318:. Another usage of queues is in the implementation of
2820:– the "opposite" of a queue: LIFO (Last In First Out)
2723:
2653:
2607:
2571:
2425:
2335:
2265:
2201:
2157:
2105:
2059:
2023:
1941:
1855:
1803:
1783:
1757:
1689:
1633:
1595:
1553:
1497:
1435:
1405:
1351:
1299:
1265:
1245:
1216:
1188:
1156:
1136:
1116:
1087:
1067:
1047:
1018:
989:
966:
946:
926:
906:
886:
866:
846:
822:
802:
782:
762:
701:
672:
635:
415:(deque) and not implemented separately. For example,
3027:. Section 10.1: Stacks and queues, pp. 200–204.
3411:
3305:
3267:
3224:
3143:
3122:
3019:, Second Edition. MIT Press and McGraw-Hill, 2001.
205:
198:
183:
168:
145:
130:
119:
94:
3056:, Third Edition. Thomson Course Technology, 2005.
2755:
2685:
2639:
2586:
2557:
2411:
2321:
2239:
2187:
2143:
2083:
2034:
2009:
1927:
1841:
1789:
1769:
1743:
1675:
1619:
1577:
1539:
1483:
1421:
1375:
1323:
1281:
1251:
1231:
1194:
1171:
1142:
1122:
1102:
1073:
1053:
1033:
1004:
972:
952:
932:
912:
892:
872:
852:
828:
808:
788:
768:
716:
687:
650:
3064:. Chapter 4: Stacks and Queues, pp. 137–169.
1676:{\displaystyle (f,\operatorname {CONS} (x,r),s)}
1540:{\displaystyle (\operatorname {CONS} (x,f),r,s)}
366:is a queue limited to a fixed number of items.
2188:{\displaystyle \operatorname {rotate} (f,r,a)}
3100:
2084:{\displaystyle \operatorname {reverse} (f,r)}
816:holds the front part of the queue. The list
283:or in object-oriented languages as classes.
8:
2956:Dictionary of Algorithms and Data Structures
2195:which takes as input three lists such that
3107:
3093:
3085:
1324:{\displaystyle \operatorname {CONS} (h,t)}
402:implemented using a modified dynamic array
116:
100:
2919:
2748:
2740:
2732:
2724:
2722:
2678:
2670:
2662:
2654:
2652:
2632:
2624:
2616:
2608:
2606:
2570:
2424:
2368:
2345:
2334:
2311:
2264:
2226:
2218:
2210:
2202:
2200:
2156:
2130:
2122:
2114:
2106:
2104:
2099:reversed. Let us furthermore assume that
2058:
2022:
1988:
1963:
1940:
1854:
1828:
1820:
1812:
1804:
1802:
1782:
1756:
1730:
1722:
1714:
1706:
1698:
1690:
1688:
1632:
1594:
1552:
1496:
1476:
1468:
1460:
1452:
1444:
1436:
1434:
1414:
1406:
1404:
1350:
1298:
1274:
1266:
1264:
1244:
1215:
1187:
1155:
1135:
1115:
1086:
1066:
1046:
1017:
988:
965:
945:
925:
905:
885:
865:
845:
821:
801:
781:
761:
700:
671:
634:
80:Learn how and when to remove this message
2329:. The inductive definition of rotate is
273:first-in-first-out (FIFO) data structure
43:This article includes a list of general
3038:, Second Edition. Prentice Hall, 2002.
2987:, Third Edition. Addison-Wesley, 1997.
2830:
91:
3054:Data Structures and Algorithms in C++
1012:time. The removal ("dequeue") takes
695:, but individual operations can take
472:class and third party libraries like
7:
983:The insert ("enqueue") always takes
625:Queues can also be implemented as a
271:The operations of a queue make it a
2882:"Purely Functional Data Structures"
1849:, or not. The formal definition is
752:This queue's data is stored in two
2247:, and return the concatenation of
1886:
1331:represents the list whose head is
49:it lacks sufficient corresponding
25:
1797:is the empty list, in which case
3036:Data Structures with C++ and STL
2943: This article incorporates
2938:
2781:
627:purely functional data structure
621:Purely functional implementation
483:
407:Queues and programming languages
34:
2980:The Art of Computer Programming
1182:time, because every element in
2900:Information Processing Letters
2799:- events are stored in a queue
2749:
2741:
2733:
2725:
2679:
2671:
2663:
2655:
2633:
2625:
2617:
2609:
2581:
2575:
2552:
2549:
2546:
2534:
2513:
2498:
2486:
2477:
2465:
2453:
2441:
2432:
2406:
2394:
2382:
2373:
2359:
2342:
2316:
2296:
2284:
2272:
2227:
2219:
2211:
2203:
2182:
2164:
2131:
2123:
2115:
2107:
2078:
2066:
2004:
1974:
1968:
1948:
1922:
1904:
1898:
1895:
1883:
1862:
1829:
1821:
1813:
1805:
1731:
1723:
1715:
1707:
1699:
1691:
1670:
1661:
1649:
1634:
1614:
1596:
1572:
1554:
1534:
1519:
1507:
1498:
1477:
1469:
1461:
1453:
1445:
1437:
1415:
1407:
1387:is the front of the queue and
1370:
1352:
1318:
1306:
1275:
1267:
1226:
1220:
1166:
1160:
1097:
1091:
1028:
1022:
999:
993:
732:and it allows the queue to be
711:
705:
682:
676:
645:
639:
495:A simple queue implemented in
1:
2841:. Docs.oracle.com. 2014-03-26
1744:{\displaystyle |s|=|f|-|r|+1}
1293:represents an empty list and
1210:The real-time queue achieves
1130:is the number of elements in
2912:10.1016/0020-0190(81)90030-2
2839:"Queue (Java Platform SE 7)"
1081:is empty, the reverse takes
940:is reversed and assigned to
3431:Directed acyclic word graph
3197:Double-ended priority queue
2789:Computer programming portal
2717:operation. Therefore, when
2091:the function which returns
1484:{\displaystyle |s|=|f|-|r|}
302:Queues provide services in
110:(first in, first out) queue
3481:
3016:Introduction to Algorithms
2818:Stack (abstract data type)
3439:
2240:{\displaystyle |r|=|f|+1}
2144:{\displaystyle |r|=|f|+1}
1842:{\displaystyle |r|=|f|+1}
1585:and inserting an element
1289:denotes its length, that
1150:. But, we can say it is
444:Standard Template Library
115:
99:
3163:Retrieval Data Structure
1751:. An auxiliary function
1491:. The tail of the queue
1429:first elements, that is
501:
3444:List of data structures
3421:Binary decision diagram
2756:{\displaystyle |f|=|r|}
2686:{\displaystyle |f|=|r|}
2640:{\displaystyle |f|-|r|}
1620:{\displaystyle (f,r,s)}
1578:{\displaystyle (f,r,s)}
1376:{\displaystyle (f,r,s)}
295:, or by using both the
281:abstract data structure
64:more precise citations.
3426:Directed acyclic graph
2985:Fundamental Algorithms
2945:public domain material
2757:
2687:
2641:
2588:
2565:. Its running time is
2559:
2413:
2323:
2241:
2189:
2145:
2085:
2036:
2011:
1929:
1843:
1791:
1771:
1745:
1677:
1621:
1579:
1541:
1485:
1423:
1377:
1325:
1283:
1253:
1233:
1196:
1173:
1144:
1124:
1104:
1075:
1055:
1035:
1006:
974:
954:
934:
914:
894:
874:
854:
830:
810:
790:
770:
718:
689:
652:
299:and the base pointer.
18:Queue (data structure)
2758:
2701:, which is a tail of
2688:
2642:
2589:
2560:
2414:
2324:
2242:
2190:
2146:
2086:
2037:
2012:
1930:
1844:
1792:
1772:
1746:
1678:
1622:
1580:
1542:
1486:
1424:
1378:
1326:
1284:
1254:
1234:
1197:
1174:
1145:
1125:
1105:
1076:
1056:
1036:
1007:
975:
960:and then the head of
955:
935:
915:
895:
875:
855:
831:
811:
791:
771:
719:
690:
653:
462:and (since J2SE 1.6)
277:linear data structure
3292:Unrolled linked list
3003:Charles E. Leiserson
2721:
2651:
2605:
2587:{\displaystyle O(r)}
2569:
2423:
2333:
2263:
2199:
2155:
2103:
2057:
2021:
1939:
1853:
1801:
1781:
1755:
1687:
1631:
1593:
1551:
1495:
1433:
1403:
1349:
1297:
1263:
1243:
1232:{\displaystyle O(1)}
1214:
1186:
1172:{\displaystyle O(1)}
1154:
1134:
1114:
1103:{\displaystyle O(n)}
1085:
1065:
1061:is not empty. When
1045:
1034:{\displaystyle O(1)}
1016:
1005:{\displaystyle O(1)}
987:
964:
944:
924:
904:
884:
864:
844:
820:
800:
780:
760:
717:{\displaystyle O(n)}
699:
688:{\displaystyle O(1)}
670:
651:{\displaystyle O(1)}
633:
326:Queue implementation
320:breadth-first search
106:Representation of a
3465:Abstract data types
3340:Self-balancing tree
3075:STL Quick Reference
1770:{\displaystyle aux}
1422:{\displaystyle |r|}
1344:singly-linked lists
1282:{\displaystyle |l|}
920:is empty, the list
754:singly-linked lists
341:high-level language
312:operations research
3320:Binary search tree
3185:Double-ended queue
2933:General references
2860:"Array (Ruby 3.1)"
2753:
2683:
2637:
2584:
2555:
2409:
2319:
2237:
2185:
2141:
2081:
2035:{\displaystyle f'}
2032:
2007:
1925:
1839:
1787:
1767:
1741:
1673:
1617:
1575:
1537:
1481:
1419:
1373:
1335:and whose tail is
1321:
1279:
1249:
1229:
1192:
1169:
1140:
1120:
1100:
1071:
1051:
1031:
1002:
970:
950:
930:
910:
890:
870:
850:
826:
806:
786:
766:
714:
685:
648:
413:double-ended queue
384:doubly linked list
27:Abstract data type
3452:
3451:
3254:Hashed array tree
3153:Associative array
2371:
2348:
2314:
1991:
1966:
1790:{\displaystyle s}
1252:{\displaystyle l}
1195:{\displaystyle f}
1143:{\displaystyle f}
1123:{\displaystyle n}
1074:{\displaystyle r}
1054:{\displaystyle r}
973:{\displaystyle r}
953:{\displaystyle r}
933:{\displaystyle f}
913:{\displaystyle r}
893:{\displaystyle r}
873:{\displaystyle r}
853:{\displaystyle f}
829:{\displaystyle r}
809:{\displaystyle f}
789:{\displaystyle r}
769:{\displaystyle f}
232:
231:
228:
227:
90:
89:
82:
16:(Redirected from
3472:
3277:Association list
3109:
3102:
3095:
3086:
3007:Ronald L. Rivest
2999:Thomas H. Cormen
2964:
2942:
2941:
2926:
2925:
2923:
2895:
2889:
2888:
2886:
2880:Okasaki, Chris.
2877:
2871:
2870:
2868:
2867:
2856:
2850:
2849:
2847:
2846:
2835:
2791:
2786:
2785:
2762:
2760:
2759:
2754:
2752:
2744:
2736:
2728:
2692:
2690:
2689:
2684:
2682:
2674:
2666:
2658:
2646:
2644:
2643:
2638:
2636:
2628:
2620:
2612:
2593:
2591:
2590:
2585:
2564:
2562:
2561:
2556:
2418:
2416:
2415:
2410:
2372:
2369:
2349:
2346:
2328:
2326:
2325:
2320:
2315:
2312:
2255:reversed and of
2246:
2244:
2243:
2238:
2230:
2222:
2214:
2206:
2194:
2192:
2191:
2186:
2150:
2148:
2147:
2142:
2134:
2126:
2118:
2110:
2090:
2088:
2087:
2082:
2041:
2039:
2038:
2033:
2031:
2016:
2014:
2013:
2008:
2003:
1992:
1989:
1984:
1967:
1964:
1934:
1932:
1931:
1926:
1848:
1846:
1845:
1840:
1832:
1824:
1816:
1808:
1796:
1794:
1793:
1788:
1776:
1774:
1773:
1768:
1750:
1748:
1747:
1742:
1734:
1726:
1718:
1710:
1702:
1694:
1682:
1680:
1679:
1674:
1626:
1624:
1623:
1618:
1584:
1582:
1581:
1576:
1546:
1544:
1543:
1538:
1490:
1488:
1487:
1482:
1480:
1472:
1464:
1456:
1448:
1440:
1428:
1426:
1425:
1420:
1418:
1410:
1382:
1380:
1379:
1374:
1330:
1328:
1327:
1322:
1288:
1286:
1285:
1280:
1278:
1270:
1258:
1256:
1255:
1250:
1238:
1236:
1235:
1230:
1201:
1199:
1198:
1193:
1178:
1176:
1175:
1170:
1149:
1147:
1146:
1141:
1129:
1127:
1126:
1121:
1109:
1107:
1106:
1101:
1080:
1078:
1077:
1072:
1060:
1058:
1057:
1052:
1040:
1038:
1037:
1032:
1011:
1009:
1008:
1003:
979:
977:
976:
971:
959:
957:
956:
951:
939:
937:
936:
931:
919:
917:
916:
911:
899:
897:
896:
891:
879:
877:
876:
871:
859:
857:
856:
851:
838:in reverse order
835:
833:
832:
827:
815:
813:
812:
807:
795:
793:
792:
787:
775:
773:
772:
767:
723:
721:
720:
715:
694:
692:
691:
686:
662:. That is, the
657:
655:
654:
649:
616:
613:
610:
607:
604:
601:
598:
595:
592:
589:
586:
583:
580:
577:
574:
571:
568:
565:
562:
559:
556:
553:
550:
547:
544:
541:
538:
535:
532:
529:
526:
523:
520:
517:
514:
511:
508:
505:
487:
467:
461:
455:
449:
304:computer science
289:circular buffers
236:computer science
224:
215:
200:Space complexity
194:
189:
179:
174:
164:
155:
117:
104:
92:
85:
78:
74:
71:
65:
60:this article by
51:inline citations
38:
37:
30:
21:
3480:
3479:
3475:
3474:
3473:
3471:
3470:
3469:
3455:
3454:
3453:
3448:
3435:
3407:
3301:
3297:XOR linked list
3263:
3239:Circular buffer
3220:
3139:
3118:
3116:Data structures
3113:
3071:
2971:
2969:Further reading
2951:"Bounded queue"
2949:Paul E. Black.
2948:
2939:
2935:
2930:
2929:
2897:
2896:
2892:
2884:
2879:
2878:
2874:
2865:
2863:
2858:
2857:
2853:
2844:
2842:
2837:
2836:
2832:
2827:
2787:
2780:
2777:
2719:
2718:
2693:if and only if
2649:
2648:
2603:
2602:
2567:
2566:
2421:
2420:
2331:
2330:
2261:
2260:
2197:
2196:
2153:
2152:
2101:
2100:
2055:
2054:
2024:
2019:
2018:
1996:
1977:
1937:
1936:
1851:
1850:
1799:
1798:
1779:
1778:
1753:
1752:
1685:
1684:
1629:
1628:
1591:
1590:
1549:
1548:
1547:is then almost
1493:
1492:
1431:
1430:
1401:
1400:
1395:is the rear of
1347:
1346:
1295:
1294:
1261:
1260:
1241:
1240:
1212:
1211:
1208:
1206:Real-time queue
1184:
1183:
1152:
1151:
1132:
1131:
1112:
1111:
1083:
1082:
1063:
1062:
1043:
1042:
1014:
1013:
985:
984:
962:
961:
942:
941:
922:
921:
902:
901:
882:
881:
862:
861:
842:
841:
818:
817:
798:
797:
778:
777:
758:
757:
750:
748:Amortized queue
730:real-time queue
697:
696:
668:
667:
631:
630:
623:
618:
617:
614:
611:
608:
605:
602:
599:
596:
593:
590:
587:
584:
581:
578:
575:
572:
569:
566:
563:
560:
557:
554:
551:
548:
545:
542:
539:
536:
533:
530:
527:
524:
521:
518:
515:
512:
509:
506:
503:
493:
463:
457:
451:
447:
409:
349:data structures
328:
218:
209:
192:
187:
177:
172:
158:
149:
121:Time complexity
111:
86:
75:
69:
66:
56:Please help to
55:
39:
35:
28:
23:
22:
15:
12:
11:
5:
3478:
3476:
3468:
3467:
3457:
3456:
3450:
3449:
3447:
3446:
3440:
3437:
3436:
3434:
3433:
3428:
3423:
3417:
3415:
3409:
3408:
3406:
3405:
3404:
3403:
3393:
3392:
3391:
3389:Hilbert R-tree
3386:
3381:
3371:
3370:
3369:
3367:Fibonacci heap
3364:
3359:
3349:
3348:
3347:
3342:
3337:
3335:Red–black tree
3332:
3327:
3317:
3311:
3309:
3303:
3302:
3300:
3299:
3294:
3289:
3284:
3279:
3273:
3271:
3265:
3264:
3262:
3261:
3256:
3251:
3246:
3241:
3236:
3230:
3228:
3222:
3221:
3219:
3218:
3217:
3216:
3211:
3201:
3200:
3199:
3192:Priority queue
3189:
3188:
3187:
3177:
3172:
3167:
3166:
3165:
3160:
3149:
3147:
3141:
3140:
3138:
3137:
3132:
3126:
3124:
3120:
3119:
3114:
3112:
3111:
3104:
3097:
3089:
3083:
3082:
3077:
3070:
3069:External links
3067:
3066:
3065:
3047:
3030:William Ford,
3028:
3011:Clifford Stein
2996:
2970:
2967:
2966:
2965:
2934:
2931:
2928:
2927:
2890:
2872:
2851:
2829:
2828:
2826:
2823:
2822:
2821:
2815:
2813:Queuing theory
2810:
2808:Priority queue
2805:
2800:
2793:
2792:
2776:
2773:
2751:
2747:
2743:
2739:
2735:
2731:
2727:
2681:
2677:
2673:
2669:
2665:
2661:
2657:
2635:
2631:
2627:
2623:
2619:
2615:
2611:
2583:
2580:
2577:
2574:
2554:
2551:
2548:
2545:
2542:
2539:
2536:
2533:
2530:
2527:
2524:
2521:
2518:
2515:
2512:
2509:
2506:
2503:
2500:
2497:
2494:
2491:
2488:
2485:
2482:
2479:
2476:
2473:
2470:
2467:
2464:
2461:
2458:
2455:
2452:
2449:
2446:
2443:
2440:
2437:
2434:
2431:
2428:
2408:
2405:
2402:
2399:
2396:
2393:
2390:
2387:
2384:
2381:
2378:
2375:
2367:
2364:
2361:
2358:
2355:
2352:
2344:
2341:
2338:
2318:
2310:
2307:
2304:
2301:
2298:
2295:
2292:
2289:
2286:
2283:
2280:
2277:
2274:
2271:
2268:
2236:
2233:
2229:
2225:
2221:
2217:
2213:
2209:
2205:
2184:
2181:
2178:
2175:
2172:
2169:
2166:
2163:
2160:
2140:
2137:
2133:
2129:
2125:
2121:
2117:
2113:
2109:
2080:
2077:
2074:
2071:
2068:
2065:
2062:
2030:
2027:
2006:
2002:
1999:
1995:
1987:
1983:
1980:
1976:
1973:
1970:
1962:
1959:
1956:
1953:
1950:
1947:
1944:
1924:
1921:
1918:
1915:
1912:
1909:
1906:
1903:
1900:
1897:
1894:
1891:
1888:
1885:
1882:
1879:
1876:
1873:
1870:
1867:
1864:
1861:
1858:
1838:
1835:
1831:
1827:
1823:
1819:
1815:
1811:
1807:
1786:
1766:
1763:
1760:
1740:
1737:
1733:
1729:
1725:
1721:
1717:
1713:
1709:
1705:
1701:
1697:
1693:
1672:
1669:
1666:
1663:
1660:
1657:
1654:
1651:
1648:
1645:
1642:
1639:
1636:
1616:
1613:
1610:
1607:
1604:
1601:
1598:
1574:
1571:
1568:
1565:
1562:
1559:
1556:
1536:
1533:
1530:
1527:
1524:
1521:
1518:
1515:
1512:
1509:
1506:
1503:
1500:
1479:
1475:
1471:
1467:
1463:
1459:
1455:
1451:
1447:
1443:
1439:
1417:
1413:
1409:
1372:
1369:
1366:
1363:
1360:
1357:
1354:
1320:
1317:
1314:
1311:
1308:
1305:
1302:
1277:
1273:
1269:
1248:
1228:
1225:
1222:
1219:
1207:
1204:
1191:
1168:
1165:
1162:
1159:
1139:
1119:
1099:
1096:
1093:
1090:
1070:
1050:
1041:when the list
1030:
1027:
1024:
1021:
1001:
998:
995:
992:
980:is removed.
969:
949:
929:
909:
889:
869:
849:
825:
805:
785:
765:
749:
746:
713:
710:
707:
704:
684:
681:
678:
675:
658:per operation
647:
644:
641:
638:
622:
619:
502:
492:
489:
408:
405:
404:
403:
396:
395:
394:
387:
327:
324:
230:
229:
226:
225:
216:
207:
203:
202:
196:
195:
190:
185:
181:
180:
175:
170:
166:
165:
156:
147:
143:
142:
137:
132:
128:
127:
125:big O notation
113:
112:
105:
97:
96:
88:
87:
42:
40:
33:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
3477:
3466:
3463:
3462:
3460:
3445:
3442:
3441:
3438:
3432:
3429:
3427:
3424:
3422:
3419:
3418:
3416:
3414:
3410:
3402:
3399:
3398:
3397:
3394:
3390:
3387:
3385:
3382:
3380:
3377:
3376:
3375:
3372:
3368:
3365:
3363:
3362:Binomial heap
3360:
3358:
3355:
3354:
3353:
3350:
3346:
3343:
3341:
3338:
3336:
3333:
3331:
3328:
3326:
3323:
3322:
3321:
3318:
3316:
3313:
3312:
3310:
3308:
3304:
3298:
3295:
3293:
3290:
3288:
3285:
3283:
3280:
3278:
3275:
3274:
3272:
3270:
3266:
3260:
3259:Sparse matrix
3257:
3255:
3252:
3250:
3247:
3245:
3244:Dynamic array
3242:
3240:
3237:
3235:
3232:
3231:
3229:
3227:
3223:
3215:
3212:
3210:
3207:
3206:
3205:
3202:
3198:
3195:
3194:
3193:
3190:
3186:
3183:
3182:
3181:
3178:
3176:
3173:
3171:
3168:
3164:
3161:
3159:
3156:
3155:
3154:
3151:
3150:
3148:
3146:
3142:
3136:
3133:
3131:
3128:
3127:
3125:
3121:
3117:
3110:
3105:
3103:
3098:
3096:
3091:
3090:
3087:
3081:
3078:
3076:
3073:
3072:
3068:
3063:
3062:0-534-49182-0
3059:
3055:
3051:
3048:
3045:
3044:0-13-085850-1
3041:
3037:
3033:
3029:
3026:
3025:0-262-03293-7
3022:
3018:
3017:
3012:
3008:
3004:
3000:
2997:
2994:
2993:0-201-89683-4
2990:
2986:
2982:
2981:
2976:
2973:
2972:
2968:
2962:
2958:
2957:
2952:
2946:
2937:
2936:
2932:
2922:
2917:
2913:
2909:
2905:
2901:
2894:
2891:
2883:
2876:
2873:
2861:
2855:
2852:
2840:
2834:
2831:
2824:
2819:
2816:
2814:
2811:
2809:
2806:
2804:
2803:Message queue
2801:
2798:
2795:
2794:
2790:
2784:
2779:
2774:
2772:
2770:
2766:
2745:
2737:
2729:
2716:
2712:
2708:
2704:
2700:
2696:
2675:
2667:
2659:
2629:
2621:
2613:
2600:
2595:
2578:
2572:
2543:
2540:
2537:
2531:
2528:
2525:
2522:
2519:
2516:
2510:
2507:
2504:
2501:
2495:
2492:
2489:
2483:
2480:
2474:
2471:
2468:
2462:
2459:
2456:
2450:
2447:
2444:
2438:
2435:
2429:
2426:
2403:
2400:
2397:
2391:
2388:
2385:
2379:
2376:
2365:
2362:
2356:
2353:
2350:
2339:
2336:
2308:
2305:
2302:
2299:
2293:
2290:
2287:
2281:
2278:
2275:
2269:
2266:
2258:
2254:
2250:
2234:
2231:
2223:
2215:
2207:
2179:
2176:
2173:
2170:
2167:
2161:
2158:
2138:
2135:
2127:
2119:
2111:
2098:
2094:
2075:
2072:
2069:
2063:
2060:
2051:
2049:
2045:
2028:
2025:
2000:
1997:
1993:
1985:
1981:
1978:
1971:
1960:
1957:
1954:
1951:
1945:
1942:
1919:
1916:
1913:
1910:
1907:
1901:
1892:
1889:
1880:
1877:
1874:
1871:
1868:
1865:
1859:
1856:
1836:
1833:
1825:
1817:
1809:
1784:
1764:
1761:
1758:
1738:
1735:
1727:
1719:
1711:
1703:
1695:
1667:
1664:
1658:
1655:
1652:
1646:
1643:
1640:
1637:
1611:
1608:
1605:
1602:
1599:
1588:
1569:
1566:
1563:
1560:
1557:
1531:
1528:
1525:
1522:
1516:
1513:
1510:
1504:
1501:
1473:
1465:
1457:
1449:
1441:
1411:
1398:
1394:
1390:
1386:
1367:
1364:
1361:
1358:
1355:
1345:
1340:
1338:
1334:
1315:
1312:
1309:
1303:
1300:
1292:
1271:
1246:
1223:
1217:
1205:
1203:
1189:
1181:
1163:
1157:
1137:
1117:
1094:
1088:
1068:
1048:
1025:
1019:
996:
990:
981:
967:
947:
927:
907:
887:
867:
847:
839:
823:
803:
783:
763:
755:
747:
745:
743:
739:
735:
731:
727:
708:
702:
679:
673:
665:
661:
642:
636:
628:
620:
500:
498:
490:
488:
486:
481:
479:
475:
471:
468:. PHP has an
466:
460:
454:
445:
440:
438:
434:
430:
426:
422:
418:
414:
406:
401:
397:
392:
388:
385:
381:
380:
379:
376:
375:
374:
372:
367:
365:
364:bounded queue
360:
358:
354:
350:
346:
342:
338:
332:
325:
323:
321:
317:
313:
309:
305:
300:
298:
297:stack pointer
294:
290:
284:
282:
278:
274:
269:
267:
263:
262:
257:
253:
248:
245:
241:
237:
222:
217:
213:
208:
204:
201:
197:
191:
186:
182:
176:
171:
167:
162:
157:
153:
148:
144:
141:
138:
136:
133:
129:
126:
122:
118:
114:
109:
103:
98:
93:
84:
81:
73:
63:
59:
53:
52:
46:
41:
32:
31:
19:
3214:Disjoint-set
3179:
3053:
3050:Adam Drozdek
3035:
3032:William Topp
3014:
2984:
2983:, Volume 1:
2978:
2975:Donald Knuth
2954:
2906:(2): 50–54.
2903:
2899:
2893:
2875:
2864:. Retrieved
2862:. 2021-12-25
2854:
2843:. Retrieved
2833:
2768:
2764:
2714:
2710:
2709:during each
2706:
2702:
2698:
2694:
2598:
2596:
2256:
2252:
2248:
2096:
2095:followed by
2092:
2053:Let us call
2052:
2047:
2046:followed by
2043:
1586:
1399:without its
1396:
1392:
1388:
1384:
1341:
1336:
1332:
1290:
1209:
982:
837:
796:. The list
751:
729:
725:
659:
624:
494:
482:
446:provides a "
441:
436:
432:
428:
424:
410:
390:
368:
363:
361:
356:
352:
333:
329:
301:
293:linked lists
285:
270:
265:
259:
255:
251:
249:
239:
233:
220:
211:
160:
151:
139:
134:
76:
70:January 2014
67:
48:
3357:Binary heap
3282:Linked list
2763:, the list
860:. And, if
742:memoization
740:lists with
513:constructor
474:beanstalk'd
378:Linked list
62:introducing
3345:Splay tree
3249:Hash table
3130:Collection
2866:2022-05-11
2845:2014-05-22
2825:References
2797:Event loop
2647:, indeed,
2050:reversed.
1627:is almost
734:persistent
660:on average
497:JavaScript
465:ArrayDeque
459:LinkedList
244:collection
140:Worst case
45:references
3401:Hash tree
3287:Skip list
3234:Bit array
3135:Container
2921:1813/6273
2622:−
2597:The list
2532:
2511:
2496:
2463:
2439:
2430:
2392:
2357:
2340:
2294:
2270:
2162:
2064:
1946:
1887:_
1881:
1860:
1720:−
1647:
1505:
1466:−
1304:
1180:amortized
664:amortized
371:O(1) time
357:underflow
308:transport
131:Operation
3459:Category
3330:AVL tree
3209:Multiset
3158:Multimap
3145:Abstract
2775:See also
2029:′
2001:′
1982:′
1259:a list,
900:. When
666:time is
470:SplQueue
353:overflow
345:pointers
3384:R+ tree
3379:R* tree
3325:AA tree
2267:reverse
2259:. Then
2061:reverse
582:dequeue
573:element
546:element
540:enqueue
491:Example
478:Gearman
433:unshift
256:dequeue
252:enqueue
135:Average
58:improve
3413:Graphs
3374:R-tree
3315:B-tree
3269:Linked
3226:Arrays
3060:
3042:
3023:
3009:, and
2991:
2715:insert
2508:rotate
2427:rotate
2337:rotate
2291:rotate
2159:rotate
2017:where
1383:where
1110:where
756:named
724:where
591:return
442:C++'s
316:buffer
310:, and
184:Delete
169:Insert
146:Search
47:, but
3307:Trees
3180:Queue
3175:Stack
3123:Types
2947:from
2885:(PDF)
2251:, of
606:shift
600:items
561:items
528:items
507:Queue
504:class
453:Queue
448:queue
429:shift
400:deque
337:array
266:front
242:is a
240:queue
206:Space
95:Queue
3396:Trie
3352:Heap
3170:List
3058:ISBN
3040:ISBN
3021:ISBN
2989:ISBN
2961:NIST
2713:and
2711:tail
2529:CONS
2493:Cons
2460:CONS
2436:CONS
2419:and
2389:Cons
2354:Cons
1935:and
1878:Cons
1644:CONS
1502:CONS
1301:CONS
776:and
738:lazy
594:this
567:push
555:this
522:this
476:and
435:and
427:and
425:push
421:Ruby
419:and
417:Perl
391:last
291:and
261:peek
238:, a
193:O(1)
188:O(1)
178:O(1)
173:O(1)
108:FIFO
3204:Set
2916:hdl
2908:doi
2370:NIL
2347:NIL
2313:NIL
2042:is
1990:NIL
1965:NIL
1943:aux
1857:aux
1589:to
1291:NIL
744:.
609:();
437:pop
264:or
234:In
123:in
3461::
3052:.
3034:.
3013:.
3005:,
3001:,
2977:.
2959:.
2953:.
2914:.
2904:13
2902:.
1339:.
585:()
576:);
516:()
499::
480:.
398:A
382:A
373:.
362:A
322:.
306:,
219:O(
210:O(
159:O(
150:O(
3108:e
3101:t
3094:v
2963:.
2924:.
2918::
2910::
2887:.
2869:.
2848:.
2769:f
2765:f
2750:|
2746:r
2742:|
2738:=
2734:|
2730:f
2726:|
2707:f
2703:f
2699:s
2695:s
2680:|
2676:r
2672:|
2668:=
2664:|
2660:f
2656:|
2634:|
2630:r
2626:|
2618:|
2614:f
2610:|
2599:s
2582:)
2579:r
2576:(
2573:O
2553:)
2550:)
2547:)
2544:a
2541:,
2538:y
2535:(
2526:,
2523:r
2520:,
2517:f
2514:(
2505:,
2502:x
2499:(
2490:=
2487:)
2484:a
2481:,
2478:)
2475:r
2472:,
2469:y
2466:(
2457:,
2454:)
2451:f
2448:,
2445:x
2442:(
2433:(
2407:)
2404:a
2401:,
2398:y
2395:(
2386:=
2383:)
2380:a
2377:,
2374:)
2366:,
2363:y
2360:(
2351:,
2343:(
2317:)
2309:,
2306:r
2303:,
2300:f
2297:(
2288:=
2285:)
2282:r
2279:,
2276:f
2273:(
2257:a
2253:r
2249:f
2235:1
2232:+
2228:|
2224:f
2220:|
2216:=
2212:|
2208:r
2204:|
2183:)
2180:a
2177:,
2174:r
2171:,
2168:f
2165:(
2139:1
2136:+
2132:|
2128:f
2124:|
2120:=
2116:|
2112:r
2108:|
2097:r
2093:f
2079:)
2076:r
2073:,
2070:f
2067:(
2048:r
2044:f
2026:f
2005:)
1998:f
1994:,
1986:,
1979:f
1975:(
1972:=
1969:)
1961:,
1958:r
1955:,
1952:f
1949:(
1923:)
1920:s
1917:,
1914:r
1911:,
1908:f
1905:(
1902:=
1899:)
1896:)
1893:s
1890:,
1884:(
1875:,
1872:r
1869:,
1866:f
1863:(
1837:1
1834:+
1830:|
1826:f
1822:|
1818:=
1814:|
1810:r
1806:|
1785:s
1765:x
1762:u
1759:a
1739:1
1736:+
1732:|
1728:r
1724:|
1716:|
1712:f
1708:|
1704:=
1700:|
1696:s
1692:|
1671:)
1668:s
1665:,
1662:)
1659:r
1656:,
1653:x
1650:(
1641:,
1638:f
1635:(
1615:)
1612:s
1609:,
1606:r
1603:,
1600:f
1597:(
1587:x
1573:)
1570:s
1567:,
1564:r
1561:,
1558:f
1555:(
1535:)
1532:s
1529:,
1526:r
1523:,
1520:)
1517:f
1514:,
1511:x
1508:(
1499:(
1478:|
1474:r
1470:|
1462:|
1458:f
1454:|
1450:=
1446:|
1442:s
1438:|
1416:|
1412:r
1408:|
1397:f
1393:s
1389:r
1385:f
1371:)
1368:s
1365:,
1362:r
1359:,
1356:f
1353:(
1337:t
1333:h
1319:)
1316:t
1313:,
1310:h
1307:(
1276:|
1272:l
1268:|
1247:l
1227:)
1224:1
1221:(
1218:O
1190:f
1167:)
1164:1
1161:(
1158:O
1138:f
1118:n
1098:)
1095:n
1092:(
1089:O
1069:r
1049:r
1029:)
1026:1
1023:(
1020:O
1000:)
997:1
994:(
991:O
968:r
948:r
928:f
908:r
888:r
868:r
848:f
824:r
804:f
784:r
764:f
726:n
712:)
709:n
706:(
703:O
683:)
680:1
677:(
674:O
646:)
643:1
640:(
637:O
615:}
612:}
603:.
597:.
588:{
579:}
570:(
564:.
558:.
552:{
549:)
543:(
537:}
534:;
531:=
525:.
519:{
510:{
223:)
221:n
214:)
212:n
163:)
161:n
154:)
152:n
83:)
77:(
72:)
68:(
54:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
