Geek asks and answers

Permanent Queue Data Structure

I need to create a class Constant Queue in which the enqueue function takes an element that puts it in the current queue and returns a new queue. As always, the initial queue remains unchanged. Similarly, the dequeue function removes the front element a, returns a new queue, but the original queue remains unchanged. Of course, this can be done in O (queue length), but I can do it faster.

+3
source share
3 answers

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

To add a new item, you need to create a new instance of the queue class, set its start item to the copied queue run item, and create a new end item.

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

The queue class may 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 the methods of the queue addand removeis equal to O (1).

Please note that you can iterate over this queue only in reverse order (i.e. latest elements). Perhaps you can come up with something that can be repeated differently or even in both directions.

+2
source

I suggest taking a look at the scala implementation. The comment at the top of the class describes the approach chosen (complexity:) O(1).

Queue List s, '' in '', '' out ''.    '' in '' '' out ''. '' out '' ,   "out" "in.reverse" "in" "Nil".  

O(1). O(1),   , O(n), n - . ,  n O(1) . O(1).

http://xuwei-k.imtqy.com/scala-library-sxr/scala-library-2.10.0/scala/collection/immutable/Queue.scala.html

+2

Java Chronicle ( : ). , tmpfs ( ).

, , ( ).

, , .

, , , O (1) .

Because Chronicle uses a compact binary form, the limit on the amount of space you can save is limited by disk space. for example, a 2 TB drive can store this data even on an 8 GB machine before you have to rotate the queue logs.

0
source

More articles:


All Articles