bool isValid(char * s){
    ST st;//我们需要利用栈的结构类型创建一个栈空间出来，
    StackInit(&st);//我们的初始化接口会自动帮我们给数组开辟好空间，直接调用接口就好了，非常的方便
    while(*s)//这里开始遍历整个字符数组，遇到'\0'遍历完毕，跳出循环
    {
        if(*s=='('||*s=='{'||*s=='[')//只要遇到左括号我们就压栈
        {
            StackPush(&st,*s);
            s++;
        }
        else
        {
            if(StackEmpty(&st))//这里是为了避免数组里只有右括号的情形
            {//如果只有右括号的话，程序不用继续运行了，直接销毁栈空间返回false就可以了
                StackDestroy(&st);
                return false;
            }
            char top=StackTop(&st);//保存栈顶数据，方便后面和左括号进行比较
            StackPop(&st);//保存完之后我们就得比较接下来的括号了，所以更新一下栈顶数据，将原来的栈顶数据pop掉
            //下面进行左括号和右括号的比较
            if((top=='{'&&*s!='}')||(top=='('&&*s!=')')||(top=='['&&*s!=']'))
                return false;//如果不相等直接返回false，
            else
                s++;//相等就继续向后遍历字符数组，进行下一次的比较
        }
    }
    //运行到这里，栈的空间必须变为空，如果不为空，说明栈中还有左括号未出
    bool ret=StackEmpty(&st);
    StackDestroy(&st);
    return ret;//若为空，返回true，若不为空，返回false
}

typedef struct {
    Queue q1;//我们在栈的结构里定义两个队列
    Queue q2;
} MyStack;
MyStack* myStackCreate() {
//这个接口是我们栈空间的创建，所以需要malloc一块空间作为栈的地址，然后调用队列初始化接口将栈里面的两个队列进行初始化，
//最后我们返回栈空间的地址，以便测试模块儿中对栈的各个接口进行实现。
    MyStack*st=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}
