leetcode.895.c

typedef struct Q {
    int val;
    int sp;
    int time[20000];
    struct Q* left;
    struct Q* right;
} Q;

Q* qCreate(int val, int time) {
    Q* q = malloc(sizeof(Q));
    q->val = val;
    q->sp = 0;
    q->time[q->sp++] = time;
    return q;
}

void qTouch(Q* q, int time) {
    q->time[q->sp++] = time;
}

int qDrain(Q* q) {
    if (!q->sp) return q->val;
    q->time[--q->sp];
    return q->val;
}

Q* qRotateLeft(Q* q) {
    Q* right = q->right;
    if (!right) return q;
    q->right = right->left;
    right->left = q;
    return right;
}

Q* qRotateRight(Q* q) {
    Q* left = q->left;
    if (!left) return q;
    q->left = left->right;
    left->right = q;
    return left;
}

bool qIsGE(Q* q, Q* node) {
    int qLen = q ? q->sp : 0;
    int nodeLen = node ? node->sp : 0;
    int qHead = qLen > 0
        ? q->time[qLen - 1]
        : -1;
    int nodeHead = nodeLen > 0
        ? node->time[nodeLen - 1]
        : -1;
    if (qLen > nodeLen) return true;
    if (qLen == nodeLen && qHead > nodeHead) return true;
    return false;
}

Q* qBalance(Q* q) {
    Q* curr = q;
    if (!curr) return NULL;
    if (qIsGE(curr, curr->left) && qIsGE(curr, curr->right)) {
        return curr;
    }
    if (qIsGE(curr->left, curr->right)) {
        curr = qRotateRight(curr);
        curr->right = qBalance(curr->right);
        return curr;
    } else {
        curr = qRotateLeft(curr);
        curr->left = qBalance(curr->left);
        return curr;
    }
}

Q* qPush(Q* q, int val, int time) {
    if (!q) {
        return qCreate(val, time);
    }
    if (q->val == val) {
        qTouch(q, time);
        return qBalance(q);
    }
    if (q->val > val) {
        q->left = qPush(q->left, val, time);
    } else {
        q->right = qPush(q->right, val, time);
    }
    return qBalance(q);
}

void qFree(Q* q) {
    if (q) {
        if (q->left) {
            qFree(q->left);
            q->left = NULL;
        }
        if (q->right) {
            qFree(q->right);
            q->right = NULL;
        }
        free(q);
    }
}

typedef struct {
    Q* q;
    int time;
} FreqStack;


FreqStack* freqStackCreate() {
    FreqStack* s = malloc(sizeof(FreqStack));
    s->q = NULL;
    s->time = 0;
    return s;
}

void freqStackPush(FreqStack* obj, int val) {
    obj->q = qPush(obj->q, val, obj->time++);
}

int freqStackPop(FreqStack* obj) {
    int val = qDrain(obj->q);
    obj->q = qBalance(obj->q);
    return val;
}

void freqStackFree(FreqStack* obj) {
    if (obj) {
        qFree(obj->q);
        obj->q = NULL;
        free(obj);
    }
}

leetcode.895.ts

class PQ {
    public val: number
    public age: number[]
    public left: PQ | null
    public right: PQ | null
    
    constructor(val: number, age: number) {
        this.val = val;
        this.age = [age];
        this.left = null;
        this.right = null;
    }

    touch(age: number) {
        this.age.push(age);
    }

    drain(): number {
        this.age.pop();
        return this.val;
    }

    rotateLeft(): PQ {
        if (!this.right) return this;
        const right = this.right;
        this.right = right.left;
        right.left = this;
        return right;
    }

    rotateRight(): PQ {
        if (!this.left) return this;
        const left = this.left;
        this.left = left.right;
        left.right = this;
        return left;
    }

    find(val: number): PQ | null {
        if (val < this.val) {
            if (!this.left) return null
            return this.left.find(val);
        }
        if (val > this.val) {
            if (!this.right) return null
            return this.right.find(val);
        }
        return this;
    }

    insert(node: PQ): PQ {
        if (node.val < this.val) {
            if (!this.left) {
                this.left = node;
            } else {
                this.left = this.left.insert(node);
            }
            return this;
        }
        if (node.val > this.val) {
            if (!this.right) {
                this.right = node;
            } else {
                this.right = this.right.insert(node);
            }
            return this;
        }
        node.left = this;
        node.right = this.right;
        this.right = null;
        return node;
    }

    isGE(node: PQ): boolean {
        const thisLen = this.age.length;
        const nodeLen = node.age.length;
        if (thisLen > nodeLen) return true;
        const thisAge = this.age[this.age.length - 1] ?? -1;
        const nodeAge = node.age[node.age.length - 1] ?? -1;
        if (thisLen == nodeLen && thisAge > nodeAge) return true
        return false;
    }

    balance(): PQ {
        if (this.left) {
            this.left = this.left.balance();
        }
        if (this.right) {
            this.right = this.right.balance();
        }
        if (this.left && this.left.isGE(this)) {
            return this.rotateRight().balance();
        }
        if (this.right && this.right.isGE(this)) {
            return this.rotateLeft().balance();
        }
        return this;
    }
}

class FreqStack {
    private _q: PQ | null = null;
    private _age: number = 0;

    constructor() {}

    push(val: number): void {
        if (!this._q) {
            this._q = new PQ(val, this._age++);
            return;
        }
        const old = this._q.find(val);
        if (old) {
            old.touch(this._age++);
        } else {
            const node = new PQ(val, this._age++);
            this._q = this._q.insert(node);
        }
        this._q = this._q.balance();
    }

    pop(): number {
        const val = this._q.drain();
        this._q = this._q.balance();
        return val;
    }
}