0

I am looking for a way to efficiently implement a FIFO array - queue. I have seen multiple workarounds with using mappings etc, but I'm interested in potential array-only approaches for this.

I need a simple array for storing values via push(value), with a custom popFirst() function which would remove the first element of the array, thus resulting in previous array[n] elements being moved logically to array[n-1]. I would put accent on logically, because moving all elements one step back is gas-costly.

A potential idea I have is to manipulate the array pointer to point to array[1] instead of array[0], but I am not sure if this is a viable/safe solution.

Any help is greatly appreciated!

3
  • Your best option is to track the index of the fifo's first entry. An array location is computed from the storage slot it is using, there's no array pointer.
    – Ismael
    Commented Jun 10, 2022 at 3:20
  • @ismael This is something that I've had in mind as well. In case I take this approach, does calling delete array[nextInLine++] give gas refunds?
    – lizardev
    Commented Jun 12, 2022 at 16:24
  • Yes, delete or assigning zero should count for a refund.
    – Ismael
    Commented Jun 12, 2022 at 20:11

1 Answer 1

1

Using mappings for this goal is more gas efficient since you are not paying for range and other checks that comes with arrays. Under the hood, dynamic sized arrays and mappings works pretty much the same so there is no actual gas wise benefit in using arrays. you can read more about this here

You can use something like this:

pragma solidity >=0.8.4;
contract Queue {
    mapping (uint256 => uint256 /* or any other type */ ) queue;
    uint256 first = 1;
    uint256 last = 1;
    function enqueue(uint256 data) public {
        last += 1;
        queue[uint256] = data;
    }

    function dequeue() public returns (uint256) {
        uint256 data;
        require(last > first);
        data = queue[first];
        delete queue[first];
        first += 1;
        return data
    }
    function length() public view returns (uint256) {
        return last - first;
    }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.