void myStackPush(MyStack* obj, int x) {
//这个模块儿是压栈,因为我们后面的出栈等会对两个队列进行频繁的换值，但肯定会有一个队列是不为空的，
//我们压栈操作一定是往非空队列中压栈的，两个队列都有可能是非空，所以我们这里分支处理了一下
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}
int myStackPop(MyStack* obj) {
//由于我们的pop操作一定是将非空队列中除尾数据的其他数据入队列到空队列当中，
//所以我们先假设定义了一个非空和空的队列，这样做可以让代码的命名风格更好一些。
    Queue* emptyQ=&obj->q1;//注意这里是栈结构中的队列1，你直接搞个q1，疯球了你妹的。
    Queue* nonemptyQ=&obj->q2;
    if(!QueueEmpty(&obj->q1))//假设错了，我们重新赋值一下
    {
        emptyQ=&obj->q2;//注意这里是栈结构中的队列1，你直接搞个q1，疯球了你妹的。
        nonemptyQ=&obj->q1;
    }
    int w=QueueSize(nonemptyQ);
    while(--w)//什么时候就转移元素停止了？因为要留一个尾数据，所以我们的循环次数比数据个数少1
    {
       QDataType top= QueueFront(nonemptyQ);
       QueuePush(emptyQ,top);
       QueuePop(nonemptyQ);
    }
    QDataType i=QueueFront(nonemptyQ);
    QueuePop(nonemptyQ);
    return i;
}
int myStackTop(MyStack* obj) {
//这个接口是取栈顶数据，这个也比较简单，通过我们对队列结构的清晰认识，我们可知队尾数据即为栈顶数据。
//所以我们找出非空队列，将队尾数据返回即可，其他什么都不用做。
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}
bool myStackEmpty(MyStack* obj) {
//这个接口是判断栈是否为空的接口，当两个队列均为空时，便可以说明我们的栈也为空了。
//这里我们利用逻辑表达式的特点，将逻辑表达式的结果进行返回
//两个队列都为空，逻辑为真，返回true，只要有一个不为空，逻辑为假，返回false。
    return QueueSize(&obj->q1)==0&&QueueSize(&obj->q2)==0;
}
void myStackFree(MyStack* obj) {
//这个接口是栈空间的销毁，我们要看一看我们都malloc了哪些空间，销毁应该将我们申请的空间全还给操作系统
//否则就会出现内存泄露的问题。
//我们每一次的push，队列都会向操作系统申请空间，所以我们先得把两个队列的空间销毁掉，
//然后再把我们开辟的栈空间销毁掉，因为我们对栈初始化时，是malloc了一个栈空间的，所以要free。
//对队列空间销毁，我们直接调用队列接口就可实现。
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

typedef int STDataType;
typedef struct Stack
{
  STDataType* array;
  int top;//这代表我们栈顶的位置，top会随着栈空间数据的扩大随之变换
  int capacity;
}ST;
void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);
STDataType StackTop(ST* ps);//取栈顶的数据
int StackSize(ST* ps);
bool StackEmpty(ST* ps);
void StackInit(ST* ps)
{
  assert(ps);
  ps->array = NULL;
  ps->top = 0;//ps->top = -1; 我们的top也是可以给-1的
  ps->capacity = 0; 
  //初始化时，top给的是0，意味着top指向栈顶数据的下一个
//我们的top指向的是最后栈顶数据的下一个，因为我们是先插入数据到下标为top的位置，然后top再++
  //初始化时，top给的是-1，意味着top指向栈顶数据
//我们的top指向的是栈顶数据，因为我们要先将top+1，然后再往此时的top位置放数据，下一次也是先将top位置+1再放数据
//这是一个什么问题呢？(就是)是先放数据再移动top呢？还是先移动top再放数据呢？
}
void StackDestroy(ST* ps)
{
  assert(ps);
  free(ps->array);
  ps->array = NULL;
  ps->capacity = ps->top = 0;
}
void StackPush(ST* ps, STDataType x)//将元素进行入栈
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    STDataType* tmp = (STDataType*)realloc(ps->array, sizeof(STDataType) * newCapacity);
    if (tmp == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
    ps->array = tmp;
    ps->capacity = newCapacity;
  }
  ps->array[ps->top] = x; 
  ps->top++;
}
void StackPop(ST* ps)//将元素进行出栈，删除数据
{
  assert(ps);
  assert(!StackEmpty(ps));//top为0的时候是不能进行删除的
  ps->top--;
}
STDataType StackTop(ST* ps)//取栈顶的数据
{
  assert(ps);
  assert(!StackEmpty(ps));//如果栈为空，就会报错
  //我们的栈必须得有数据你才能取数据啊，如果没有数据你还取数据的话，就是访问下标-1的数据了，造成越界访问
  return ps->array[ps->top - 1];
}
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;//top指向的是栈顶数据的下一个位置，又因为它从0开始增大，所以top的值正好就是栈数据的个数
}
bool StackEmpty(ST* ps)
{
  assert(ps);
  /*if (ps->top > 0)
  {
    return false;
  }
  else
  {
    return true;
  }*/
  return ps->top == 0;//这里的判断条件的正确与否，正好就对应上我们返回的是逻辑真还是逻辑假。true or false
}

