• 栈与队列练习题

    作者前言

    🎂 ✨✨✨✨✨✨🍧🍧🍧🍧🍧🍧🍧🎂
    ​🎂 作者介绍： 🎂🎂
    🎂 🎉🎉🎉🎉🎉🎉🎉 🎂
    🎂作者id：老秦包你会， 🎂
    简单介绍：🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂
    喜欢学习C语言和python等编程语言，是一位爱分享的博主，有兴趣的小可爱可以来互讨 🎂🎂🎂🎂🎂🎂🎂🎂
    🎂个人主页::小小页面🎂
    🎂gitee页面:秦大大🎂
    🎂🎂🎂🎂🎂🎂🎂🎂
    🎂 一个爱分享的小博主 欢迎小可爱们前来借鉴🎂

    练习题

    有效的括号

    有效的括号
    在这里插入图片描述
    思路: 我们可以使用一个栈来解决这个问题, 我们用栈来存储左括号,当遇见右括号就取出栈顶元素出来比较,如果符合就继续匹配,否则就返回false, 或者最后栈还要数据,或者栈没有数据但还要右括号都是不匹配成功的

    typedef char TackDataType;
typedef struct Stack
{
    TackDataType * a;
    int top; //栈顶元素
    int capacity;
}Stack;
//初始化
void TackInit(Stack *pst)
{
    assert(pst);
    pst->a = NULL;
    pst->top = -1;
    pst->capacity = 0;
}
// 入栈
void TackPush(Stack *pst, TackDataType elemest)
{
    assert(pst);
    //判断是否满了
    if ((pst->top) +1 == pst->capacity)
    {
        pst->capacity = (pst->capacity == 0? 4 : pst->capacity * 2);
        TackDataType* tmp = (TackDataType*)realloc(pst->a,sizeof(Stack) * pst->capacity);
        if (tmp == NULL)
        {
            perror("realloc");
            return;
        }
        pst->a = tmp;

    }
    pst->a[++(pst->top)] = elemest;

}
//出栈
void TackPop(Stack *pst)
{
    assert(pst);
    if(pst->top != -1)
        pst->top--;
}
//长度
int TackSize(Stack *pst)
{
    assert(pst);
    return (pst->top) + 1;
}
//是否为空
bool TackEmpty(Stack *pst)
{
    assert(pst);
    return pst->top == -1; 
}
//栈顶元素
TackDataType TackTop(Stack *pst)
{
    assert(pst);
    return pst->a[pst->top];
}
//释放
void TackDestroy(Stack *pst)
{
    free(pst->a);
    pst->a = NULL;
    pst->top = -1;
    pst ->capacity = 0;
}

bool isValid(char* s) 
{
    Stack pst;
    //初始化
    TackInit(&pst);
    while(*s)
    {
        if(*s == '{' || *s == '[' || *s == '(')
        {
            //入栈
            TackPush(&pst, *s);

        }
        else
        {
            //是否为空
            if (TackEmpty(&pst))
            {
                TackDestroy(&pst);
                return false;
            }

                
            //栈顶元素
            if ((*s == '}' &&  TackTop(&pst) == '{')
            || (*s == ']' &&  TackTop(&pst) == '[')
            ||(*s == ')' &&  TackTop(&pst) == '('))
            {
                //出栈
                TackPop(&pst);
            }
            else
            {
                return false;
            }
            

        }
        s++;
    }
    //是否为空
    if (!TackEmpty(&pst))
    {
        TackDestroy(&pst);
        return false;
    }
    TackDestroy(&pst);    
    return true;

    
}

    • 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
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120

    用队列实现栈

    用队列实现栈
    在这里插入图片描述

    这道题主要的就是在删除和插入数据中要下点功夫,
    插入: 我们只需往不为空的队列插入,因为这样必定有一个队列为空,如果刚开始两个队列都为空,我们只需随意插入一个队列就行
    删除: 我们删除栈的栈顶元素,是直接删除最新插入的元素,而队列的特点就是先进先出,我们可以借助空队列把非空队列的最后一个元素保留下来,然后把多余的元素插入到空队列中,需要注意的是,插入的最后一个元素的下一个next一定要修改为NULL,不然在释放会有野指针,然后保留的最后一个元素再free掉,
    剩下的就是释放空间:
    我们要先释放掉链表的空间,然后再释放两个队列的空间,

    删除:
    在这里插入图片描述

    typedef int QDataType;
//链表节点
typedef struct QNode
{
    QDataType val;
    struct QNode *next;
}QNode;
//队列结构
typedef struct Queue
{
    QNode* head;
    QNode* tail; //队尾
    int size;
}Queue;


//创建两个队列
typedef struct
{
    Queue stack1;
     Queue stack2;

} MyStack;


