有效的括号
题目链接：力扣（LeetCode）
思路：这道题可以用栈来解决，先让字符串中的左括号' ( '，' [ '，' { '入栈，s指向字符串下一个字符，如果该字符也是左括号，那就继续入栈，如果是右括号，那就让其与栈顶元素相匹配（每次都要弹出栈顶元素），匹配上了，继续循环，匹配不上就返回false，注意在每次返回false之前都要销毁栈。
还要考虑极端情况，如果全是左括号，我们要在代码最后进行判空，不为空，返回false，同时，这次判空也能解决前面几对都匹配上，只有最后一个左括号没匹配上的问题（例如："()[]{}{"）。
如果全是右括号，说明整个过程中没有入栈元素，此时判空，如果为空返回false，同时，这次判空也能解决前面几对都匹配上，只有最后一个右括号没匹配上的问题（例如："()[]{}}"）。
如果用C语言来解题的话，栈需要自己写。
代码如下：
typedef int STDatatype; typedef struct Stack { STDatatype* a; int top; int capacity; }ST; //初始化栈 void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->top = 0; pst->capacity = 0; } //入栈 void STPush(ST* pst, STDatatype x) { //开辟空间 if (pst->top == pst->capacity) { int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDatatype) * newcapacity); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newcapacity; } //插入 pst->a[pst->top] = x; pst->top++; } //判空函数 bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; } //出栈 void STPop(ST* pst) { assert(pst); assert(!STEmpty(pst)); pst->top--; } //获取栈顶元素 STDatatype STTop(ST* pst) { assert(pst); assert(!STEmpty(pst)); return pst->a[pst->top - 1]; } //获取栈中有效数据的个数 int STSize(ST* pst) { assert(pst); return pst->top; } //销毁栈 void STDestory(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->top = pst->capacity = 0; } bool isValid(char* s) { ST st; STInit(&st); while(*s) { if(*s=='('||*s=='['||*s=='{') { STPush(&st,*s); } else { if(STEmpty(&st)) { STDestory(&st); return false; } char top=STTop(&st); STPop(&st); if((top!='('&&*s==')') ||(top!='['&&*s==']') ||(top!='{'&&*s=='}')) { STDestory(&st); return false; } } ++s; } bool ret=STEmpty(&st); STDestory(&st); return ret; }
用队列实现栈
题目链接：力扣（LeetCode）
思路：队列是先入先出，栈是先入后出，要用队列实现栈，我们可以定义两个栈q1和q2，当它们都为空时，随便选一个存入数据，假设q1中有数据1 2 3 4，我们可以把q1中的1 2 3 push进q2中，然后把q1中的4pop出去，接着把q2中的1 2 push进q1，然后把q2中的3pop出去，这样循环在q1和q2中倒数据，就实现了4 3 2 1依次出栈，即先入后出。
当我们在出栈的同时，想要入栈，就把数据push进有数据的队列即可。
想要用C语言做这道题，队列的实现代码也要自己写。
注意，我们下列代码是结构体的三层嵌套，所以销毁时要先销毁q1和q2，再销毁obj，如果只销毁obj，由于我们的队列q1和q2中分别有两个头尾指针还有节点，会造成内存泄漏的问题。
它们的关系图如下：
代码如下：
typedef int QDatatype; typedef struct QueueNode { struct QueueNode* next; QDatatype data; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; //初始化队列 void QueueInit(Queue* pq) { pq->phead = NULL; pq->ptail = NULL; pq->size = 0; } //队尾入队列 void QueuePush(Queue* pq, QDatatype x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; if (pq->ptail == NULL) { assert(pq->phead == NULL); pq->phead = pq->ptail=newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } //判空函数 bool QueueEmpty(Queue* pq) { assert(pq); return pq->size ==0 ; } //队头出队列 void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); //一个节点 //多个节点 if (pq->phead->next == NULL) { free(pq->phead); pq->phead = pq->ptail= NULL; } else { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; } //获取队列头部元素 QDatatype QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->phead->data; } //获取队列尾部元素 QDatatype QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->ptail->data; } //获取队列中有效元素个数 int Queuesize(Queue* pq) { assert(pq); return pq->size; } //销毁队列 void DestoryQueue(Queue* pq) { assert(pq); while (pq->phead) { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->phead = pq->ptail = NULL; pq->size = 0; } typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* obj=(MyStack*)malloc(sizeof(MyStack)); if(obj==NULL) { perror("malloc fail"); return NULL; } QueueInit(&obj->q1); QueueInit(&obj->q2); return obj; } void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x); } else { QueuePush(&obj->q2,x); } } int myStackPop(MyStack* obj) { Queue* pemptyq=&obj->q1; Queue* pnoemptyq=&obj->q2; if(!QueueEmpty(&obj->q1)) { pemptyq=&obj->q2; pnoemptyq=&obj->q1; } while(Queuesize(pnoemptyq)>1) { QueuePush(pemptyq,QueueFront(pnoemptyq)); QueuePop(pnoemptyq); } int top=QueueFront(pnoemptyq); QueuePop(pnoemptyq); return top; } int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->q1)) return QueueBack(&obj->q1); else return QueueBack(&obj->q2); } bool myStackEmpty(MyStack* obj) { assert(obj); return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { DestoryQueue(&obj->q1); DestoryQueue(&obj->q2); free(obj); }
用栈实现队列
题目链接：力扣（LeetCode）
思路：这道题用上道题的思路也能实现，但是过于复杂。
简单思路：我们定义两个栈pushst和popst，栈中数据遵循先入后出的原则，如果在pushst中push进去1 2 3 4，那他从栈顶到栈底依次是 4 3 2 1 ，但是如果我们把pushst中的数据再push进popst中，那popst中从栈顶到栈底依次是 1 2 3 4，此时我们只要将popst中的数据按照栈本身先入后出的原则pop出去，就是1 2 3 4，这样就实现了先入先出。如下图：
当我们在出队列的同时，想要入队列，要先等popst中的数据出完才行，所以当popst为空，pushst不为空时，才能把pushst中的数据往popst中push。
代码如下：
typedef int STDatatype; typedef struct Stack { STDatatype* a; int top; int capacity; }ST; //初始化栈 void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->top = 0; pst->capacity = 0; } //入栈 void STPush(ST* pst, STDatatype x) { //开辟空间 if (pst->top == pst->capacity) { int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDatatype) * newcapacity); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newcapacity; } //插入 pst->a[pst->top] = x; pst->top++; } //判空函数 bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; } //出栈 void STPop(ST* pst) { assert(pst); assert(!STEmpty(pst)); pst->top--; } //获取栈顶元素 STDatatype STTop(ST* pst) { assert(pst); assert(!STEmpty(pst)); return pst->a[pst->top - 1]; } //获取栈中有效数据的个数 int STSize(ST* pst) { assert(pst); return pst->top; } //销毁栈 void STDestory(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->top = pst->capacity = 0; } typedef struct { ST pushst; ST popst; } MyQueue; MyQueue* myQueueCreate() { MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue)); if(obj==NULL) { perror("malloc fail\n"); return NULL; } STInit(&obj->pushst); STInit(&obj->popst); return obj; } void myQueuePush(MyQueue* obj, int x) { STPush(&obj->pushst,x); } int myQueuePop(MyQueue* obj) { int front= myQueuePeek(obj); STPop(&obj->popst); return front; } 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); } bool myQueueEmpty(MyQueue* obj) { assert(obj); return STEmpty(&obj->pushst)&&STEmpty(&obj->popst); } void myQueueFree(MyQueue* obj) { STDestory(&obj->pushst); STDestory(&obj->popst); free(obj); }
设计循环队列
题目链接：力扣（LeetCode）
思路： 本题用数组队列和链表队列都能实现，在这里我们使用数组队列，首先，要设计一个循环队列，我们就要知道队列什么时候满，什么时候空，空很容易判断，当front=rear时就为空，问题是当我们循环一圈以后，队列已经满了，但此时front也等于rear，所以为了不发生混淆，我们在开辟空间时多开辟一块，假设要存7个数据就开辟8个空间：
此时当rear+1==front时就为满。但这只是上图为了形象展示，实际上在数组中，每存一个数，rear++，但是数组首尾并没有相连，不能用rear+1==front判断是否满了，我们可以用下标rear，当(rear+1)%(k+1)==front时就说明队列满了。
而要在队列中插入数据，每次插入之后下标rear++，但是当队列满了之后，rear就是数组中最后一个下标，这时如果我们在队头出了两个数据，想再往队列里插数据，就要让rear回到开始的位置，所以每次rear++后，让rear=rear%(k+1)，此时再插入，就形成了一个完美的循环，同理，删除数据也一样，每次删完都让front=front%(k+1)。
obj->a[(obj->rear+obj->k)%(obj->k+1)]这段代码是为了返回队尾元素。
代码如下：
typedef struct { int front; int rear; int k; int*a; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->a=(int*)malloc(sizeof(int)*(k+1)); obj->front=obj->rear=0; obj->k=k; return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front==obj->rear; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->rear+1)%(obj->k+1)==obj->front; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if( myCircularQueueIsFull(obj)) return false; obj->a[obj->rear]=value; obj->rear++; obj->rear=(obj->rear)%(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; else return obj->a[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; else return obj->a[(obj->rear+obj->k)%(obj->k+1)]; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); }
栈与队列的内容到这里就结束了，下节开始学习堆与二叉树，
未完待续。。。
