30015：整数双端队列

题目

实现使用环形数组的整数双端队列。队列拥有自己的存储；扩容失败时不得改变队列，弹出失败时不得改变输出对象。

解析

用 head 指向逻辑首元素，用 size 表示元素个数。容量非零时，逻辑位置 offset 对应的物理位置是从 head 向后绕行 offset 步的位置。为了避免 head + offset 的大小计算溢出，位置计算采用一次条件减法。

扩容时先分配新数组，再按逻辑顺序复制旧数组。复制完成后才释放旧数组并把 head 归零；因此分配失败不会改变原队列。队列始终满足：size <= capacity，空容量与空存储指针同时出现，且非空容量下 head < capacity。

答案

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

typedef struct IntDeque IntDeque;

struct IntDeque {
    int64_t *items;
    size_t capacity;
    size_t head;
    size_t size;
};

static size_t deque_at(
    const IntDeque *deque,
    size_t offset
) {
    size_t distance = deque->capacity - deque->head;
    if (offset >= distance) {
        return offset - distance;
    }
    return deque->head + offset;
}

static bool deque_grow(IntDeque *deque) {
    if (deque->capacity > SIZE_MAX / sizeof *deque->items) {
        return false;
    }

    size_t maximum = SIZE_MAX / sizeof *deque->items;
    size_t next = deque->capacity == 0 ? 8 : deque->capacity;
    if (next > maximum) {
        return false;
    }
    while (next <= deque->size) {
        if (next > maximum / 2) {
            next = maximum;
            break;
        }
        next *= 2;
    }
    if (next <= deque->size || next == 0) {
        return false;
    }

    int64_t *replacement = malloc(next * sizeof *replacement);
    if (replacement == NULL) {
        return false;
    }
    for (size_t i = 0; i < deque->size; ++i) {
        replacement[i] = deque->items[deque_at(deque, i)];
    }
    free(deque->items);
    deque->items = replacement;
    deque->capacity = next;
    deque->head = 0;
    return true;
}

IntDeque *int_deque_create(void) {
    IntDeque *deque = malloc(sizeof *deque);
    if (deque == NULL) {
        return NULL;
    }
    deque->items = NULL;
    deque->capacity = 0;
    deque->head = 0;
    deque->size = 0;
    return deque;
}

void int_deque_destroy(IntDeque *deque) {
    if (deque == NULL) {
        return;
    }
    free(deque->items);
    free(deque);
}

static bool deque_prepare_push(IntDeque *deque) {
    if (deque == NULL) {
        return false;
    }
    if (deque->size < deque->capacity) {
        return true;
    }
    return deque_grow(deque);
}

bool int_deque_push_front(IntDeque *deque, int64_t value) {
    if (!deque_prepare_push(deque)) {
        return false;
    }
    deque->head = deque->head == 0
        ? deque->capacity - 1
        : deque->head - 1;
    deque->items[deque->head] = value;
    ++deque->size;
    return true;
}

bool int_deque_push_back(IntDeque *deque, int64_t value) {
    if (!deque_prepare_push(deque)) {
        return false;
    }
    deque->items[deque_at(deque, deque->size)] = value;
    ++deque->size;
    return true;
}

bool int_deque_pop_front(IntDeque *deque, int64_t *out_value) {
    if (deque == NULL || out_value == NULL || deque->size == 0) {
        return false;
    }
    *out_value = deque->items[deque->head];
    deque->head = deque->head + 1 == deque->capacity
        ? 0
        : deque->head + 1;
    --deque->size;
    if (deque->size == 0) {
        deque->head = 0;
    }
    return true;
}

bool int_deque_pop_back(IntDeque *deque, int64_t *out_value) {
    if (deque == NULL || out_value == NULL || deque->size == 0) {
        return false;
    }
    size_t index = deque_at(deque, deque->size - 1);
    *out_value = deque->items[index];
    --deque->size;
    if (deque->size == 0) {
        deque->head = 0;
    }
    return true;
}

size_t int_deque_size(const IntDeque *deque) {
    return deque == NULL ? 0 : deque->size;
}

扩容只在队列已满时发生；因此两端插入的摊还复杂度为 $O(1)$，两端删除和查询大小为 $O(1)$。