 # FIFO LinkedList Queue in Motoko

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

};
};``````
3 Likes

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 `pop`s.

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()
}
}
}
}
};
};
}``````
6 Likes

Oops. I see that my code has at least one bug (need to set `second` back to `null` after reversing it). Will fix above.

6 Likes

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`

Very cool and works

6 Likes

I implemented a functional one here if it’s of use to you @rckprtr

2 Likes