数据结构和算法分析Java-Python-Django社区

【慕课-数据结构-C++语言】栈篇

2018-04-22  本文已影响10人  苍云横渡

原文地址：https://www.cloudcrossing.xyz/post/29/

栈的原理

栈，一种机制。栈机制为后进先出（last in first out）。

单一数据类型栈

首先建立一个字符型的栈的。

#MyStack.h
#ifndef MYSTACK_H
#define MYSTACK_H

class MyStack
{
public:
    MyStack(int size);          //分配内存初始化栈空间，设定栈容量，栈顶
    ~MyStack();                 //回收栈空间内存
    bool stackEmpty();          //判断栈空
    bool stackFull();           //判断栈满
    void Cleanstack();          //清空栈
    int stackLength();          //返回已有元素个数
    bool push(char elem);                   //元素入栈，栈顶上升
    bool pop(char &elem);                   //元素出栈，栈顶下降
    void stackTraverse(bool isFromButton);  //遍历栈中所有元素

private:
    char *m_pBuffer;        //栈空间指针
    int m_iSize;            //栈容量
    int m_iTop;             //栈顶，栈中元素个数
};

#endif // MYSTACK_H

#MyStack.cpp
#include "MyStack.h"
#include "iostream"

using namespace std;

MyStack::MyStack(int size)
{
    m_iSize = size;
    m_pBuffer = new char[m_iSize];
    m_iTop = 0;
}

MyStack::~MyStack()
{
    delete []m_pBuffer;
}

bool MyStack::stackEmpty()
{
    return 0 == m_iTop ? true : false;  //m_iTop == 0
}

bool MyStack::stackFull()
{
    return m_iTop == m_iSize ? true : false; 
}

void MyStack::Cleanstack()
{
    m_iTop = 0;
}

int MyStack::stackLength()
{
    return m_iTop;
}

bool MyStack::push(char elem)
{
    if (stackFull())
    {
        return false;
    }
    m_pBuffer[m_iTop] = elem;
    m_iTop++;
    return true;
}

//char MyStack::pop()
//{
//    if (stackEmpty())
//    {
//        throw - 1;
//    }
//    else
//    {
//        m_iTop--;
//        return m_pBuffer[m_iTop];
//    }
//}

bool MyStack::pop(char &elem)
{
    if (stackEmpty())
    {
        return false;
    }
    m_iTop--;
    elem = m_pBuffer[m_iTop];
    return true;
}

void MyStack::stackTraverse(bool isFromButton)
{
    if (isFromButton)
    {
        for (int i = 0; i < m_iTop; i++)
        {
            cout << m_pBuffer[i] << ",";
        }
    }
    else 
    {
        for (int i = m_iTop; i >= 0; i--)
        {
            cout << m_pBuffer[i] << ",";
        }
    } 
}

在这里栈使用数组的方式建立，定义栈底为0，即下标为0的元素；栈顶指向当前数组最后一个元素的下一个位置（NULL）。此时m_iTop可以用来作为栈内元素的个数。

所以当m_iTop为0时表示栈空；当m_iTop等于m_iSize时表示栈满。

#include "stdafx.h"
#include "stdlib.h"
#include "MyStack.h"
#include "iostream"

using namespace std;

int main(void)
{
    MyStack *pStack = new MyStack(5);

    pStack->push('h'); //底
    pStack->push('e');
    pStack->push('l');
    pStack->push('l');
    pStack->push('o'); //顶

    pStack->stackTraverse(true);

    char elem = 0;
    pStack->pop(elem);
    cout << endl;
    cout << elem << endl;

    //pStack->Cleanstack();

    pStack->stackTraverse(true);

    cout << endl;
    cout << pStack->stackLength() << endl;

    if (pStack->stackEmpty())
    {
        cout << "栈为空" << endl;
    }
    if (pStack->stackFull())
    {
        cout << "栈为满" << endl;
    }

    delete pStack;
    pStack = NULL;

    system("pause");
    return 0;
}

运行结果：

栈的类模板

新建MyStack.cpp

#MyStack.cpp
#ifndef MYSTACK_H
#define MYSTACK_H

template <typename T>
class MyStack_tem
{
public:
    MyStack_tem(int size);          //分配内存初始化栈空间，设定栈容量，栈顶
    ~MyStack_tem();                 //回收栈空间内存
    bool stackEmpty();          //判断栈空
    bool stackFull();           //判断栈满
    void Cleanstack();          //清空栈
    int stackLength();          //返回已有元素个数
    bool push(T elem);                   //元素入栈，栈顶上升
    bool pop(T &elem);                   //元素出栈，栈顶下降
    void stackTraverse(bool isFromButton);  //遍历栈中所有元素

private:
    T * m_pBuffer;        //栈空间指针
    int m_iSize;            //栈容量
    int m_iTop;             //栈顶，栈中元素个数
};

template <typename T>
MyStack_tem<T>::MyStack_tem(int size)
{
    m_iSize = size;
    m_pBuffer = new T[m_iSize];
    m_iTop = 0;
}

template <typename T>
MyStack_tem<T>::~MyStack_tem()
{
    delete[]m_pBuffer;
}

template <typename T>
bool MyStack_tem<T>::stackEmpty()
{
    return 0 == m_iTop ? true : false;  //m_iTop == 0
}

template <typename T>
bool MyStack_tem<T>::stackFull()
{
    return m_iTop == m_iSize ? true : false;
}

template <typename T>
void MyStack_tem<T>::Cleanstack()
{
    m_iTop = 0;
}

template <typename T>
int MyStack_tem<T>::stackLength()
{
    return m_iTop;
}

