​225.用队列实现栈--Leetcode

​225.用队列实现栈

​225.用队列实现栈

题目分析

其实这个题目和昨天232类似，并且解题思路和232一模一样。我就不过多描述了。
我的思路就是在入队时，将新压栈的数，压入最下层。操作就是将原有队列(Q1)先翻转到(Q2)中，再将新压栈的数入队，再将Q2中的数翻转到Q1。
如官方示意图所示

官方解释

代码实现

#define MAXSIZE 128
struct queue
{
    int val[MAXSIZE];
    int front;
    int rear;
};
typedef struct
{
    struct queue Q1;
    struct queue Q2;
} MyStack;
​
MyStack* myStackCreate()
{
    MyStack *S = (MyStack *)malloc(sizeof(MyStack));
    S->Q1.front = -1;
    S->Q1.rear = -1;
    S->Q2.front = -1;
    S->Q2.rear = -1;
    return S;
}
void myStackPush(MyStack* obj, int x)
{
    if(obj->Q1.rear>=MAXSIZE-1)
        return ;
    if(obj->Q1.front==-1)
    {
        obj->Q1.val[++obj->Q1.front]=x;
        obj->Q1.rear++;
        return ;
    }
    while(obj->Q1.front <= obj->Q1.rear)
    {
        obj->Q2.val[++obj->Q2.rear]=obj->Q1.val[obj->Q1.front++];
    }
    obj->Q2.front++;
    obj->Q1.front=-1;
    obj->Q1.val[++obj->Q1.front]=x;
    obj->Q1.rear = obj->Q1.front;
    while(obj->Q2.front <= obj->Q2.rear)
    {
        obj->Q1.val[++obj->Q1.rear]=obj->Q2.val[obj->Q2.front++];
    }
    obj->Q2.front=-1;
    obj->Q2.rear=-1;
}
​
int myStackPop(MyStack* obj)
{
    return obj->Q1.val[obj->Q1.front++];
}
​
int myStackTop(MyStack* obj)
{
    return obj->Q1.val[obj->Q1.front];
}
​
bool myStackEmpty(MyStack* obj)
{
    if(obj->Q1.front==-1 || obj->Q1.front > obj->Q1.rear)
        return true;
    return false;
}
​
void myStackFree(MyStack* obj)
{
    free(obj);
}

在代码实现中，我出现两个问题。

1.第一个问题: 在压栈时，Q1，Q2队列的头指针和尾指针都需要初始化。在下有点愚笨，不知道该如何优化代码。2.第二个问题：在判断队列是否为空时，不只是头指针为-1，还有一个条件是头指针大于尾指针。

复杂度分析

函数	时间复杂度	空间复杂度
压栈	O(n)	O(1)
出栈	O(1)	O(1)
判断空	O(1)	O(1)
取栈顶元素	O(1)	O(1)