Оценка сложности алгоритма поиска минимума

Какова сложность алгоритма поиска минимума в очереди, если при добавлении элемента я ищу минимальный элемент, при удалении, если элемент очереди равен минимальному, то удаляю его и опять ищу минимальный элемент, а в функции вывода минимального элемента просто вывожу минимальный элемент. Хотелось бы узнать оценку сложности алгоритма. Если есть ссылки на реализацию поиска минимума с использованием двух стеков, то просьба выложить их в комментах

typedef struct Queue {
    int size;
    int min;
    int *arr;
}Queue;

int findMin(Queue *q) {
    int min = 1000001;
    for (int i = 0; i < q->size; ++i) {
        if (q->arr[i] < min) {
            min = q->arr[i];
        }
    }
    return min;
}

void push(struct Queue *queue, int elem) {
    queue->size++;
    queue->arr  = (int *)realloc(queue->arr, queue->size);
    for (int i = queue->size; i > -1; --i) {
        queue->arr[i] = queue->arr[i-1];
    }
    queue->arr[0] = elem;
    queue->min = findMin(queue);
}

void pop(Queue *q) {
    if (q->arr[q->size-1]==q->min) {
        q->min = findMin(q);
    }

     q->size--;
     q->arr  = (int *)realloc(q->arr, q->size);
}

int showMin(Queue *q) {
    return q->min;
}