栈和队列特别篇:栈和队列的经典算法问题

图均为手绘,代码基于vs2022实现

系列文章目录

数据结构初探: 顺序表
数据结构初探:链表之单链表篇
数据结构初探:链表之双向链表篇
链表特别篇:链表经典算法问题
数据结构:栈篇
数据结构:队列篇

---

---

前言

• 栈和队列作为基础数据结构，是算法设计中的重要基石。它们在操作系统、编译器设计、网络协议等领域有着广泛应用。本文将通过C语言实现经典算法问题，帮助读者深入理解它们的底层原理和应用技巧。学习这些内容不仅能提升算法能力，还能加深对内存管理和数据结构设计的理解。

---

一.有效的括号(leetcode 20)

让我们先来看看题目:

让我们来理清楚思路:

• 首先,我们可以用栈来实现匹配

1.我们将左括号入栈;
2.在遍历中找到右括号,进行匹配;

• 在这个过程中,我们需要手撕一个栈的代码出来,加在题目代码之前,如果发现还不太熟练,可以再去我的这篇博客中熟悉熟悉—> 数据结构:栈篇
• 我们还是上代码实际感受一下吧(考虑到篇幅有限,已省略栈的代码):

//注意这里是字符,栈的代码中要将int改为char
//typedef char STDataType;
bool isValid(char* s) {ST st;//创建栈STInit(&st);//初始化栈while(*s)//依次遍历字符串{if(*s == '(' || *s == '[' || *s == '{')//如果是左括号{STPush(&st,*s);//我们就将其入栈}else//其他情况{if(STEmpty(&st))//如果没找到左括号,就算下面有右括号{//我们也无法找到匹配的括号STDestroy(&st);//所以销毁,防止内存泄漏return false;//直接返回false,表示找不到匹配的括号}//因为题目要求的是按顺序一一对应;char top=STTop(&st);//此时记录下栈顶元素STPop(&st);//再pop,表示出栈操作//匹配括号逻辑结构//大家可以自行分析;//即如果右括号没有在栈顶找到对应的左括号,则错误if((*s == ')' && top != '(')||(*s == ']' && top != '[')||(*s == '}' && top != '{')){STDestroy(&st);//所以销毁,防止内存泄漏return false;//直接返回false,表示找不到匹配的括号}}s++;//更新循环条件}bool ret=STEmpty(&st);//记录是否找到对应括号的状态STDestroy(&st);//销毁,防止内存泄漏return ret;//返回对应状态
}

学完后,自己多多练习,自行手撕,理清逻辑即可;

二.用队列实现栈(leetcode 225)

让我们先来看看题目:

让我们来理清楚思路:
我们需要用到两个队列来实现栈:

• 一个用来当作入栈队列
• 一个用来当作出栈队列
• 我们还要注意其LIFO的性质,和随进随出的特点
  1.我们需要保持一个队列为空,一个队列存数据
  2.出栈,把前面的数据导入空队列
  3.如此两班来回倒,就可以实现栈的特性;
  逻辑如图:
  
  在这个过程中,我们需要手撕队列的代码出来,加在题目代码之前,如果发现还不太熟练,可以再去我的这篇博客中熟悉熟悉—> 数据结构:队列篇
  我们来实战一下:

//创建两个队列的结构体
typedef struct {Queue q1;Queue q2;
} MyStack;
//我们需要动态开辟出空间来实现mystack
MyStack* myStackCreate() {MyStack* pst=(MyStack*)malloc(sizeof(MyStack));if(pst == NULL){perror("malloc fail");return NULL;}QueueInit(&pst->q1);//对两个队列初始化QueueInit(&pst->q2);return pst;//返回初始化后的我们的mystack
}
//来实现栈的插入
void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1))//如果q1不为空就插入到q1里{//反正有一个队列里面是空的,我们不能插入,一旦插入就会弄乱整体的逻辑QueuePush(&obj->q1,x);//可以参看上文图进行理解}else//如果q2不为空就插入到q2里{//两个都为空就随便选一个QueuePush(&obj->q2,x);}
}
//实现栈的删除,题目要求:移除并返回栈顶元素
int myStackPop(MyStack* obj) {//首先要明确哪个为空,哪个为非空Queue* emptyQ=&obj->q1;//假设q1为空Queue* nonemptyQ=&obj->q2;//q2不为空if(!QueueEmpty(&obj->q1))//验证是否正确{//进入则是不正确emptyQ=&obj->q2;//不正确则交换nonemptyQ=&obj->q1;}while(QueueSize(nonemptyQ) > 1)//设置遍历循环{QueuePush(emptyQ,QueueFront(nonemptyQ));//将非空的前面n-1个挪入空队列QueuePop(nonemptyQ);//pop掉已经挪入的那n-1个}//剩下的就是要按照栈的特性LIFO顺序的数据int top=QueueFront(nonemptyQ);//按照题目要求记录下数据QueuePop(nonemptyQ);//popreturn top;//返回数据
}
//返回栈顶元素
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(obj);
}

销毁逻辑示例图:

三.用栈实现队列(leetcode 232)

