【LeetCode】20.有效的括号（栈的括号匹配问题）
原题链接：🍏有效的括号🍏
题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 1.左括号必须用相同类型的右括号闭合。
- 2.左括号必须以正确的顺序闭合。
- 3.每个右括号都有一个对应的相同类型的左括号。
根据栈“先入后出”的特性，我们可以利用栈的数据结构进行检验。
当遇到左括号时，入栈，遇到右括号出栈。
最后检查栈中是否还堆积有元素，如果有证明匹配失败，如果栈空，证明匹配成功。
代码实现：
typedef int STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; // 初始化 void STInit(ST* ps) { assert(ps); ps->a = NULL; ps->capacity = 0; ps->top = 0; } // 销毁 void STDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } // 入栈 void STPush(ST* ps, STDataType x) { assert(ps); if (ps->capacity == ps->top) { int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; STDataType* tmp = (STDataType*)realloc(ps->a,newcapacity * sizeof(STDataType)); if (tmp==NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->top]=x; ps->top++; } // 出栈 void STPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; } // 取栈顶元素 STDataType STTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top-1]; } // 判空 bool STEmpty(ST* ps) { assert(ps); return ps->top == 0; } // 检验是否匹配 bool isValid(char * s) { ST st; STInit(&st); char val; while(*s) { if(*s=='('||*s=='{'||*s=='[') { STPush(&st,*s);// 是左括号 入栈 } else { if(STEmpty(&st))// 排除 首个字符为右括号的情况 { STDestroy(&st); return false; } val=STTop(&st);// 取栈顶字符判断 STPop(&st); if((*s==')'&& val!='(') ||(*s==']' && val!='[') ||(*s=='}' && val!='{'))// 左右括号不匹配 { STDestroy(&st); return false; } } s++; } bool ret=STEmpty(&st);// 判断数量是否匹配 STDestroy(&st); return ret; }
【LeetCode】225.用队列实现栈
原题链接：🍏用队列实现栈🍏
题目：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
首先我们知道队列的特性是先入先出，栈的特性是先入后出，题目既然给了我们两个队列，那么一定是利用这两个队列进行捯数据，从而实现栈先入后出的特性。
思路：
每次入栈，利用不空的队列入数据；
当需要出栈时，将非空队列“出队”到空的队列上，直到剩余最后一个元素，取该元素，然后出队，即完成出栈动作。
当需要取栈顶元素时，只需要取非空队列的队尾，此时该队尾即为栈顶元素。
当需要判空时，只需要判断两个队列是否都为空即可。
注意：该题主要考察的其实是大家对于结构的理解，如形参MyStack* obj，实参对应为&obj->q1或&obj->q2，&操作符的优先级低于->，obj是该栈指针，obj->q1为队列结构体，但由于参数为指针类型，所以需要&。
代码实现：
// 队列的基本函数 typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Que; void QueueInit(Que* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; } bool QueueEmpty(Que* pq) { assert(pq); return pq->head == NULL; } void QueueDestroy(Que* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; pq->size = 0; } void QueuePush(Que* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; if (pq->tail == NULL) { pq->tail = pq->head = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; } void QueuePop(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next; free(pq->head); pq->head = next; } pq->size--; } QDataType QueueFront(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } QDataType QueueBack(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } int QueueSize(Que* pq) { assert(pq); return pq->size; } // 以上为队列的基本函数 // 以下为用队列实现栈 // 定义栈 typedef struct { Que q1; Que q2; } MyStack; // 创建栈 MyStack* myStackCreate() { MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&pst->q1); QueueInit(&pst->q2); return pst; } // 入栈 void myStackPush(MyStack* obj, int x) { if (!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1, x); } else { QueuePush(&obj->q2, x); } } // 出栈 int myStackPop(MyStack* obj) { // 假设法，假设q1为空，q2不空 Que* EmpQue = &obj->q1; Que* noEmpQue = &obj->q2; if (!QueueEmpty(&obj->q1)) { noEmpQue = &obj->q1; EmpQue = &obj->q2; } // 此时EmpQue一定为空的队列，noEmpQue 一定不为空的队列 // 将size-1个数据移动到空队列中 while (QueueSize(noEmpQue) > 1) { QueuePush(EmpQue, QueueFront(noEmpQue)); QueuePop(noEmpQue); } //保存返回值 int ret = QueueFront(noEmpQue); QueuePop(noEmpQue); return ret; } // 取栈顶元素 int myStackTop(MyStack* obj) { // 不空的队列的队尾即为栈顶 if (!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } else { return QueueBack(&obj->q2); } } // 判空 bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); } // 销毁栈 void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); // free栈之前一定要先销毁队列，否则会导致内存泄露 free(obj); }
【LeetCode】232.用栈实现队列
原题链接：🍏用栈实现队列🍏
题目：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
与上面用队列实现栈的思路相似，需要两个栈用来捯数据，不同的是，分析过后你会发现这里的两个栈，一个可以固定用来做入队栈（下面统称为pushst），而另外一个固定用来做出队栈（下面统称为popst）。
思路：
入队时，直接push到pushst即可；
出队时，需要进行判断，当popst不为空时，直接出栈popst，注意保存栈顶元素以便返回；当popst为空时，需要将pushst的数据依次捯到popst中，然后出栈popst，同样注意保存栈顶元素以便返回；
返回队头元素时，我们可以写一个返回栈底元素的函数，然后同样进行判断，如果popst为空，我们就返回pushst的栈底；如果popst不为空，我们就返回popst的栈顶即可；
判空时，思路与用队列实现栈相同。
代码实现：
typedef struct { ST s1;//入队栈pushst ST s2;//出队栈popst } MyQueue; MyQueue* myQueueCreate() { MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue)); STInit(&pst->s1); STInit(&pst->s2); return pst; } void myQueuePush(MyQueue* obj, int x) { STPush(&obj->s1,x); } int myQueuePop(MyQueue* obj) { if(!STEmpty(&obj->s2)) { int x=STTop(&obj->s2); STPop(&obj->s2); return x; } else { while(!STEmpty(&obj->s1)) { int x=STTop(&obj->s1); STPop(&obj->s1); STPush(&obj->s2,x); } int y=STTop(&obj->s2); STPop(&obj->s2); return y; } } int myQueuePeek(MyQueue* obj) { if(STEmpty(&obj->s2)) { return STbase(&obj->s1); } else { return STTop(&obj->s2); } } bool myQueueEmpty(MyQueue* obj) { return STEmpty(&obj->s1)&&STEmpty(&obj->s2); } void myQueueFree(MyQueue* obj) { STDestroy(&obj->s1); STDestroy(&obj->s2); free(obj); }
【LeetCode】622.设计循环队列
原题链接：🍏设计循环队列🍏
题目：设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
由于题目中已经明确队列长度，所以定长数组是一个较优的解决方案。
该题目最要首先理解的两个函数为判空和判满。
判空：我们首先肯定会想到当front和rear相等时，即为空。
那么问题来了，如何判满呢？
貌似判空和判满都可以利用front和rear是否相等来判断，如何区分呢？
判满：普遍的解决方案为牺牲一个空间，让该数组始终留有一个空间，用作区分，那么就有以下几种情况，请试着依据下图总结规律，得到判满通用公式。
判满公式：(rear+1)%(k+1)==front
只要了解了这个思想，剩下的就简单很多了。
代码实现：
typedef struct { int* a; int front; int rear; int k; } 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->k+1; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return false; } 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); }
