目录
?一.括号匹配问题?
?二.用队列实现栈?
?三.用栈实现队列?
?四.设计循环队列?
?一.括号匹配问题?
OJ链接力扣
题目描述：
思路：先判断字符串长度，如果长度为奇数，则一定括号不匹配，直接返回false，若不为奇数，则采取以下的思路：遍历字符串，遇到左括号则入栈，遇到右括号则出栈，如果此时栈为空即没有左括号与之匹配，则返回false，让出栈的左括号与遇到的有括号匹配，若匹配失败则返回false。若匹配成功则继续遍历字符串，遍历完毕后检查栈是否为空，为空则说明全部括号匹配成功，返回true，如果不为空则说明有匹配未成功的情况返回false
代码：由于笔者用的编程语言为c语言，c语言没有标准库，故需要自己造轮子，下同
#include<stdbool.h>typedef char STDataType; typedef struct Stack{STDataType* a;int top;int capacity;}Stack;void StackInit(Stack* ps){assert(ps);ps->a = (STDataType *)malloc(sizeof(STDataType)*4);//申请空间if (ps->a ==NULL)//申请失败则报错{perror("error:ps->a");return;}ps->top = 0;//栈顶指向当前元素的下一个位置ps->capacity = 4;//初始容量为4}void StackPush(Stack* ps, STDataType data ){assert(ps);if (ps->top >= ps->capacity)//栈顶下标大于最大容量则扩容{ps->capacity = ps->capacity * 2;//容量翻倍ps->a = (STDataType*)realloc(ps->a, ps->capacity*sizeof(STDataType));}ps->a[ps->top++] = data;//元素入栈，栈顶指针+1}void StackPop(Stack* ps){assert(ps);assert(ps->top != 0);//栈为空则直接报错ps->top--;//出栈，即将栈顶指针减1}STDataType StackTop(Stack* ps){assert(ps);assert(ps->top != 0);//栈为空则直接报错return ps->a[ps->top - 1];//返回栈顶元素}int StackSize(Stack* ps){assert(ps);return ps->top;//返回栈顶指针}int StackEmpty(Stack* ps){assert(ps);if (ps->top == 0)//栈顶指针为0则说明栈空return 1;return 0;}void StackDestroy(Stack* ps){assert(ps);free(ps->a);//释放指针指向的空间ps->a = NULL;ps->top = ps->capacity = 0;}bool isValid(char * s){ int len=strlen(s); if(len%2!=0)//字符串长度为奇数则返回false return false; //定义栈并初始化 Stack st; StackInit(&st); int i=0; for(i=0;i<len;i++)//遍历字符串 { if(s[i]=='('||s[i]=='{'||s[i]=='[')//遇到左括号则入栈 StackPush(&st,s[i]); else//遇到右括号则进行匹配 { if(StackEmpty(&st))//如果栈为空则返回false return false; else { //出栈 char tmp=StackTop(&st); StackPop(&st); //不匹配则返回false if ((s[i]==')'&&tmp!='(')|| (s[i] == '}' && tmp != '{') || (s[i] == ']' && tmp != '[')) return false; } } //遍历完字符串判断栈是否为空，为空则说明都匹配成功返回true，否则返回false if(StackEmpty(&st)) return true;elsereturn false;}
?二.用队列实现栈?
oj链接力扣
题目描述：
思路：设置两个队列
入栈过程：入栈时判断哪个队列为空，将数据入栈到不为空的队列中，若两个队列都不为空则入栈到任意一个队列中
出栈过程：将不为空的队列出队数据到为空的队列中，直到不为空的队列数据个数只剩一个，这一个数据即需要出栈的数据，将此数据出栈即可
返回栈顶元素：找到不为空的队列，栈顶元素即此队列的队尾元素，调用返回队尾元素的函数即可
判空：两个队列同时为空即栈为空，分别调用两个队列判空函数进行判断即可
销毁：由于两个队列和栈都是动态开辟在堆上的，所以现需要将两个队列释放，再将栈释放
代码：
typedef int QDataType;typedef struct QListNode{struct QListNode* next;QDataType data;}QNode;// 队列的结构 typedef struct Queue{QNode* front;QNode* rear;}Queue;// 初始化队列 void QueueInit(Queue* q);// 队尾入队列 void QueuePush(Queue* q, QDataType data);// 队头出队列 void QueuePop(Queue* q);// 获取队列头部元素 QDataType QueueFront(Queue* q);// 获取队列队尾元素 QDataType QueueBack(Queue* q);// 获取队列中有效元素个数 int QueueSize(Queue* q);// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* q);// 销毁队列 void QueueDestroy(Queue* q);void QueueInit(Queue* q){assert(q);//队头和队尾指针置为空q->front = NULL;q->rear = NULL;}void QueuePush(Queue* q, QDataType data){assert(q);QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建一个新的节点newnode->data = data;if (q->rear ==NULL)//如果队列为空队列，则让队头和队尾都指向该新节点{q->rear = q->front = newnode;}else{//不为空则将新节点进行尾插操作q->rear->next = newnode;q->rear = newnode;}}void QueuePop(Queue* q){assert(q);assert(q->rear != NULL);//队列为空则报错if (q->rear == q->front)//如果队列只有一个元素，则将该元素出列，队头队尾指针置为空{free(q->front);q->rear = q->front = NULL;}else{//如果队列不只有一个元素，则进行出列操作，即头删操作QNode* cur = q->front;q->front = q->front->next;free(cur);}}QDataType QueueFront(Queue* q){assert(q);if (q->front == NULL)return NULL;return q->front->data;//返回队头指针指向的元素值}QDataType QueueBack(Queue* q){assert(q);if (q->rear == NULL)return NULL;return q->rear->data;//返回队尾指针指向的元素值}int QueueSize(Queue* q){assert(q);if (q->rear == NULL)//队列为空则返回空return 0;QNode* cur = q->front;//定义遍历指针int num = 1;//统计元素个数while (cur != q->rear)//遍历统计元素个数{num++;cur = cur->next;}return num;}int QueueEmpty(Queue* q){assert(q);if((q->front == q->rear) && (q->front == NULL))//队头队尾指针相等且都为空则队列为空return 1;return 0;}void QueueDestroy(Queue* q){assert(q);if (QueueEmpty(q))//队列为空则直接返回return;if (q->front == q->rear)//队列只有一个元素，删除这个元素，将两个指针置空{free(q->front);q->front = q->rear = NULL;}else{QNode* cur = q->front;//定义临时指针while (cur != q->rear)//遍历删除元素{q->front = q->front->next;free(cur);cur = q->front;}free(q->rear);//删除队尾q->front = q->rear = NULL;//两个指针置空}}//定义两个队列typedef struct { Queue q1; Queue q2;} MyStack;bool myStackEmpty(MyStack* obj);MyStack* myStackCreate() {动态开辟空间 MyStack* obj=(MyStack*)malloc(sizeof(MyStack));//两个队列初始化 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) {if(myStackEmpty(obj))return;//任意假设非空队列和空队列 Queue* empty=&obj->q1; Queue* noempty=&obj->q2;//假设错误则更改 if(!QueueEmpty(&obj->q1)) { empty=&obj->q2; noempty=&obj->q1; }//将非空队列的元素出队到空队列中，直到还剩一个元素 while(QueueSize(noempty)>1) { QueuePush(empty,QueueFront(noempty)); QueuePop(noempty); }//将只剩的这一个元素保存并返回 int tmp=QueueFront(noempty); QueuePop(noempty); return tmp;}int myStackTop(MyStack* obj) {if(myStackEmpty(obj))return;//假设非空队列和空队列 Queue* empty=&obj->q1; Queue* noempty=&obj->q2;//假设错误则更改 if(!QueueEmpty(&obj->q1)) { empty=&obj->q2; noempty=&obj->q1; }//调用队列获取队尾元素的函数return QueueBack(noempty);}bool myStackEmpty(MyStack* obj) {//两个队列都为空说明栈为空 return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);}void myStackFree(MyStack* obj) {//先释放两个队列 QueueDestroy(&obj->q1); QueueDestroy(&obj->q2);//再释放栈 free(obj);}
?三.用栈实现队列?
oj链接力扣
题目描述：
思路：设置两个栈，一个作为入队栈，一个作为出队栈
入队过程：将数据入队到入队栈，即调用入栈函数将数据插入到该栈即可
出队过程：判断出队栈是否为空，为空则将入队栈的元素倒到出队栈，队头元素就是出队栈的栈顶元素，对出队栈调用出栈函数即可
返回队头元素：判断出队栈是否为空，为空则将入队栈的元素倒到出队栈，队头元素就是出队栈的栈顶元素，对出队栈调用返回栈顶元素函数即可
判空：两个栈都空即队列为空，分别对两个队列调用队列判空的函数进行判断即可
销毁：由于两个栈和队列都是在堆上动态开辟的，因此需要先释放两个栈，再释放队列
代码：
typedef int STDataType; typedef struct Stack{STDataType* a;int top;int capacity;}Stack; //初始化栈void StackInit(Stack * ps); // 入栈 void StackPush(Stack* ps, STDataType data); // 出栈 void StackPop(Stack* ps); // 获取栈顶元素 STDataType StackTop(Stack* ps); // 获取栈中有效元素个数 int StackSize(Stack* ps); // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 int StackEmpty(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps);void StackInit(Stack* ps){assert(ps);ps->a = (STDataType *)malloc(sizeof(STDataType)*4);//申请空间if (ps->a ==NULL)//申请失败则报错{perror("error:ps->a");return;}ps->top = 0;//栈顶指向当前元素的下一个位置ps->capacity = 4;//初始容量为4}void StackPush(Stack* ps, STDataType data ){assert(ps);if (ps->top >= ps->capacity)//栈顶下标大于最大容量则扩容{ps->capacity = ps->capacity * 2;//容量翻倍ps->a = (STDataType*)realloc(ps->a, ps->capacity*sizeof(STDataType));}ps->a[ps->top++] = data;//元素入栈，栈顶指针+1}void StackPop(Stack* ps){assert(ps);assert(ps->top != 0);//栈为空则直接报错ps->top--;//出栈，即将栈顶指针减1}STDataType StackTop(Stack* ps){assert(ps);assert(ps->top != 0);//栈为空则直接报错return ps->a[ps->top - 1];//返回栈顶元素}int StackSize(Stack* ps){assert(ps);return ps->top;//返回栈顶指针}int StackEmpty(Stack* ps){assert(ps);if (ps->top == 0)//栈顶指针为0则说明栈空return 1;return 0;}void StackDestroy(Stack* ps){assert(ps);free(ps->a);//释放指针指向的空间ps->a = NULL;ps->top = ps->capacity = 0;}typedef struct { //定义两个栈 Stack pushst; Stack popst;} MyQueue;MyQueue* myQueueCreate() { //开辟空间 MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue)); //初始化两个栈 StackInit(&obj->pushst); StackInit(&obj->popst); return obj;}void myQueuePush(MyQueue* obj, int x) { assert(obj); //将出队栈出栈即可 StackPush(&obj->pushst,x);}int myQueuePeek(MyQueue* obj) { assert(obj); //出队栈如果为空，则需要将入队栈的元素倒到出队栈 if(StackEmpty(&obj->popst)) { //将入队栈的元素倒到出队栈 while(!StackEmpty(&obj->pushst)) { StackPush(&obj->popst,StackTop(&obj->pushst)); StackPop(&obj->pushst); } } //返回出队栈的栈顶元素 return StackTop(&obj->popst);}bool myQueueEmpty(MyQueue* obj) { assert(obj); //两个栈都为空即队列为空 return StackEmpty(&obj->pushst)&&StackEmpty(&obj->popst);}int myQueuePop(MyQueue* obj) { assert(obj); 将出队栈的栈顶元素保存然后返回 int tmp=myQueuePeek(obj); StackPop(&obj->popst); return tmp;}void myQueueFree(MyQueue* obj) { assert(obj); //先释放两个栈 StackDestroy(&obj->pushst); StackDestroy(&obj->popst); //再释放队列 free(obj);}
?四.设计循环队列?
oj链接力扣
题目描述：
思路：利用静态数组实现循环队列，题目要求队列长度为k,我们额外开辟一个空间，保持始终有一个空间为空，方便判空和判满，队头下标指向队头元素，队尾下标指向队尾元素的下一个位置
初始化：开辟一个K+1的空间并用一个指针指向该空间，队头和队尾指针都置为零，然后返回整个空间
获取队头元素：判断对列是否为空，队头下标等于队尾下标即为空，为空则返回-1，不为空则返回队头下标的元素，如果队头下标等于K+1,即此时队头下标越界，由于是循环队列，故将队头下标置为0
获取队尾元素：判断对列是否为空，队头下标等于队尾下标即为空，为空则返回-1，不为空则返回队尾下标-1的元素，如果如果队尾下标等于K+1,即此时队头下标越界，由于是循环队列，故将队头下标置为0，如果队尾下标为0，此时-1发生越界，故直接返回下标为k-1的元素即可
入队：判断队列是否已满，已满则返回false,未满则将数据赋值到队尾下标，然后队尾下标加1。若队尾下标发生越界则置为0
出队：判断队列是否为空，为空则返回false,不为空则将队头下标+1即可，若队头下标发生越界则置为0
判空：队头下标等于队尾下标即为空，否则不为空
判满：队尾下标+1等于队头下标即为满，由于是循环队列，故需要对加1后的队尾下标模上队列长度再与队头下标比较
销毁：先释放数组空间，再释放整体
代码：
typedef struct { int *a; int front; int rear; int k;} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); //开辟k+1的空间 obj->a=(int *)malloc(sizeof(int)*(k+1)); //队头下标和队尾下标都置为0 obj->front=obj->rear=0; obj->k=k; return obj;}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { //判满，若队列已满则但会false if((obj->rear+1)%(obj->k+1)==obj->front) return false; //入队 obj->a[obj->rear]=value; obj->rear++; //队尾下标越界则置为0 if(obj->rear==obj->k+1) obj->rear=0; return true;}bool myCircularQueueDeQueue(MyCircularQueue* obj) { //判空，若队列为空则返回false if(obj->front==obj->rear) return false; //出队 obj->front++; 队头下标越界则置为0 if(obj->front==obj->k+1) obj->front=0; return true;}int myCircularQueueFront(MyCircularQueue* obj) { //判空，若队列为空则返回-1 if(obj->front==obj->rear) return -1; //队头下标越界则置为0 if(obj->front==obj->k+1) obj->front=0; //返回队头下标的元素 return obj->a[obj->front];}int myCircularQueueRear(MyCircularQueue* obj) { //判空，若队列为空则返回-1 if(obj->front==obj->rear) return -1; //队尾下标越界则置为0 if(obj->rear==obj->k+1) obj->rear=0; //若队尾下标为0，则返回最后一个元素 if(obj->rear==0) return obj->a[obj->k]; //队尾下标不为0则返回队尾下标-1的元素 else return obj->a[obj->rear-1];}bool myCircularQueueIsEmpty(MyCircularQueue* obj) { //队头下标等于队尾下标则为空 if(obj->front==obj->rear) return true; else return false;}bool myCircularQueueIsFull(MyCircularQueue* obj) { //队尾下标加1再模等于之后如果等于队头下标则已满 if((obj->rear+1)%(obj->k+1)==obj->front) return true; else return false;}void myCircularQueueFree(MyCircularQueue* obj) { //先释放数组空间 free(obj->a); obj->a= NULL; obj->front=obj->rear=0; //再释放整体 free(obj);}好啦，关于栈和队列的经典题解就先学到这，如果对您有所帮助，欢迎一键三连~