• 【算法】栈和队列常见算法

    【算法】—— 栈和队列常见算法

    目录

    1. 括号匹配

    1.1 问题描述

    ​ 给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

    ​ 有效字符串需满足：

    1. 左括号必须用相同类型的右括号闭合。
    2. 左括号必须以正确的顺序闭合。

    示例 1：

    输入：s = "()[]{}"
输出：true

    • 1
    • 2

    示例 2：

    输入：s = "(]"
输出：false

    • 1
    • 2

    1.2 实现思路

    ​ 我们使用栈的先进后出的特性完成括号的匹配，遇到左括号入栈，遇到右括号时，将栈顶元素出栈，并与右括号比较，若是匹配则继续重复上述操作，若是不匹配则停止并返回false，当字符串遍历结束，检查

    1. 创建栈，并开始遍历字符串

    括号匹配1

    1. 匹配到第一个括号为左括号，入栈，第2个也为左括号，入栈

    括号匹配2

    1. 匹配到第3个为右括号，将栈顶出栈，比较结果与栈顶匹配，继续操作

    括号匹配3

    1. 匹配到第4个括号，将栈顶出栈，比较结果匹配

    括号匹配4

    1. 匹配到第5个字符为左括号，入栈，此时字符串遍历完毕，但是栈中还有数据，则括号不匹配，返回false

    括号匹配5

    1.3 代码实现

    //栈的接口