MyStack* myStackCreate() 
{
    //创建两个队列
    MyStack * Queuetack = (MyStack*)malloc(sizeof(MyStack));
    //创建哨兵位
    Queuetack->stack1.head = (QNode*)malloc(sizeof(QNode));
    Queuetack->stack1.head->next = NULL;
    Queuetack->stack1.size = 0;
     Queuetack->stack1.tail = Queuetack->stack1.head;
      //创建哨兵位
     Queuetack->stack2.head = (QNode*)malloc(sizeof(QNode));
    Queuetack->stack2.head->next = NULL;
    Queuetack->stack2.size = 0;
     Queuetack->stack2.tail = Queuetack->stack2.head;
     return Queuetack;

    
}

void myStackPush(MyStack* obj, int x) 
{
   assert(obj);
    if (obj->stack2.size)
    {
        //创建节点
        QNode* newnode = (QNode*)malloc(sizeof(QNode));
        newnode->val = x;
        newnode->next = NULL;
        //插入
        obj->stack2.tail->next = newnode;
        obj->stack2.tail = newnode;
        obj->stack2.size++;
    }
    else
    {
        //创建节点
        QNode* newnode = (QNode*)malloc(sizeof(QNode));
        assert(newnode);
        newnode->val = x;
        newnode->next = NULL;
        //插入
        obj->stack1.tail->next = newnode;
        obj->stack1.tail = newnode;
        obj->stack1.size++;
    }
}

int myStackPop(MyStack* obj) 
{
    if (!obj->stack2.size && !obj->stack1.size)
        return 0;
    if (obj->stack2.size)
    {
        while (obj->stack2.head->next != obj->stack2.tail)
        {
            QNode* node = obj->stack2.head->next;
            obj->stack2.head->next = node->next;
            obj->stack1.tail->next = node;
            obj->stack1.tail = node;
            
            obj->stack1.size++;

        }
        obj->stack1.tail->next = NULL;
        int a = obj->stack2.tail->val;
        free(obj->stack2.tail);
        obj->stack2.tail = obj->stack2.head;
        obj->stack2.head->next = NULL;
        obj->stack2.size = 0;
        return a;
    }
    else
    {

        while (obj->stack1.head->next != obj->stack1.tail)
        {
            QNode* node = obj->stack1.head->next;
            obj->stack1.head->next = node->next;
            obj->stack2.tail->next = node;
            obj->stack2.tail = node;
            
            obj->stack2.size++;

        }
        obj->stack2.tail->next = NULL;
        int a = obj->stack1.tail->val;
        free(obj->stack1.tail);
        obj->stack1.tail = obj->stack1.head;
        obj->stack1.head->next = NULL;
        obj->stack1.size = 0;
        return a;
    }
    
}

int myStackTop(MyStack* obj) 
{

    
    if (!obj->stack2.size && !obj->stack1.size)
        return 0;
    if (!obj->stack2.size)
    {
        return obj->stack1.tail->val;
    }
    else
    {
        return obj->stack2.tail->val;
    }
}

bool myStackEmpty(MyStack* obj) 
{
    return obj->stack2.size== 0 && obj->stack1.size ==0;
}

void myStackFree(MyStack* obj) 
{
    QNode *cur = obj->stack1.head->next;
    while(cur)
    {
        QNode *cur1 = cur->next;
        free(cur);
        cur = cur1;
    }
    free(obj->stack1.head);
    obj->stack1.head = NULL;
    obj->stack1.size = 0;
    obj->stack1.tail = NULL;

    cur = obj->stack2.head->next;
     while(cur)
    {
        QNode *cur1 = cur->next;
        free(cur);
        cur = cur1;
    }
     free(obj->stack2.head);
    obj->stack2.head = NULL;
    obj->stack2.size = 0;
    obj->stack2.tail = NULL;
    free(obj);
}

    • 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
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168

    用栈实现队列

    在这里插入图片描述
    这道题的思路和上面的题目思路是相同的,我们借助两个栈来实现队列,
    有点差别就是
    删除:
    在这里插入图片描述
    删除我们不能从top那边开始拉数据,而是要从left开始,
    我们还要注意的就是队列插入的时候一定判断 栈是否要扩大空间,

    typedef int StackDAtaType;
typedef struct Stack
{
    StackDAtaType *data;
    int top;//栈顶元素下一个
    int capacity;

}Stack;

typedef struct 
{
    Stack stack1;
    Stack stack2;
} MyQueue;


MyQueue* myQueueCreate() 
{
    //初始化
    MyQueue *queue = (MyQueue*)malloc(sizeof(MyQueue));
    //第一个栈
    queue->stack1.data = NULL;
    queue->stack1.top = 0;//栈顶元素的下一个
    queue->stack1.capacity = 0;
    //第二个栈
    queue->stack2.data = NULL;
    queue->stack2.top = 0;
    queue->stack2.capacity = 0;
    return queue;
}