typedef struct {
    ST st1;//在这里提前说明一点，st1是用来push数据的，st2是为了模仿队列出数据的。
    //只要入数据，我们直接入到st1里面，出数据时，将数据出栈到st2里，在出st2里的数据。
    ST st2;
} MyQueue;
MyQueue* myQueueCreate() {
    MyQueue*queue=(MyQueue*)malloc(sizeof(MyQueue));
    //动态申请一个队列的空间后续通过队列空间的地址，实现队列的各个接口
    StackInit(&queue->st1);//将队列中两个栈进行初始化，为各个栈malloc好初始化的空间大小。
    StackInit(&queue->st2);
    return queue;//返回malloc好的队列地址
}
void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->st1,x);//只要入队列的数据，我们都入到st1里边
}
int myQueuePop(MyQueue* obj) {
//值得注意的是只要我们的st2中有数据，我们直接出栈st2的元素即可，如果没有，我们才会将st1中的数据出栈再压栈到st2里，所以第一件事情就是判断st2是否为空。
    if(StackEmpty(&obj->st2))
    {
        while(StackSize(&obj->st1)>0)//如果为空我们将st1中的数据挪动到st2里
      {
          STDataType top=StackTop(&obj->st1);
          StackPush(&obj->st2,top);
          StackPop(&obj->st1);
      }
    }
    STDataType i=StackTop(&obj->st2);//保存一下st2的栈顶元素，等会儿将他返回
    StackPop(&obj->st2);//直接出栈st2中的数据，和出队列数据一样了就。
    return i;
}
int myQueuePeek(MyQueue* obj) {
//返回队头数据，我们也得返回st2的栈顶数据，所以这个接口和上面出队列的接口甚是相似
//第一件事就是判断st2中的数据是否为空，如果为空，我们就得赶紧将st1中的数据挪到st2里
//如果不为空，直接返回st2的栈顶数据即可，利用我们的StackTop接口
    if(StackEmpty(&obj->st2))//只要st2是空的，我们就赶紧得将st1中的数据压栈到st2里边
    {
        while(StackSize(&obj->st1)>0)
        {
            STDataType top=StackTop(&obj->st1);
            StackPush(&obj->st2,top);
            StackPop(&obj->st1);
        }
    }
    return StackTop(&obj->st2);
}
bool myQueueEmpty(MyQueue* obj) {
//当我们的两个栈均为空时，队列才会为空，所以这里利用逻辑表达式的结果返回
    return StackEmpty(&obj->st1)&&StackEmpty(&obj->st2);
    //两个栈都为空，逻辑判断为真，返回true，只要有一个栈不为空，逻辑判断为假，返回false。
}
void myQueueFree(MyQueue* obj) {
//我们队列的空间和两个栈的空间都是malloc出来的，但我们得分先后顺序进行释放空间
    StackDestroy(&obj->st1);
    //我们栈中的接口都用栈地址作为接口参数，所以我们要取队列中栈空间的地址，
    //将地址传回栈的接口，接口用指针来作为参数接收，好对栈结构进行修改。
    StackDestroy(&obj->st2);
    free(obj);
}

typedef struct {
    int*array;
    int front;
    int tail;
    int k;//环形队列的有效长度
} MyCircularQueue;
 bool myCircularQueueIsFull(MyCircularQueue* obj);
 bool myCircularQueueIsEmpty(MyCircularQueue* obj);
MyCircularQueue* myCircularQueueCreate(int k) {
//我们malloc一个循环队列的空间出来，并且将队列内容进行初始化
    MyCircularQueue*cq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    cq->array=NULL;
    cq->front=cq->tail=0;
    cq->k=k;
    cq->array=(int*)malloc(sizeof(int)*(k+1));
    //我们开辟的空间要比循环队列的有效空间多一个，否则空间满和空的情况会是一样的
    return cq;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
        //入队列之前，需要判断队列空间是不是满了，如果满了，增加数据失败。
    }
    obj->array[obj->tail]=value;//直接在下标为tail的位置插入数据
    obj->tail++;
    obj->tail=(obj->tail)%(obj->k+1);//要保证我们的下标在有效数据个数里
    return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;//同样的，删除数据时我们也要判断队列是否为空
    }
    obj->front++;//删除数据就比较简单了，只要前面的下标++，我们就无法访问到头部数据了，也就是出队列操作。从队头出嘛。
    obj->front=(obj->front)%(obj->k+1);//保证我们的下标在有效数据个数里面
    return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->array[obj->front];//直接返回Front下标位置的数据就可以了
}
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    //这个获取队尾数据的接口，大家一定要小心啊，这里是有两种情况的
    //队列恰好满，和队列没满这两种情况是不一样的，我们返回的元素位置也不同
    if(obj->tail==0)//这里有两种情况，一定要小心呐
    {
        return obj->array[obj->k];
    }
    else
    {
        return obj->array[obj->tail-1];
    }
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->tail;//front==tail时，队列为空
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1)%(obj->k+1)==obj->front;
    //tail的下一个位置若是front，说明队列已满
}
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->array);//释放动态数组的空间
    free(obj);//释放初始化时，开辟的循环队列空间
}