FIFO Queue

Related Projects Algorithms
1

Hi, i'm wondering if there's an easy way to get a FIFO queue with O(1) complexity on Push() and Pop() in swift, and ended up looking at the "Algorithm" project.

Is this the correct place to look for ?
I'm pretty sure i could come up with a basic implementation, but i'm also pretty sure this is exactly the kind of structure that would end up to be hard to get optimal performance for without solid stdlib experience.

2

You can grab the one implemented in swift-nio here: https://github.com/apple/swift-nio/blob/main/Sources/NIO/CircularBuffer.swift

It already conforms to most protocols you'd want and is well vetted.

5 Likes
3

Thanks, i'll have a look. I understand the behavior is similar to a queue by default if the buffer keeps growing, but i'm having a bit of a mental block using a class called "circularbuffer" for a queue.

It the algorithm project thinking about implementing a high-level container hierarchy ? a bit similar to what stdlib did with the Sequence (and all the rest) ?

4

It's not similar, it's identical. A FIFO queue isn't a data structure, it's a description of behavior. There are various ways to implement that behavior. Array can be used as a FIFO queue, but you add the further constraints that you want O(1) time complexity for push/pop, which disqualifies Array.

Two data structures that match your description are a resizing ring buffer like this one, or a linked list (whose performance is usually hot garbage, don't use these 99% of the time).

If you want to enforce the FIFO nature of it, then I suggest you make a Queue protocol, whose only methods are push() and pop(), then you can extend SwiftNIO's CircularBuffer to conform.

Though yeah, I really wish such basic batteries were included in the standard library.

3 Likes
5

To get O(1) complexity for push and pop (not searching) the ideal candidate is a LinkedList with a tail and a head node. Pushing adds an element to the tail, popping moves the head one step forward. This should be easy to implement. But, the only caveat is that this doesn't allow easy access to an element at a random index. Searching will also require you to traverse through the list until you find the element (which would cost O(n) complexity).

6

Since this thread was started, we've launched the Swift Collections package that comes with a Deque that can be used as a FIFO queue.

1 Like
7

Do I need to make something like this or is there better cooked method of having a FIFO?

struct FIFO<Value> {
    var data = Deque<Value>()
    
    mutating func push(_ newElement: Value) {
        data.append(newElement)
    }
    
    mutating func pop() -> Value {
        guard let first = data.popFirst() else {
            fatalError("Trying to popFirst() on an empty Deque!")
        }
        return first
    }
}