So I have been trying to make a FIFO queue that is based on a Linked-List and realized that every technique I come up with ends up being a FILO queue.
Im trying to wrap my mind around how I might reuse the Node type below, which is a linked-list and reuse the variables so I might have a pointer to the first item in the list and a pointer to the last item in the list.
So instead of current, I would have: first: Node<T> //pointer to head last: Node<T> //pointer to end
Code Below
module {
public type Node<T> = ?(T, Node<T>);
public class Queue<T>() {
public var current : Node<T> = null;
public func isEmpty() : Bool {
switch current {
case null { true };
case _ { false };
}
};
public func enqueue(item : T) {
if(isEmpty()){
current := ?(item, null);
} else {
current := ?(item, current);
};
};
//this will return the first
//but how do I remove that item
//what if the list is 100k items long
//how would I just have a pointer to
//the first item and just set first to
//be previous item?
public func dequeueFIFO() : ?T {
func rec(l : Node<T>) : ?T {
switch l {
case null { null };
case (?(x, null)) { ?x };
case (?(x, t)){ rec(t) };
};
};
rec(current)
};
// this will return the last entry FILO
public func dequeue() : ?T {
switch current {
case null { null };
case (?(x, null)) {
current := null;
?x
};
case (?(x, t)){
current := t;
?x
};
};
};
};
};
There’s this way to do a FIFO with two pure linked lists; see below.
The key “trick” is to have a pair of lists, not just one, and to do pushes on one (the second) and pops on the other (the first); whenever the first is empty but the second is not, the technique introduces a step where the elements from the second list are reversed when moved into the first, for more pops.
That reverse step “fixes” the issue you are having with the LIFO order, IIUC.
To analyze the complexity of this approach, people usually employ some kind of amoritized analysis (not worst-case analysis). In that way of analyzing the complexity, each operation only requires O(1) time, even though the “worst case” will be O(n) for some pop steps.
To get a better worst-case time, I would use the Buf module in the standard library to implement something like a ring buffer. That’s more complex, and perhaps not really needed (but please correct me if that’s mistaken).
import List "mo:std/list";
module {
public class Fifo<T>() {
// invariant: fifo-elements = first @ (rev second)
public var first : List.List<T> = List.nil<T>();
public var second : List.List<T> = List.nil<T>();
public func isEmpty() : Bool {
switch (first, second) {
case (null, null) true;
case _ false;
}
};
public func push(item : T) {
// items go on to the second list in revserse-FIFO order:
second := ?(item, second)
};
public func pop() : ?T {
switch first {
case (?(hd, tl)) {
first := tl;
?hd
};
case null {
switch second {
case null null;
case (?_) {
// items into FIFO order on first list:
first := List.rev<T>(second);
second := null;
pop()
}
}
}
}
};
};
}
Ok I get it, basically when you call Pop the first time it creates the first list of reversed queue items and then pops from that until its empty. As you push into the second list it keeps growing until first is empty this cutting new list of items to pop…