template <typename T>
bool MyStack_tem<T>::push(T elem)
{
    if (stackFull())
    {
        return false;
    }
    m_pBuffer[m_iTop] = elem;
    m_iTop++;
    return true;
}

template <typename T>
bool MyStack_tem<T>::pop(T &elem)
{
    if (stackEmpty())
    {
        return false;
    }
    m_iTop--;
    elem = m_pBuffer[m_iTop];
    return true;
}

template <typename T>
void MyStack_tem<T>::stackTraverse(bool isFromButton)
{
    if (isFromButton)
    {
        for (int i = 0; i < m_iTop; i++)
        {
            cout << m_pBuffer[i];
        }
    }
    else
    {
        for (int i = m_iTop - 1; i >= 0; i--)
        {
            cout << m_pBuffer[i];
        }
    }
}

#endif // MYSTACK_H

栈用例

进制转换

新建 demo_hex.cpp

#demo_hex.cpp
#include "stdafx.h"
#include "stdlib.h"
#include "iostream"
#include "MyStack_tem.h"

#define BIN 2
#define OCT 8
#define HEX 16

using namespace std;

int main(void)
{
    char num[] = "0123456789ABCDEF";

    MyStack_tem<int> *pStack = new MyStack_tem<int>(30);

    int N = 2016; 
    int mod = 0;
    while (N != 0)
    {
        mod = N % HEX;
        pStack->push(mod);
        N = N / HEX;
    }

    //pStack->stackTraverse(false);
    int elem = 0;
    while (!pStack->stackEmpty())
    {
        pStack->pop(elem);
        cout << num[elem];
    }

    delete pStack;
    pStack = NULL;

    system("pause");
    return 0;
}

因为栈内的某一项均为0-15之间的某个数字，而这个数字需要转换为0-F，所以构造了一个存有0-F字符串的数组，让0-15作为下标去访问这个数组，因为0-15本身也是0-F数组的索引。

括号匹配

新建demo_par.cpp

#demo_par.cpp
#include "stdafx.h"
#include "stdlib.h"
#include "iostream"
#include "MyStack_tem.h"

using namespace std;

int main(void)
{
    MyStack_tem<char> *pStack = new MyStack_tem<char>(30);
    MyStack_tem<char> *pNeedStack = new MyStack_tem<char>(30);

    char str[] = "[()]]";

    char currentNeed = 0; //当前需要的字符

    for (int i = 0; i < strlen(str); i++)
    {
        if (str[i] != currentNeed)
        {
            pStack->push(str[i]);
            switch (str[i])
            {
            case '[':
                if (currentNeed != 0)
                {
                    pNeedStack->push(currentNeed);
                }
                currentNeed = ']';
                break;
            case '(':
                if (currentNeed != 0)
                {
                    pNeedStack->push(currentNeed);
                }
                currentNeed = ')';
                break;
            default:
                cout << "字符串括号不匹配" << endl;
                system("pause");
                return 0;
            }
        }
        else
        {
            char elem;
            pStack->pop(elem);
            if (!pNeedStack->pop(currentNeed))
            {
                currentNeed = 0;
            }
        }
    }

    if (pStack->stackEmpty())
    {
        cout << "字符串括号匹配" << endl;
    }
    else
    {
        cout << "字符串括号不匹配" << endl;
        pStack->stackTraverse(false);
    }

    delete pStack;
    pStack = NULL;
    delete pNeedStack;
    pStack = NULL;

    system("pause");
    return 0;
}

以 [ ( ) ] 为例。

第一次循环， [ 入pStack栈成为栈顶，当前需要匹配的currentNeed变为 ] 。

第二次循环，下一项为 ( ，匹配不成功，将其入pStack栈， ( 称为栈顶，修改currentNeed为 ) ，之前的 ] 入pNeedStack栈。

第三次循环，发现是 ) ，与当前pStack栈的栈顶 ( 匹配，所以将栈顶 ( pop出来，将currentNeed修改为pNeedStack.pop()，即 ] 。

第四次循环，发现是其与 currentNeed相等，即其为 ] ，与 [ 匹配成功，所以pStack.pop()，将 [ 出栈。最后判断pStack栈是栈空，输出匹配成功信息。

这里要注意的是，在pNeedStack->pop(currentNeed)的时候，如果执行失败，要将currentNeed赋值为0。

if(!pNeedStack->pop(currentNeed))
{
    currentNeed=0;
}

这里的 if 如果真则currentNeed=0；如果false则pNeedStack->pop(currentNeed)。也就是从pNeedStack这个栈中出栈,而出栈的值赋值给currentNeed。

最后附上一个支持干扰字符的括号匹配。

#demo_par_new.cpp
#include <iostream>
#include "stdafx.h"
#include "stdlib.h"
#include <string>
#include "MyStack_tem.h"

using namespace std;

int main() {
    MyStack_tem<char> *pStack = new MyStack_tem<char>(30);
    int flag = 0;
    char elem;
    char str[] = "[cfg(2sdf*2ds)f]";
    for (int i = 0; i < strlen(str); i++)
    {
        switch (str[i])
        {
        case '(':
        case '[':
            pStack->push(str[i]);
            break;
        case ')':
            if (!pStack->pop(elem))
            {
                flag = 1;
                continue;
            }
            if (elem != '(')
            {
                flag = 1;
            }
            break;
        case ']':
            if (!pStack->pop(elem))
            {
                flag = 1;
                continue;
            }
            if (elem != '[')
            {
                flag = 1;
            }
            break;
        }
    }
    if (!pStack->stackEmpty() || 1 == flag)
    {
        cout << "字符串括号不匹配" << endl;
    }
    else
    {
        cout << "字符串括号匹配" << endl;
    }
    system("pause");
    return 0;
}
上一篇下一篇

猜你喜欢

热点阅读