void StackInit(Stack** pps);			//初始化
void StackDestroy(Stack** pps);			//销毁
void StackPush(Stack* ps, int x); 		//入栈
void StackPop(Stack* ps);				//出栈
int StackTop(Stack* ps);			    //获取栈顶元素
_Bool StackEmpty(Stack* ps);			//判空
size_t StackSize(Stack* ps);			//获取大小

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    bool isValid(char * s)
{
    //创建栈
    Stack* ps = NULL;
    StackInit(&ps);

    char *c = s;
    while (*c != '\0')
    {
        //左括号入栈
        if (*c=='(' || *c=='[' || *c=='{')
        {
            StackPush(ps, *c);
        }
		
        //若栈为空，则栈中没有左括号，无法匹配右括号，返回0
        if (StackEmpty(ps))
        {
            StackDestroy(&ps);
            return false;
        }
        
        //右括号匹配则出栈，不匹配返回false
        if (*c==')' || *c==']' || *c=='}')
        {
            if ((*c==')' && StackTop(ps)=='(')
             ||(*c==']' && StackTop(ps)=='[')
             ||(*c=='}' && StackTop(ps)=='{'))
            {
                StackPop(ps);
            }
            else
            {
                StackDestroy(&ps);
                return false;
            }
        }

        c++;
    }

    //遍历结束栈为空时所有括号匹配，不为空时证明还有左括号未匹配
    if (StackEmpty(ps))
    {
        StackDestroy(&ps);
        return true;
    }
    else
    {
        StackDestroy(&ps);
        return false;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    2. 栈实现队列

    2.1 问题描述

    1. 使用两个栈实现先入先出的队列。
    2. 栈应只具备基本操作（入栈，出栈、获取栈顶元素、判空）
    3. 队列应具备基本的操作（入队列，出队列，获取队头元素，判空）

    2.2 实现思路

    1. 入队列： 将数据存储在一个栈中，顺序为1，2，3，4，模拟队列如图下方

    栈实现队列1

    1. 出队列： 由于出栈时的顺序为4，3，2，1，则将数据存储到另一个栈中，顺序为1，2，3，4，再出栈。若是再出栈则并不需要倒，直到第二个栈中没有数据时需要倒

    栈实现队列2

    栈实现队列3

    1. 获取队头元素： 直接获取第二个栈的栈顶元素，若是栈为空，则从第一个栈继续倒向第二个
    2. 判断队列为空： 两个栈都为空则队列为空

    2.3 代码实现

    //栈的接口
void StackInit(Stack* ps);			//初始化
void StackPush(Stack* ps, int x);	 //入栈
void StackPop(Stack* ps);			//出栈
int StackTop(Stack* ps);			//获取栈顶元素
_Bool StackEmpty(Stack* ps);		//判空
size_t StackSize(Stack* ps);		//获取大小
void StackDestroy(Stack* ps);		//销毁

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    //队列的声明
typedef struct Queue
{
    Stack s1;
    Stack s2;
} Queue;

//初始化
Queue* QueueCreate()
{
    Queue* pq = (Queue*)malloc(sizeof(Queue));
    if (pq == NULL)
    {
        perror("malloc fail\n");
        exit(-1);
    }
    
    StackInit(pq->s1);
    StackInit(pq->s2);
    return pq;
}

//入队列
void QueuePush(Queue* pq, int x)
{
    StackPush(&(pq->s1), x);
}

//如果s2为空，将s1数据倒入s2中
void S1ToS2(Queue* pq)
{
    if (StackEmpty(&(pq->s2)))
    {
        while (!StackEmpty(&(pq->s1)))
        {
        	StackPush(&(pq->s2), StackTop(&(pq->s1)));
        	StackPop(&(pq->s1));
        }
    }
}

//出队列
int QueuePop(Queue* pq)
{
    assert(!QueueEmpty(pq));
    S1ToS2(pq);
    int top = StackTop(&(pq->s2));
    StackPop(&(pq->s2));
    return top;
}

//获取队头元素
int QueueFront(Queue* pq)
{
    assert(!QueueEmpty(pq));
    S1ToS2(pq);
    return StackTop(&(pq->s2));
}

//判空
_Bool QueueEmpty(Queue* pq)
{
    return StackEmpty(&(pq->s1)) && StackEmpty(&(pq->s2));
}

//销毁
void QueueDestroy(Queue* pq)
{
    //先销毁栈，再释放队列
    StackDestroy(&(pq->s1));
    StackDestroy(&(pq->s2));
    free(pq);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73

    3. 队列实现栈

    3.1 问题描述

    1. 使用两个队列实现先入后出的栈。
    2. 队列应只具备基本的操作（入队列，出队列，获取队头元素，获取队尾元素，判空）
    3. 栈应具备基本操作（入栈，出栈、获取栈顶元素、判空）

    3.2 实现思路

    1. 入栈： 将数据存储在其中一个队列中，此时数据顺序是1，2，3，4，模拟栈中的存储如下图右侧

    队列实现栈1

    1. 获取栈顶元素： 可以调用队列的获取队尾元素操作

    队列实现栈2

    1. 出栈： 将4出栈，但是队列只能从1开始出，所以从1开始将数据往队列Queue_2中放，然后将4出队列

    队列实现栈3

    队列实现栈4

    1. 判断栈为空： 直接判断两个队列是否为空即可

    队列实现栈5

    3.3 代码实现

    //队列接口
void QueueInit(Queue* pq);				//初始化
void QueueDestroy(Queue* pq);			//销毁
void QueuePush(Queue* pq, int x);		//入队列
void QueuePop(Queue* pq);				//出队列
int QueueFront(Queue* pq);				//获取队头元素
int QueueBack(Queue* pq);				//获取队尾元素
_Bool QueueEmpty(Queue* pq);			//判空
size_t QueueSize(Queue* pq);			//获取队列长度

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    //声明栈
typedef struct Stack
{
    Queue q1;
    Queue q2;
} Stack;

//初始化
Stack* StackCreate()
{
    Stack* ps = (Stack*)malloc(sizeof(Stack));
    if (ps == NULL)
    {
        perror("malloc fail\n");
        exit(-1);
    }
    
    QueueInit(&(ps->q1));	//初始化q1
    QueueInit(&(ps->q2));	//初始化q2
    return ps;
}

//入栈
void StackPush(Stack* ps, int x)
{
    //如果q1不为空则插入到q1，否则插入到q2
    if (!QueueEmpty(&(ps->q1)))
    {
        QueuePush(&(ps->q1), x);
    }
    else
    {
        QueuePush(&(ps->q2), x);
    }
}

//出栈
int StackPop(Stack* ps)
{
    assert(!StackEmpty(ps));	//栈不能为空
    
    //判断空队列和非空队列
    Queue* empty = &(ps->q1);
    Queue* nonEmpty = &(ps->q2);
    if (!QueueEmpty(&(ps->q1)))
    {
        nonEmpty = &(ps->q1);
        empty = &(ps->q2);
    }
    
    //将非空队列的元素倒入空队列
    while (QueueSize(nonEmpty) > 1)
    {
        QueuePush(empty, QueueFront(nonEmpty));
        QueuePop(nonEmpty);
    }
    
    //返回非空队列的队头元素并出队列
    int top = QueueFront(nonEmpty);
    QueuePop(nonEmpty);
    return top;
}

//获取栈顶元素
int StackTop(Stack* ps)
{
    assert(!StackEmpty(ps));	//栈不能为空
    
    //哪个队列不为空，就返回它的队尾元素
    if (!QueueEmpty(&(ps->q1)))
    {
        return QueueBack(&(ps->q1));
    }
    
    if (!QueueEmpty(&(ps->q2)))
    {
        return QueueBack(&(ps->q2));
    }
}

//判空
_Bool StackEmpty(Stack* ps)
{
    return QueueEmpty(&(ps->q1)) && QueueEmpty(&(ps->q2));
}

//销毁
void StackDestroy(Stack* ps)
{
    //先销毁队列，再释放栈
    QueueDestroy(&(ps->q1));
    QueueDestroy(&(ps->q2));
    free(ps);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
  • 相关阅读:
    test IBM MQ with mqmeter
    bp神经网络的拓扑结构,bp神经网络拓扑结构图
    吃瓜教程第一二章学习记录
    板刷codeforces 1000分
    国际站腾讯云服务器搭建数据库的网络服务系统怎么设置呢？
    统一网关Gateway
    Ceph 在Linux上的使用
    mac删除带锁标识的app
    博客个人网页，是html博客网页设计
    从零构建医疗领域知识图谱的KBQA问答系统：其中7类实体，约3.7万实体，21万实体关系。
  • 原文地址：https://blog.csdn.net/weixin_52811588/article/details/126549921