void myQueuePush(MyQueue* obj, int x) 
{
    if(obj->stack1.top)
    {
        //第一个栈插入
        //判断是否满栈
        if(obj->stack1.top == obj->stack1.capacity)
        {
            obj->stack1.capacity = (obj->stack1.capacity == 0 ? 4 : obj->stack1.capacity * 2);
             StackDAtaType *tmp =  (StackDAtaType*)realloc(obj->stack1.data, sizeof(StackDAtaType) * obj->stack1.capacity);
             if (tmp == NULL)
             {
                 perror("realloc");
                 return ;
             }
              obj->stack1.data = tmp;
        }
        obj->stack1.data[obj->stack1.top++] = x;
    }
    else
    {
        //第二个栈插入
        //判断是否满栈
        if(obj->stack2.top == obj->stack2.capacity)
        {
            obj->stack2.capacity = (obj->stack2.capacity == 0 ? 4 : obj->stack2.capacity * 2);
             StackDAtaType *tmp =  (StackDAtaType*)realloc(obj->stack2.data, sizeof(StackDAtaType) * obj->stack2.capacity);
             if (tmp == NULL)
             {
                 perror("realloc");
                 return ;
             }
             obj->stack2.data = tmp;
        }
        obj->stack2.data[obj->stack2.top++] = x;
    }
}

int myQueuePop(MyQueue* obj)
{
    if (!obj->stack2.top && !obj->stack1.top)
        return 0;
        //判断是否满栈
    if (obj->stack1.top == obj->stack1.capacity)
    {
        obj->stack1.capacity = (obj->stack1.capacity == 0 ? 4 : obj->stack1.capacity * 2);
        StackDAtaType* tmp = (StackDAtaType*)realloc(obj->stack1.data, sizeof(StackDAtaType) * obj->stack1.capacity);
        if (tmp == NULL)
        {
            perror("realloc");
            return 0;
        }
        obj->stack1.data = tmp;
    }
    //判断是否满栈
    if (obj->stack2.top == obj->stack2.capacity)
    {
        obj->stack2.capacity = (obj->stack2.capacity == 0 ? 4 : obj->stack2.capacity * 2);
        StackDAtaType* tmp = (StackDAtaType*)realloc(obj->stack2.data, sizeof(StackDAtaType) * obj->stack2.capacity);
        if (tmp == NULL)
        {
            perror("realloc");
            return 0;
        }
        obj->stack2.data = tmp;
    }
    int a = 1;
    if (obj->stack2.top)
    {
        
        //取出第二栈的元素 插入到第一栈
        while (obj->stack2.top > a)
        {
            obj->stack1.data[obj->stack1.top] = obj->stack2.data[a++];
            obj->stack1.top++;

        }
        obj->stack2.top = 0;
        return obj->stack2.data[obj->stack2.top];
    }
    else
    {
        //取出第一栈的元素 插入到第二栈
        while (obj->stack1.top > a)
        {
  
            obj->stack2.data[obj->stack2.top++] = obj->stack1.data[a++];

        }
        obj->stack1.top = 0;
        return obj->stack1.data[obj->stack1.top];

    }

}

int myQueuePeek(MyQueue* obj) 
{
    if(!obj->stack2.top && !obj->stack1.top)
        return 0;
    if(obj->stack2.top)
    {
        return obj->stack2.data[0];
    }
    else
    {
       return obj->stack1.data[0];

    }
    
}

bool myQueueEmpty(MyQueue* obj) 
{
    return obj->stack1.top == 0 && obj->stack2.top == 0;
}

void myQueueFree(MyQueue* obj) 
{
    free(obj->stack1.data);
    obj->stack1.data = NULL;
    obj->stack1.top = 0;
    obj->stack1.capacity = 0;

    free(obj->stack2.data);
    obj->stack2.data = NULL;
    obj->stack2.top = 0;
    obj->stack2.capacity = 0;
    free(obj);

}

    • 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
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162

    总结

    这些题目主要还是考察我们对队列和栈的熟悉程度

    ​

  • 相关阅读:
    Apache Commons FileUpload框架的简介说明
    svn使用（上传自己的项目到svn上）
    当前读和快照读
    Mysql创建账号并且赋予权限
    MacOS安装git
    网络部署思路、路由器以及静态路由协议
    C++单调向量算法：132模式枚举1简洁版
    项目一：使用 Spring + SpringMVC + Mybatis + lombok 实现网络五子棋
    Paparazzi: Surface Editing by way of Multi-View Image Processing
    申报国家高新技术企业有什么好处？
  • 原文地址：https://blog.csdn.net/m0_69984273/article/details/134409110