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

图均为手绘,代码基于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);//pop

    return 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）的特性。这两个问题不仅锻炼了对数据结构特性的灵活运用，还让我们深入理解了不同数据结构间的转换和模拟方法。
• 最后，在“设计循环队列”中，使用数组实现循环队列，通过巧妙的取模操作实现队列的循环，同时提供了判空和判满的方法。这种实现方式既高效又简洁，充分利用了数组的连续性和可索引性，加深了我们对队列数据结构的理解和应用能力。

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