前情提要：
本次OJ题需要能够独立实现栈和队列，如果对栈和队列还不熟悉可以参考一下：栈和队列(C语言版)-CSDN博客
一、循环队列
1.题目
2.循环队列的概念
循环队列也是一种线性的数据结构，其操作表现基于先进先出的特性，队尾与队头相连接形成一个回环，被称为“环形缓冲器”。
3.循环队列的结构选取
我们在实现循环队列的时候应尽量运用连续的空间，把数据存储起来，这样我们可以大大提高空间的利用率，因此我们采用数组为底层结构，这样我们通过两个变量来控制队头和队尾的操作。
4.循环队列的注意事项
3.1有了循环队列的结构我们又会发现，因为循环队列是循环利用的，所以当判空和判满的情况相同，这样就会产生歧义，那么这样我们应该如何区分呢？
这时候我们可以给数组额外增加一个存储空间，当尾+1 == 头的时候为队列满的1状态，当尾 == 头的时候队列就是空的状态，这样我们的问题就得到了完美的解决。
3.2我们应该如何来控制维护变量的指针在循环队列中循环遍历起来呢？
我们给出下面两个公式：
（尾+1）% 空间大小
（头+1）% 空间大小
5.循环队列的实现思路及其代码
5.1结构的定义
typedef struct
{int* arr;int front;int rear;int capacity;
} MyCircularQueue;5.2循环队列初始化
先给循环队列的方法先申请一块空间，然后给循环队列开辟空间，并让arr指向那片空间(需要额外多开辟一块空间为判满做铺垫)，然后将存储空间变量的大小设置为队列可以存储的元素个数，其余全部置为0。
MyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue* tmp = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));tmp->arr = (int*)malloc(sizeof(int)*(k+1));tmp -> front = tmp->rear = 0;tmp->capacity = k;return tmp;
}5.3判满
队尾的下一个元素为队头，该队列为满。
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear + 1)%(obj->capacity+1) == obj->front;
}5.4入队
如果队列没满，则直接将数据插入到队尾然后维护队尾下标的变量，走向下一个有效下标。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{if(myCircularQueueIsFull(obj)){return false;}obj->arr[obj->rear++] = value;obj->rear %= obj->capacity + 1;return true;
}5.5判空
当队头等于队尾的时候，队列就为空。
//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{return obj->rear == obj->front;
}5.6删除数据
如果队列不为空，将头的指针指向下一个有效下标。
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}obj->front++;obj->front %= obj->capacity + 1;return true;
}5.7取队头数据
返回以维护队头变量为下标的元素值。
int myCircularQueueFront(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj)){return -1;}return obj->arr[obj->front];
}5.8取队尾数据
返回维护队尾前一个有效数据下标的元素值。
int myCircularQueueRear(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj)){return -1;}int tmp = obj->rear-1;if(tmp < 0){tmp = obj->capacity;}return obj->arr[tmp];
}5.9销毁队列
申请的空间和循环队列实现方法，全部释放，且置为空。
void myCircularQueueFree(MyCircularQueue* obj)
{free(obj->arr);obj->arr = NULL;free(obj);obj = NULL;
}二、用队列实现栈
1.题目
2.实现思路
2.1定义方法
首先定义一个结构体方法，方法里面定义两个队列，通过两个栈来回倒数据来模拟栈的操作
typedef struct {Queue p1;Queue p2;
} MyStack;2.2模拟栈的初始化操作
将结构体方法里面存储两个队列，利用以前队列实现的功能接口，将两个创建的新队列初始化，即可完成模拟栈的初始化。
//初始化
MyStack* myStackCreate() {MyStack* tmp = (MyStack*)malloc(sizeof(MyStack));QueueInit(&tmp->p1);QueueInit(&tmp->p2);return tmp;
}2.3模拟入栈数据的操作
找到两个队列中为空的队列然后将要插入的数据插入到空队列中。
void myStackPush(MyStack* obj, int x)
{Queue* null = &obj -> p1;Queue* fnull = &obj -> p2;if(QueueEmpty(fnull)){null = &obj -> p2;fnull = &obj -> p1;}QueuePush(fnull,x);
}2.4模拟出栈数据的操作
先找到两个队列中的非空队列将非空队列n-1个数据插入到空队列中，然后取出非空队列中仅剩的唯一数据并将它删除。
int myStackPop(MyStack* obj)
{Queue* null = &obj -> p1;Queue* fnull = &obj -> p2;if(QueueEmpty(fnull)){null = &obj -> p2;fnull = &obj -> p1;}while(QueueSize(fnull) > 1){QueuePush(null,QueueFront(fnull));QueuePop(fnull);}int ret = QueueFront(fnull);QueuePop(fnull);return ret;
}2.5模拟返回栈顶元素操作
找到两个队列中的非空队列，然后取队尾的数据。
int myStackTop(MyStack* obj)
{if(QueueEmpty(&obj->p1)){return QueueBack(&obj->p2);}else{return QueueBack(&obj->p1);}
}2.6模拟栈判空的操作
看两个队列是否为空如果都为空则代表栈为空否则栈不为空。
bool myStackEmpty(MyStack* obj)
{return QueueEmpty(&obj->p1) && QueueEmpty(&obj->p2);
}2.7模拟栈销毁的操作
将创建的两个栈手动销毁，然后将模拟栈的方法的容器手动销毁并置空。
void myStackFree(MyStack* obj)
{QueueDestory(&obj->p1);QueueDestory(&obj->p2);free(obj);obj == NULL;
}三、栈实现队列
1.题目
2.代码
2.1定义方法
首先常见一个模拟队列结构体方法创建两个栈，一个入数据一个出数据，来模拟队列的实现。
typedef struct
{ST PushStack;ST PopStack;} MyQueue;2.2模拟队列初始化
首先申请模拟队列的空间，然后利用以前实现栈的功能接口，将两个新的栈初始化，即可完成模拟栈的初始化操作。
MyQueue* myQueueCreate()
{MyQueue* tmp = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&tmp->PushStack);StackInit(&tmp->PopStack);return tmp;
}2.3模拟入队的操作
将需要插入的数据插入到入数据的栈中。
void myQueuePush(MyQueue* obj, int x)
{StackPush(obj->pushST,x);
}2.4模拟出队的操作
首先判断需要出数据的栈是否为空，如果为空，就将入数据的栈中的数据全部导入到，出数据的栈中，然后再出数据，如果出数据的栈不为空就直接将数据出栈。
int myQueuePop(MyQueue* obj)
{if(StackEmpty(&obj->PopStack)){while(StackSize(&obj->PushStack) > 0){StackPush(&obj->PopStack,StackFront(&obj->PushStack));StackPop(&obj->PushStack);}}int ret = StackFront(&obj->PopStack);StackPop(&obj->PopStack);return ret;
}2.5模拟取队头数据
与出队的方法相似，先判断出数据的栈中是否存在数据，如果有直接返回数据，如果没有就先导入数据然后再返回数据。
int myQueuePeek(MyQueue* obj)
{if(StackEmpty(&obj->PopStack)){while(StackSize(&obj->PushStack) > 0){StackPush(&obj->PopStack,StackFront(&obj->PushStack));StackPop(&obj->PushStack);}}return StackFront(&obj->PopStack);
}2.6模拟队列的判空
看两个栈是否都为空，如果都为空则证明队列为空，否则队列不为空。
bool myQueueEmpty(MyQueue* obj)
{return StackEmpty(&obj->PopStack) && StackEmpty(&obj->PushStack);
}2.7模拟队列的销毁
将两个栈销毁，并将模拟的方法销毁，且置为空。
void myQueueFree(MyQueue* obj)
{StackDestory(&obj->PopStack);StackDestory(&obj->PushStack);free(obj);obj = NULL;
}四、有效括号的匹配问题
1.题目
2.代码
首先遍历字符串，如果是左括号则入栈，如果是右括号则出栈一个栈的数据与该又括号是否匹配，如果匹配则继续遍历，否则返回失败。当字符串遍历完成后，如果栈为空则返回真，否则返回假，如果第一个为右括号则直接返回假，注意返回前要销毁栈养成一个良好的习惯。
bool isValid(char* s)
{ST SL;STInit(&SL);while(*s != '\0'){if(*s == '(' || *s == '{' || *s == '['){StackPush(&SL,*s);}else{if(!StackEmpty(&SL)){STDestory(&SL);return false;}char ch = StackFront(&SL);if((ch == '{' && *s == '}') ||(ch == '[' && *s == ']') ||(ch == '(' && *s == ')')){StackPop(&SL);}else{STDestory(&SL);return false;}}s++;}if(StackEmpty(&SL)){STDestory(&SL);return false;}STDestory(&SL);return true;
}
