Persistent Queue datastructure

Question

I need to make a class Persistent queue in which the function enqueue takes an element enqueues it to the current queue and return the new queue. How ever the original queue remains unchanged. Similarly the dequeue function removes the front element an returns the new queue but the original queue remains unchanged. This can of course be done in O(length of queue) but can i do it faster.??

Answer 1

I suggest to have a look to scala implementation. Comment at the top of the class describes the chosen approach (complexity : O(1)).

Queue is implemented as a pair of Lists, one containing the ''in'' elements and the other the ''out'' elements.
Elements are added to the ''in'' list and removed from the ''out'' list. When the ''out'' list runs dry, the queue is pivoted by replacing the ''out'' list by ''in.reverse'', and ''in'' by ''Nil''.

Adding items to the queue always has cost O(1). Removing items has cost O(1), except in the case where a pivot is required, in which case, a cost of O(n) is incurred, where n is the number of elements in the queue. When this happens, n remove operations with O(1) cost are guaranteed. Removing an item is on average O(1).

http://xuwei-k.github.io/scala-library-sxr/scala-library-2.10.0/scala/collection/immutable/Queue.scala.html

Answer 2

You can use a linked list as queue (not LinkedList, but your own implementation).

To add a new element you only have to create a new instance of your queue class, set its start element to the copied queue's start element, and create a new end element.

Removing an element is similar, but set the end element of the new queue to the second to last element of the copied queue.

The queue class could look like this:

static class Node {
    final Node next;
    final Object o;
    Node(Node next, Object o) {...}
}

final Node start, end;

private Queue(Node start, Node end) {...}

public Queue(Object o) {
    start = end = new Node(null, o);
}

public Queue add(Object o) {
    return new Queue(start, new Node(end, o));
}

public Queue remove() {
    return new Queue(start, end.next);
}

The complexity of this queue's add and remove methods is O(1).

Please note that you can only iterate this queue in reverse order (i.e. newest elements first). Maybe you can come up with something that can be iterated the other way around or even in both directions.