only push/pop operations. Since J2SE5.0, Java's library contains a interface that specifies queue operations; implementing classes include and (since J2SE 1.6) . PHP has an SplQueue class and third party libraries like beanstalk'd and Gearman. Example A simple queue implemented in JavaScript: class Queue { constructor() { this.items = []; } enqueue(element) { this.items.push(element); } dequeue() { return this.items.shift(); } } Purely functional implementation Queues can also be implemented as a purely functional data structure. There are two implementations. The first one only achieves per operation on average. That is, the amortized time is , but individual operations can take 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. Amortized queue This queue's data is stored in two singly-linked lists named and . The list holds the front part of the queue. The list holds the remaining elements (a.k.a., the rear of the queue) in reverse order. It is easy to insert into the front of the queue by adding a node at the head of . And, if is not empty, it is easy to remove from the end of the queue by removing the node at the head of . When is empty, the list is reversed and assigned to and then the head of is removed. The insert ("enqueue") always takes time. The removal ("dequeue") takes when the list is not empty. When is empty, the reverse takes where is the number of elements in . But, we can say it is amortized time, because every element in had to be inserted and we can assign a constant cost for each element in the reverse to when it was inserted. Real-time queue The real-time queue achieves time for all operations, without amortization. This discussion will be technical, so recall that, for a list, denotes its length, that NIL represents an empty list and represents the list whose head is h and whose tail is t. The data structure used to implement our queues consists of three singly-linked lists where f is the front of the queue, r is the rear of the queue in reverse order. The invariant of the structure is that s is the rear of f without its first