Content deleted Content added
Adding local short description: "Data structure implementable in purely functional languages", overriding Wikidata description "persistent data structure that does not rely on mutable state" |
Seriousman9 (talk | contribs) →Amortized analysis and scheduling: I made what I believe to be a small edit on this topic, by reference to the page on the real-time queue (https://en.wikipedia.org/wiki/Queue_(abstract_data_type)#Real-time_queue). However, it did reverse the meaning of a part of the article, and I am only now learning about these things. |
||
Line 50:
====Example: queue====
[[Amortized queue]]s{{r|Okasaki-book|p=65}}{{r|Okasaki-book|p=73}} are composed of two singly-linked lists: the front and the reversed rear. Elements are added to the rear list and are removed from the front list. Furthermore, whenever the front queue is empty, the rear queue is reversed and becomes the front, while the rear queue becomes empty. The amortized time complexity of each operation is constant. Each cell of the list is added, reversed and removed at most once. In order to avoid an inefficient operation where the rear list is reversed, [[real-time queue]]s add the restriction that the rear list is only as long as the front list. To ensure that the
==See also==
| |||