代码随想录算法训练营第10天 | 232. 用栈实现队列 | 225. 用队列实现栈

232. 用栈实现队列

解

typedef struct {
    int intop, outtop;
    int instack[105], outstack[105];
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue *queue = (MyQueue *)malloc(sizeof(MyQueue));

    queue->intop = queue->outtop = -1;
    memset(queue->instack, -1, sizeof(int) * 105);
    memset(queue->outstack, -1, sizeof(int) * 105);

    return queue;
}

void myQueuePush(MyQueue* obj, int x) {
    
    while (obj->outtop >= 0) {
        obj->instack[++obj->intop] = obj->outstack[obj->outtop--];
    }
    
    obj->instack[++obj->intop] = x;
}

int myQueuePop(MyQueue* obj) {

    while (obj->intop >= 0) {
        obj->outstack[++obj->outtop] = obj->instack[obj->intop--];
    }

    return obj->outstack[obj->outtop--];
}

int myQueuePeek(MyQueue* obj) {

    while (obj->intop >= 0) {
        obj->outstack[++obj->outtop] = obj->instack[obj->intop--];
    }

    return obj->outstack[obj->outtop];
}

bool myQueueEmpty(MyQueue* obj) {
    
    while (obj->intop >= 0) {
        obj->outstack[++obj->outtop] = obj->instack[obj->intop--];
    }

    if (obj->outtop < 0) {
        return true;
    }

    return false;
}

void myQueueFree(MyQueue* obj) {
    free(obj);
}

225. 用队列实现栈

题目链接

解

用环形队列实现

const int max = 105;


typedef struct {
    int front1, back1;
    int front2, back2;
    int queue1[105], queue2[105];
} MyStack;


MyStack* myStackCreate() {
    MyStack *stack = (MyStack *)malloc(sizeof(MyStack));
    
    memset(stack->queue1, -1, sizeof(int) * max);
    stack->front1 = stack->back1 = 0;

    memset(stack->queue2, -1, sizeof(int) * max);
    stack->front2 = stack->back2 = 0;

    return stack;
}

void myStackPush(MyStack* obj, int x) {

    obj->queue1[obj->front1] = x;
    obj->front1 = (obj->front1 + 1) % max;

    return;
}

int myStackPop(MyStack* obj) {
    int ret;

    while (obj->back1 != obj->front1-1) {
        obj->queue2[obj->front2] = obj->queue1[obj->back1];
        obj->front2 = (obj->front2 + 1) % max;
        obj->back1 = (obj->back1 + 1) % max;
    }

    ret = obj->queue1[obj->back1];
    obj->back1 = (obj->back1 + 1) % max;

    while (obj->back2 != obj->front2) {
        obj->queue1[obj->front1] = obj->queue2[obj->back2];
        obj->front1 = (obj->front1 + 1) % max;
        obj->back2 = (obj->back2 + 1) % max;
    }

    return ret;
}

int myStackTop(MyStack* obj) {
    int ret;

    while (obj->back1 != obj->front1-1) {
        obj->queue2[obj->front2] = obj->queue1[obj->back1];
        obj->front2 = (obj->front2 + 1) % max;
        obj->back1 = (obj->back1 + 1) % max;
    }

    ret = obj->queue1[obj->back1];
    obj->queue2[obj->front2] = obj->queue1[obj->back1];
    obj->front2 = (obj->front2 + 1) % max;
    obj->back1 = (obj->back1 + 1) % max;

    while (obj->back2 != obj->front2) {
        obj->queue1[obj->front1] = obj->queue2[obj->back2];
        obj->front1 = (obj->front1 + 1) % max;
        obj->back2 = (obj->back2 + 1) % max;
    }

    return ret;
}

bool myStackEmpty(MyStack* obj) {
    if (obj->front1 == obj->back1) {
        return true;
    }

    return false;
}

void myStackFree(MyStack* obj) {
    free(obj);
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/