CODEWITHSUNDEEP
javadata-structures
Aditya Nambiar
Aditya Nambiar

Reputation: 886

Persistent Queue datastructure

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.??

Upvotes: 4

Views: 3096

Answers (3)

Gab
Gab

Reputation: 8332

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

Upvotes: 3

Njol
Njol

Reputation: 3279

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.

Upvotes: 1

Peter Lawrey
Peter Lawrey

Reputation: 533880

What I do is use Java Chronicle (disclaimer: which I wrote). This is an unbounded off heap persisted queue which is stored on disk or tmpfs (shared memory).

In this approach your consumer keeps track of where it is up to in the queue, but no entry is actually removed (except in a daily or weekly maintenance cycle)

This avoids the need to alter the queue except when adding to it, and you would not need to copy it.

As such maintaining multiple references to where each consumer believes is the tail of the queue is O(1) for each consumer.

As Chronicle uses a compact binary form, the limit to how much you can store is limited by your disk space. e.g. a 2 TB drive can store this much data even on a machine with 8 GB before you have to rotate the queue logs.

Upvotes: 0

Related Questions