information:classification, linguistic:paraphrasing
Purely functional implementation

Queues can also be implemented as a purely functional data structure. There are two implementations. The first one only achieves O (1) {\displaystyle O(1)} per operation on average. That is, the amortized time is O (1) {\displaystyle O(1)}, but individual operations can take O (n) {\displaystyle O(n)} where n is the number of elements in the queue. The second implementation is called a real-time queue and it allows the queue to be persistent with operations in O(1) worst-case time. It is a more complex implementation and requires lazy lists with memoization.