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;
}