一、括号匹配问题
1、题目要求：
2、大体思路
遍历这个字符串，如果是左括号就让它入栈，如果是右括号就让它和栈顶元素进行匹配（前提是栈中有元素），匹配成功的话就让栈顶元素出栈，匹配失败就返回false，直到遍历完字符串，如果遍历完了栈中没有元素，则返回true。
3、代码实现
bool isValid(char * s){Stack stack;StackInit(&stack);//初始化int i = 0;while(s[i] != '\0'){//入栈if(s[i] == '{' || s[i] == '[' || s[i] == '('){StackPush(&stack,s[i]);}else{//栈为空时if(StackEmpty(&stack)){StackDestroy(&stack); //销毁栈return false;}if((StackTop(&stack) == '(' && s[i] == ')') ||(StackTop(&stack) == '{' && s[i] == '}') ||(StackTop(&stack) == '[' && s[i] == ']')){ StackPop(&stack); //匹配的话出栈}else{//不匹配StackDestroy(&stack);return false;}}i++;}//遍历完后栈为空if(StackEmpty(&stack)){StackDestroy(&stack);return true;}StackDestroy(&stack);return false;}
二、用队列实现栈
1、题目要求：
2、大体思路
用两个队列q1和q2来实现，要实现入栈的话可以选不为空的队列进行入队列操作（开始两个队列都可以），假设现在元素都在q1中，要实现出栈的话把q1中的元素放入q2中，直到q1中剩一个一个元素，在让它出队列。
3、代码实现
//用两个队列实现栈typedef struct {Queue q1;Queue q2;} MyStack;MyStack* myStackCreate() {MyStack* ms = (MyStack*)malloc(sizeof(MyStack));if(ms == NULL){return NULL;}QueueInit(&ms->q1);QueueInit(&ms->q2);return ms;}void myStackPush(MyStack* obj, int x) {//给不为空的队列加入元素，模拟入栈if(QueueEmpty(&obj->q1) ){QueuePush(&obj->q2,x);}else{QueuePush(&obj->q1,x);}}int myStackPop(MyStack* obj) {//当q1为空时，把q2中的元素放入q1中直到q2中只剩一个元素，然后q2再出队列，模拟出栈int ret = 0;if(QueueEmpty(&obj->q1)){while(QueueSize(&obj->q2) != 1){QueuePush(&obj->q1,QueueFront(&obj->q2));QueuePop(&obj->q2);}ret = QueueFront(&obj->q2);QueuePop(&obj->q2);}else{while(QueueSize(&obj->q1) != 1){QueuePush(&obj->q2,QueueFront(&obj->q1));QueuePop(&obj->q1);}ret = QueueFront(&obj->q1);QueuePop(&obj->q1);}return ret;}//栈顶元素相当于是队尾元素int myStackTop(MyStack* obj) {if(QueueEmpty(&obj->q1)){return QueueBack(&obj->q2);}else{return QueueBack(&obj->q1);}}bool myStackEmpty(MyStack* obj) {if(QueueSize(&obj->q1) == 0 && QueueSize(&obj->q2) == 0){return true;}return false;}void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);}
三、用栈实现队列
1、题目要求
2、大体思路
用两个栈s1和s2来实现，s1用来模拟入队列，s2用来模拟出队列。实现入队列就直接对s1进行入栈操作；出队列的话，先判断s2中是否有元素，如果没有则把s1中的元素放入s2中，然后再对s2进行出栈操作。
3、代码实现
typedef struct {//s1用来入队列，s2用来出队列Stack s1; Stack s2;} MyQueue;MyQueue* myQueueCreate() {MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));if(q == NULL){return NULL;}StackInit(&q->s1);StackInit(&q->s2);return q;}//入队列void myQueuePush(MyQueue* obj, int x) {StackPush(&obj->s1,x);}//出队列int myQueuePop(MyQueue* obj) {//s2不为空的话先把s1中的元素搬移到s2中if(StackEmpty(&obj->s2)){while(!StackEmpty(&obj->s1)){StackPush(&obj->s2,StackTop(&obj->s1));StackPop(&obj->s1);}}int ret = StackTop(&obj->s2);StackPop(&obj->s2);return ret;}//返回对头元素，和出队列差不多int myQueuePeek(MyQueue* obj) {if(StackEmpty(&obj->s2)){while(!StackEmpty(&obj->s1)){StackPush(&obj->s2,StackTop(&obj->s1));StackPop(&obj->s1);}}return StackTop(&obj->s2);}bool myQueueEmpty(MyQueue* obj) {if(StackEmpty(&obj->s1) && StackEmpty(&obj->s2)){return true;}return false;}void myQueueFree(MyQueue* obj) {if(obj != NULL){StackDestroy(&obj->s1);StackDestroy(&obj->s2);free(obj);}}
四、设计一个循环队列
1、题目要求
2、大体思路
循环队列是用顺序结构存储的。用两个指针来标记对头和队尾，如图：
但这样会有一个问题，就是在队列为空和队列满了的情况下，rear和front都重合了，这样就不能判断是队列满了还是队列为空。解决这个问题有三种方法：
方法一：我们可以少用一个存储空间，如图所示，这样就代表队列已经满了。
方法二：用一个flag进行标记，开始设为0，插入元素时将flag设为1，删除元素时设为0；这样当front等于rear时，判断一下flag就行了。
方法三：使用一个count进行计数，只有count为零时队列为空。
3、代码实现
这里用的是方法三
typedef struct {int* array;//存储数据int front; //对头int rear; //队尾int count; //计数int N; //队列容量} MyCircularQueue;//初始化MyCircularQueue* myCircularQueueCreate(int k) {//先给队列申请空间MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(q == NULL ){return NULL;}//再给队列里的数组申请空间q->array = (int*)malloc(sizeof(int) * k);if(q->array == NULL){//如果失败，要先释放队列的空间，注意代码的严谨性free(q);return NULL;}q->front = q->rear = q->count = 0;q->N = k;return q;}//判断队列是否为空bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return 0 == obj->count;}//判断队列是否满了bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->count == obj->N;}//入队列bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}obj->array[obj->rear] = value;if(obj->rear == obj->N - 1){obj->rear = 0;}else{obj->rear++;}obj->count++;return true;}//出队列bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}if(obj->front == obj->N - 1){obj->front = 0;}else{obj->front++;}obj->count--;return true;}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->array[obj->front];}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}//注意获取队尾元素的计算方法return obj->array[(obj->rear - 1 + obj->N) % obj->N];}//释放空间void myCircularQueueFree(MyCircularQueue* obj) {if(obj){if(obj->array){free(obj->array);}free(obj);nhj }}
