stack-栈的学习笔记

栈是一种后进先出的数据结构(Last in First out LIFO)，只能在一端进行插入和删除操作。

常见的用处：判断回文字符串，检验括号匹配

做过的题目：CDUT OJ 1143

借助栈判断回文字符串

#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
    char a[101],s[101];
    int i,len,mid,next,top;

//    读入一行字符串
    gets(a);
//    求字符串长度
    len = strlen(a);
//    求字符串中点之前的位置（入栈终点）
    mid = len / 2 - 1;

//    初始化栈
    top = 0;

//    将mid前依次入栈
    for(i = 0;i <= mid;i++)
        s[++top] = a[i];

//    判断字符串长度是奇数还是偶数 找出需要进行匹配的起始下标
    if(len % 2 == 0)
        next = mid + 1;
    else
        next = mid + 2;

//    开始匹配
    for(i = next;i <= len - 1;i++)
    {
        if(a[i] != s[top])
            break;
        top--;
    }

//    若top为0说明全部匹配顺利循环结束
    if(top == 0)
        printf("YES");
    else
        printf("NO");

    getchar();//利用getchar()函数让程序调试运行结束后等待编程者按下键盘才返回编辑界面
    return 0;
}
           

借助栈实现括号匹配的检验

#include <iostream>
#include <stack>
#include <string>
using namespace std;
stack<char> mystack;
bool checksymbol = 1;

bool check(char a)
{
    switch(a)
    {
        //左括号入栈
        case '{':
            mystack.push(a);
            break;
        case '(':
            mystack.push(a);
            break;
        case '[':
            mystack.push(a);
            break;
//右括号与栈顶元素比较
//匹配 删除栈顶元素 不匹配 表达式括号有问题
        case '}':
            {
                if(mystack.top() != '{')
                    checksymbol = 0;
                else
                    mystack.pop();
                break;
            }
        case ')':
            {
                if(mystack.top() != '(')
                    checksymbol = 0;
                else
                    mystack.pop();
                break;
            }
        case ']':
            {
                if(mystack.top() != '[')
                    checksymbol = 0;
                else
                    mystack.pop();
                break;
            }
    }
}

int main()
{
    //给定需要判断的表达式
    string s;
    cin>>s;
    //判断函数
    int length = s.length();
    for(int i = 0;i < length;i++)
    {
        check(s[i]);
    }
//到最后栈为空 表达式括号没问题
    if(!mystack.empty())//stack为空返回1 不空返回0
        checksymbol = 0;

    if(checksymbol == 1)
        cout<<"YES";
    else
        cout<<"NO";

    return 0;
}