持久性隊列數據結構

我需要創建一個類持久化隊列，其中函數入隊需要一個元素將其排入當前隊列並返回新隊列。原始隊列如何保持不變。同樣，出列函數刪除前面的元素，返回新的隊列，但原始隊列保持不變。這當然可以在O（隊列的長度）中完成，但我可以做得更快。持久性隊列數據結構

來源

2014-01-14 Aditya Nambiar

是否有任何理由爲什麼你需要一成不變的隊列？ – Njol

@ Gab是的，因爲回答無用的問題是無用的。如果我們知道提問者打算做什麼，那麼可以提出更好的方法，而不是提問者最初打算做的事情。 – Njol

回到主題：我相信你將無法複製任何集合的每個元素，而無需迭代每個元素一次。因此，比O（n）好看似乎對我來說不合理。 – ccjmne

你可以使用鏈表作爲隊列（不是LinkedList，但是你自己的實現）。

要添加一個新元素，您只需創建一個新的隊列類實例，將其開始元素設置爲複製隊列的開始元素，並創建一個新的結束元素。

刪除元素與此類似，但將新隊列的結束元素設置爲複製隊列的倒數第二個元素。

隊列類看起來是這樣的：

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); 
}

的這一隊列的add和remove方法複雜度爲O（1）。

請注意，您只能以相反的順序（即最新的元素）迭代此隊列。也許你可以想出一些可以以其他方式迭代或甚至在兩個方向上迭代的東西。

來源

2014-01-14 08:37:12 Njol

雙向鏈表應該允許你在兩個方向上迭代。 –

@PeterLawrey然後你將不能在O（1）中添加或刪除，因爲你必須複製每個節點（如果我的代碼天真地擴展了一個新的'Node previous'） – Njol

好點。每個隊列都需要有一個自己的前一個字段。如果你只有一個生產者，這將不是一個問題。 –

我所做的是使用Java Chronicle（免責聲明：我寫的）。這是存儲在磁盤或tmpfs（共享內存）上的一個無界的堆持久化隊列。

在這種方法您的消費跟蹤，其中它是由在排隊，但沒有進入實際刪除（除非在每天或每週的保養週期）

這避免了需要改變的隊列中，除了當添加到它時，你不需要複製它。因此，保持對每個消費者認爲的地方的多個引用是每個消費者的隊列的尾部是O（1）。

由於Chronicle使用緊湊的二進制格式，因此可以存儲多少的限制受到磁盤空間的限制。例如即使在8 GB的計算機上，2 TB驅動器也可以存儲大量數據，然後再旋轉隊列日誌。

來源

2014-01-14 08:35:02

您不能使用此方法添加元素而不修改數據結構 – Njol

@Njol如果您需要此功能，您還可以記錄結束位置。要拍攝所有你需要知道的是開始和結束。 O（1）。只有當您想添加到多個快照並且您不能應用排隊消息的任何過濾器時，問題纔會出現。 –

我建議看看scala的實現。對課程頂部的評論描述了所選方法（複雜性：O(1)）。

Queue被實現爲對List S，一個包含「」中「」的元素和其它的「」出來「」元素。
元素被添加到''in''列表中，並從''out''列表中刪除。當'out''列表乾涸時，隊列通過用'in.reverse'替換''out''列表，並用''Nil''替換''in''。

將項目添加到隊列始終有成本O(1)。刪除物品的費用爲O(1)，但在需要數據透視的情況下爲，在這種情況下，將產生O(n)的費用，其中n是隊列中元素的數量。發生這種情況時， n刪除操作與O(1)成本有保證。刪除項目平均爲O(1)。

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

來源

2014-01-14 08:51:00 Gab

持久性隊列數據結構

回答

相關問題