Реализация быстрой очереди на Lua

    queue = {}

    -- в разных участках кода добавляем элементы в очередь:
    queue[#queue + 1] = val1

    queue[#queue + 1] = val2

    queue[#queue + 1] = val3

    queue[#queue + 1] = val4

    queue[#queue + 1] = val5

    -- И потом разбираем очередь через такую банальную функцию:

    function queue_dispatch()
        --Если нет элементов, то сразу выходим
        if #queue == 0 then return end

        -- Пока есть элементы, получаем первый, обрабатываем его и удаляем из очереди
        while #queue ~= 0 do
            local value = queue[1]
            table.remove(queue, 1)
            -- Что-то делаем с элементом value
            -- ...
        end
    end

    ----   Функции работы с очередями --
    --- При использовании между потоком колбеков и потоком main очереди потокобезопасные.
    --- Создать очередь
    function QueueNew()
        return  {first = 1, last = 0 }
    end
    ---  Записать в очередь --
    function QueuePush(self, v)
        if v == nil then error('!!! Ошибка. Параметр v функции QueuePush nil') end
        local last = self.last + 1
        self[last] = v
        self.last = last
        return last - self.first + 1    -- количество элементов в очереди ---
    end
    ---  Читать очередь  --
    function QueuePop(self)
        local  first =  self.first
        if  first > self.last then return nil   end
        local v, v1  =  self[first], self[first + 1]
        self[first]  =  nil
        self.first   = first + 1
        v1 = type (v1) == 'string' and #v1 or 0
        return  v, v1   -- v1 -длина следующего элемента (если строка) ---
    end

    -- Текущий размер очереди ---
    function QueueSize(self)
        return self.last - self.first + 1
    end

    local q = QueueNew()
    -- Помещаем 10 элементов в очередь
    for i = 1, 10 do
        QueuePush(q, i)
    end

    -- Вынимаем элементы, пока очередь не опустеет.
    local x = QueuePop(q)
    local s = 1
    print(s, 'x: ', x, 'q['..s..']', q[s], 'size', QueueSize(q), 'first', q.first, 'last', q.last)
    while x do
        x = QueuePop(q)
        s = s + 1
        print(s, 'x: ', x, 'q['..s..']', q[s], 'size', QueueSize(q), 'first', q.first, 'last', q.last)
    end

    for i = 1, 10 do
        QueuePush(q, i)
    end

    s = q.first
    x = QueuePop(q)
    print(s, 'x: ', x, 'q['..s..']', q[s], 'size', QueueSize(q), 'first', q.first, 'last', q.last)
    while x do
        x = QueuePop(q)
        s = s + 1
        print(s, 'x: ', x, 'q['..s..']', q[s], 'size', QueueSize(q), 'first', q.first, 'last', q.last)
    end

    if  first > self.last then
        self.first = 1
        self.last = 0
        return nil
    end

    -- Создаем класс для очереди
    local queue_class = {}
    queue_class.__index = queue_class
    -- Добавляем метамод __len, чтобы работал вариант добавления в очередь через q[#q+1] = value
    function queue_class.__len(self)
        return self.head == nil and 0 or 1
    end
    function queue_class.__newindex(self, _, value)
        self:push(value)
    end

    -- Создаем экземпляр очереди. Он хранит два важных элемента head - голова (первый элемент) очереди, tail - хвост (последний элемент) очереди.
    -- Использование rawset(table, key, value) для поддержки варианта добавления через q[#q+1] = value
    -- pool - это ссылка на прошлый удаленный узел, чтобы при добавлении нового элемента в очередь не выделять дополнительную память, а использовать уже выделенное ранее.
    function queue_class.new()
        local self = setmetatable({}, queue_class)
        rawset(self, 'head', nil)
        rawset(self, 'tail', nil)
        rawset(self, 'pool', nil)
        return self
    end

    -- Помещаем элемент в очередь.
    function queue_class:push(value)
        local node
        local pool = self.pool
        if pool then
            node = pool
            rawset(self, 'pool', pool.next)
            node.value = value
            node.next = nil
            node.prev = nil
        else
            node = {value = value, next = nil, prev = nil}
        end
        if self.tail then
            self.tail.next = node
            node.prev = self.tail
            rawset(self, 'tail', node)
        else
            rawset(self, 'head', node)
            rawset(self, 'tail', node)
        end
    end

    -- Извлекает элемент из начала очереди
    function queue_class:pop()
        if not self.head then return end
        local node = self.head
        rawset(self, 'head', node.next)
        if self.head then
            self.head.prev = nil
        else
            rawset(self, 'tail', nil)
        end
        local value = node.value
        node.value = nil
        node.next = self.pool
        node.prev = nil
        -- Возврат в пул
        rawset(self, 'pool', node)
        return value
    end

    -- Удаляет конкретный узел из любого места очереди за O(1)
    function queue_class:remove(node)
        if not node.next and not node.prev and self.head ~= node and self.tail ~= node then
            return
        end
        local next_node = node.next
        local prev_node = node.prev
        if prev_node then
            prev_node.next = next_node
        else
            rawset(self, 'head', next_node)
        end
        if next_node then
            next_node.prev = prev_node
        else
            rawset(self, 'tail', prev_node)
        end
        node.value = nil
        node.next = self.pool
        node.prev = nil
        rawset(self, 'pool', node)
    end

    -- Итератор по очереди
    -- Возвращает функцию, которую можно использовать в цикле for.
    -- Безопасен к вызову self:remove() внутри тела цикла.
    function queue_class:next()
        local next_node = self.head
        return function()
            local current_node = next_node
            if current_node then
                next_node = current_node.next
                return current_node, current_node.value
            end
            return nil
        end
    end

    -- Пример использования (как это работает на практике):
    -- Создаем очередь
    local q = Queue.new()

    q:push("Задача 1")
    q:push("Задача 2 (удалить)")
    q:push("Задача 3")
    q:push("Задача 4")

    q[#q+1] = "Задача 5" -- Демонстрация возможности добавления как в обычный массив.

    print("--- Итерация с удалением ---")
    for node, value in q:GetNext() do
        print("Обрабатываю:", value)

        if value == "Задача 2 (удалить)" then
            print("  -> Удаляю этот узел!")
            q:remove(node)
            -- Итератор не сломается, так как он уже запомнил "Задача 3" как next_node
        end
    end

    print("\n--- Проверяем что осталось ---")
    for node, value in q:GetNext() do
        print("Осталось:", value)
    end