​

1. 题目描述

2. 思路分析

用两个栈实现，一个栈进行入队操作，另一个栈进行出队操作。
出队操作： 当出队的栈不为空时，直接进行出栈操作；如果为空，需要把入队的栈元素全部导入到出队的栈，然后再进行出栈操作

3. 代码实现

typedef int STDataType;
#define INIT_CAPACITY 4
typedef struct Stack
{
   
    STDataType* a;
    int top;  //栈顶
    int capacity;  //容量
}ST;

//初始化栈
void STInit(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空
bool STEmpty(ST* ps);
//销毁栈
void STDestroy(ST* ps);

void STInit(ST* ps)
{
   
    assert(ps);
    ps->a = NULL;
    ps->top = 0;
    ps->capacity = 0;
}

void STPush(ST* ps, STDataType x)
{
   
    assert(ps);
    if (ps->top == ps->capacity)
    {
   
        int newCapacity = ps->capacity == 0 ? INIT_CAPACITY : ps->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
        if (tmp == NULL)
        {
   
            perror("realloc failed");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity = newCapacity;
    }
    ps->a[ps->top] = x;
    ps->top++;
}

void STPop(ST* ps)
{
   
    assert(ps);
    //空
    assert(ps->a > 0);
    --ps->top;
}

STDataType STTop(ST* ps)
{
   
    assert(ps);
    //空
    assert(ps->a > 0);
    return ps->a[ps->top - 1];
}

int STSize(ST* ps)
{
   
    assert(ps);
    return ps->top;
}

bool STEmpty(ST* ps)
{
   
    assert(ps);
    return ps->top == 0;
}

void STDestroy(ST* ps)
{
   
    assert(ps);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}

typedef struct {
   
  ST pushst;
  ST popst;
} MyQueue;


MyQueue* myQueueCreate() {
   
  MyQueue *obj=(MyQueue*)malloc(sizeof(MyQueue));
  STInit(&obj->pushst);
  STInit(&obj->popst);
  return obj;
}

void myQueuePush(MyQueue* obj, int x) {
   
  STPush(&obj->pushst,x);
}

int myQueuePeek(MyQueue* obj) {
   
    if(STEmpty(&obj->popst))
    {
   
        //捯数据
    while(!STEmpty(&obj->pushst))
    {
   
        STPush(&obj->popst,STTop(&obj->pushst));
      STPop(&obj->pushst);
    }
  }
  return STTop(&obj->popst);
}

int myQueuePop(MyQueue* obj) {
   
    int front=myQueuePeek(obj);
    STPop(&obj->popst);
    return front;
}

bool myQueueEmpty(MyQueue* obj) {
   
    return STEmpty(&obj->popst)&&STEmpty(&obj->pushst);
}

void myQueueFree(MyQueue* obj) {
   
    STDestroy(&obj->popst);
    STDestroy(&obj->pushst);
    free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);

 * int param_2 = myQueuePop(obj);

 * int param_3 = myQueuePeek(obj);

 * bool param_4 = myQueueEmpty(obj);

 * myQueueFree(obj);
*/

​