让我们先来看看题目:

让我们来理清楚思路:
我们需要用到两个栈来实现队列:

• 一个用来当作入队栈
• 一个用来当作出队栈
• 我们还要注意其FIFO的性质,和随进随出的特点
  1.我们需要保持一个入队栈,一个出队栈
  2.出队列,把前面的数据导入空栈
  3.当出队栈不为空时,不能再将出队栈中的数据导入,否则顺序会乱;
  如图:
  
  让我们来感受一下代码:

typedef struct {ST pushst;//入队栈ST popst;//出队栈
} MyQueue;int myQueuePeek(MyQueue* obj);//返回队头元素的函数声明;
//动态开辟
MyQueue* myQueueCreate() {MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));if(obj==NULL){perror("malloc fail");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) {
//两个栈都为空,才为空return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
}
//释放所有动态开辟的空间
void myQueueFree(MyQueue* obj) {STDestroy(&obj->pushst);STDestroy(&obj->popst);free(obj);}

四.设计循环队列(leetcode 622)

让我们来看看题目:

我们来理清楚逻辑:
这里我们选择用数组来实现,链表实现也是可以的,但是相对来说,数组实现会更加容易;对于数组是否满了,我们有两种解决办法:

• 在结构体中加入size来计量;
• 空出一个位置来提醒判断已满
  让我们来实战:

//定义结构体
typedef struct {int* a;//静态数组int front;//头int rear;//尾int k;//满数据时候的个数
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//函数声明,防止编译错误
bool myCircularQueueIsFull(MyCircularQueue* obj);
//开出对应大小的空间
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(obj==NULL){perror("malloc fail");return NULL;}obj->a=(int*)malloc(sizeof(int)*(k+1));//多开,防止溢出if(obj->a==NULL){perror("malloc fail");return NULL;}obj->front=obj->rear=0;//指向开头obj->k=k;return obj;
}
//插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))//如果是满的{return false;//返回false,表示不能再插入了}obj->a[obj->rear++] = value;//否则存储值,并且rear++到下一个位置;obj->rear %= (obj->k+1);//对尾取模,比如,1%5==1,3%5==3,如果满了5%5==0//就会循环回到数组开始的下标return true;//返回true,表示还可以插入
}
//删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))//如果是空的{return false;//返回false,表示不能再删除了}obj->front++;//头往下一个位置走,这个就与我们曾经讲过的顺序表里面的删除一样的//只要我们不把它计量在有效个数中就可以删除它obj->front %= (obj->k+1);//对头取模,比如,1%5==1,3%5==3,如果满了5%5==0//就会循环回到数组开始的下标return true;//返回true,表示还可以删除
}
//按题目要求:从队首获取元素。如果队列为空，返回 -1
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))//若为空{return -1;//返回}return obj->a[obj->front];//返回头元素
}
//按题目要求:获取队尾元素。如果队列为空，返回 -1 
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->a[(obj->rear-1+obj->k+1) % (obj->k+1)];//防止因为rear在下标0的位置--,而发生错误;//通过取模,来造成循环;
}
//简单的判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->rear == obj->front;
}
//判断满
bool myCircularQueueIsFull(MyCircularQueue* obj) {//通过取模,来造成循环;return (obj->rear+1) % (obj->k+1) == obj->front;//保证rear的下一个是头
}
//释放,相同与前两题,可以自行画图理解;
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}

以上就是我要讲的所有的经典问题,你学会了吗?

---

五.总结

在本次博客中，我们围绕栈和队列这两种基础数据结构，通过C语言实现经典算法问题，深入探索了它们的底层原理与应用技巧。

• 首先是“有效的括号”问题，利用栈来匹配括号，左括号入栈，右括号与栈顶元素匹配，这种方式充分展现了栈“后进先出”（LIFO）的特性，在处理具有成对结构的数据时十分有效 ，能够清晰地判断括号是否匹配，避免逻辑混乱。
• 接着，在“用队列实现栈”和“用栈实现队列”的问题中，分别运用两个队列和两个栈来模拟对方的特性。用队列实现栈时，通过在两个队列间来回转移数据，确保满足栈的LIFO性质；用栈实现队列则是利用两个栈，在入队栈和出队栈间合理转移数据，保证队列“先进先出”（FIFO）的特性。这两个问题不仅锻炼了对数据结构特性的灵活运用，还让我们深入理解了不同数据结构间的转换和模拟方法。
• 最后，在“设计循环队列”中，使用数组实现循环队列，通过巧妙的取模操作实现队列的循环，同时提供了判空和判满的方法。这种实现方式既高效又简洁，充分利用了数组的连续性和可索引性，加深了我们对队列数据结构的理解和应用能力。

通过解决这些经典算法问题，我们不仅掌握了栈和队列在实际编程中的应用，还提升了算法设计、逻辑思维以及内存管理的能力。希望读者能够通过不断练习，熟练掌握这些知识，在后续的编程学习和实践中更加得心应手，灵活运用栈和队列解决各种复杂的实际问题，为更深入的算法学习和系统开发打下坚实的基础。