数据结构探险系列—栈篇-学习笔记

作者: 天涯明月笙 | 来源:发表于2017-09-03 14:43 被阅读285次

数据结构探险—栈篇

什么是栈？
古代栈就是牲口棚的意思。

栈是一种机制：后进先出 LIFO（last in first out）

电梯

栈要素

空栈。栈底，栈顶。没有元素的时候，栈顶和栈底指向同一个元素，如果加入新元素，栈顶不断升高。取出数据时栈顶不断地降低。栈顶和栈底都称之为栈要素。

通过demo说明栈的基本原理
热身运动-进制转换：十进制转换到二进制，八进制，十六进制

N = (N div d) * d + N mod d

步步为营- 括号匹配检测：检测一个字符串中的各种括号是否匹配

[()]  [()()]  [()[()]]

实例介绍

栈要求

mystack.h:

#ifndef MYSTACK_H
#define MYSTACK_H
class MyStack
{
public:
    MyStack(int size);      //分配内存初始化栈空间，设定栈容量，栈顶
    ~MyStack();             //回收栈空间内存
    bool stackEmpty();      //判断栈是否为空
    bool stackFull();       //判断栈是否为满
    void clearStack();      //清空栈
    int stackLength();      //栈中元素的个数
    bool push(char elem);   //将元素压入栈中，栈顶上升
    bool pop(char &elem);   //将元素推出栈，栈顶下降
    void stackTraverse(bool isFromButtom);  //遍历栈中元素并输出
private:
    int m_iTop;             //栈顶，栈中元素个数
    int m_iSize;            //栈容量
    char *m_pBuffer;        //栈空间指针
};


#endif

mystack.cpp:

#include "Mystack.h"
#include <iostream>
using namespace std;

MyStack::MyStack(int size)
{
    m_iSize = size;
    m_pBuffer = new char[size];
    m_iTop = 0;
}
MyStack::~MyStack()
{
    delete[]m_pBuffer;
    m_pBuffer = NULL;
    
}
bool MyStack::stackEmpty()
{
    if (m_iTop == 0)//if(0 == m_iTop)
    {
        return true;
    }
    else
    {
        return false;
    }
}
bool MyStack::stackFull()
{
    if ( m_iTop == m_iSize)//>=
    {
        return true;
    }
    else
    {
        return false;
    }
}

void MyStack::clearStack()
{
    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;
}
bool MyStack::pop(char &elem)
{
    if (stackEmpty())
    {
        return false;
    }
    m_iTop--;//因为入栈时做了++，使栈顶指向下一个空位置
    elem = m_pBuffer[m_iTop];
    return true;
}

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

void MyStack::stackTraverse(bool isFromButtom)
{
    if (isFromButtom)
    {
        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] << ",";
        }
    }
    
}

main.cpp:

#include "Mystack.h"
#include <iostream>
#include <stdlib.h>
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->clearStack();
    pStack->stackTraverse(false);

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



    delete pStack;
    pStack = NULL;
    system("pause");
    return 0;
}

运行结果：

栈运行结果

案例改造。

要求：

栈改造要求

#ifndef MYSTACK_H
#define MYSTACK_H
#include "Coordinate.h"
class MyStack
{
public:
    MyStack(int size);      //分配内存初始化栈空间，设定栈容量，栈顶
    ~MyStack();             //回收栈空间内存
    bool stackEmpty();      //判断栈是否为空
    bool stackFull();       //判断栈是否为满
    void clearStack();      //清空栈
    int stackLength();      //栈中元素的个数
    bool push(Coordinate elem); //将元素压入栈中，栈顶上升
    bool pop(Coordinate &elem); //将元素推出栈，栈顶下降
    void stackTraverse(bool isFromButtom);  //遍历栈中元素并输出
private:
    int m_iTop;             //栈顶，栈中元素个数
    int m_iSize;            //栈容量
    Coordinate *m_pBuffer;      //栈空间指针
};
#endif

#include "Mystack.h"
#include <iostream>
using namespace std;

MyStack::MyStack(int size)
{
    m_iSize = size;
    m_pBuffer = new Coordinate[size];
    m_iTop = 0;
}
MyStack::~MyStack()
{
    delete[]m_pBuffer;
    m_pBuffer = NULL;
    
}
bool MyStack::stackEmpty()
{
    if (m_iTop == 0)//if(0 == m_iTop)
    {
        return true;
    }
    else
    {
        return false;
    }
}
bool MyStack::stackFull()
{
    if ( m_iTop == m_iSize)//>=
    {
        return true;
    }
    else
    {
        return false;
    }
}

void MyStack::clearStack()
{
    m_iTop = 0;//原栈中所有值无效
}

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

bool MyStack::push(Coordinate elem)//放入栈顶
{
    if (stackFull())
    {
        return false;
    }
    m_pBuffer[m_iTop] = elem;
    //因为这里的coordinate是一个简单的复制。所以使用默认拷贝函数就可以了
    m_iTop++;
    return true;
}
bool MyStack::pop(Coordinate &elem)
{
    if (stackEmpty())
    {
        return false;
    }
    m_iTop--;//因为入栈时做了++，使栈顶指向下一个空位置
    elem = m_pBuffer[m_iTop];
    return true;
}

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

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

#ifndef COORDINATE_H
#define COORDINATE_H
class Coordinate
{
public:
    Coordinate(int x=0,int y=0);
    void printCoordinate();
private:
    int m_iX;
    int m_iY;
};
#endif

#include "Coordinate.h"
#include <iostream>
using namespace std;

Coordinate::Coordinate(int x, int y)
{
    m_iX = x;
    m_iY = y;
}
void Coordinate::printCoordinate()
{
    cout << "(" << m_iX << "," << m_iY << ")" << endl;
}

main.cpp:

#include "Mystack.h"
#include <iostream>
#include <stdlib.h>
using namespace std;
int main(void)
{
    MyStack *pStack = new MyStack(5);

    pStack->push(Coordinate(1,2));//底
    pStack->push(Coordinate(3, 4));

    pStack->stackTraverse(true);
    
    pStack->stackTraverse(false);

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

    delete pStack;
    pStack = NULL;
    system("pause");
    return 0;
}

运行结果：

改造后运行结果

经过改造我们使栈满足了coordinate对象的入栈出栈。

将普通栈改为类模板栈。使其可以适用于任何数据类型

类模板栈实现要求

上面我们实现过两遍对于栈的实现。一次是实现char数组的栈。一次是实现coordinate对象的。两次除过数据类型。差别不是很大。所以本次我们使用类模板实现适用任何数据类型的栈

mystack.h:(因为编译器不支持类模板分开编译。所以cpp为空)

#ifndef MYSTACK_H
#define MYSTACK_H
#include <iostream>
using namespace std;
template <typename T>
class MyStack
{
public:
    MyStack(int size);      //分配内存初始化栈空间，设定栈容量，栈顶
    ~MyStack();             //回收栈空间内存
    bool stackEmpty();      //判断栈是否为空
    bool stackFull();       //判断栈是否为满
    void clearStack();      //清空栈
    int stackLength();      //栈中元素的个数
    bool push(T elem);  //将元素压入栈中，栈顶上升
    bool pop(T &elem);  //将元素推出栈，栈顶下降
    void stackTraverse(bool isFromButtom);  //遍历栈中元素并输出
private:
    int m_iTop;             //栈顶，栈中元素个数
    int m_iSize;            //栈容量
    T *m_pBuffer;       //栈空间指针
};

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

}
template <typename T>
bool MyStack<T>::stackEmpty()
{
    if (m_iTop == 0)//if(0 == m_iTop)
    {
        return true;
    }
    else
    {
        return false;
    }
}
template <typename T>
bool MyStack<T>::stackFull()
{
    if (m_iTop == m_iSize)//>=
    {
        return true;
    }
    else
    {
        return false;
    }
}
template <typename T>
void MyStack<T>::clearStack()
{
    m_iTop = 0;//原栈中所有值无效
}
template <typename T>
int MyStack<T>::stackLength()
{
    return m_iTop;
}
template <typename T>
bool MyStack<T>::push(T elem)//放入栈顶
{
    if (stackFull())
    {
        return false;
    }
    m_pBuffer[m_iTop] = elem;
    //因为这里的coordinate是一个简单的复制。所以使用默认拷贝函数就可以了
    m_iTop++;
    return true;
}
template <typename T>
bool MyStack<T>::pop(T &elem)
{
    if (stackEmpty())
    {
        return false;
    }
    m_iTop--;//因为入栈时做了++，使栈顶指向下一个空位置
    elem = m_pBuffer[m_iTop];
    return true;
}

//char MyStack::pop()
//{
//  if (stackEmpty())
//  {
//      throw 1;
//  }
//  else
//  {
//      m_iTop--;
//      return m_pBuffer[m_iTop];
//  }
//}
template <typename T>
void MyStack<T>::stackTraverse(bool isFromButtom)
{
    if (isFromButtom)
    {
        for (int i = 0; i < m_iTop; i++)
        {
            cout << m_pBuffer[i];
            //m_pBuffer[i].printCoordinate();
        }
    }
    else
    {
        for (int i = m_iTop - 1; i >= 0; i--)
        {
            cout << m_pBuffer[i];
            //m_pBuffer[i].printCoordinate();
        }
    }

}
#endif

#ifndef COORDINATE_H
#define COORDINATE_H
#include <ostream>
using namespace std;
class Coordinate
{
    friend ostream &operator<<(ostream &out, Coordinate &coor);
public:
    Coordinate(int x=0,int y=0);
    void printCoordinate();
private:
    int m_iX;
    int m_iY;
};
#endif


#include "Coordinate.h"
#include <iostream>
using namespace std;

Coordinate::Coordinate(int x, int y)
{
    m_iX = x;
    m_iY = y;
}
void Coordinate::printCoordinate()
{
    cout << "(" << m_iX << "," << m_iY << ")" << endl;
}

ostream &operator<<(ostream &out, Coordinate &coor)
{
    out << "(" << coor.m_iX << "," << coor.m_iY << ")" << endl;
    return out;
}

main.cpp:

#include "Mystack.h"
#include <iostream>
#include <stdlib.h>
#include "Coordinate.h"
using namespace std;
int main(void)
{
    MyStack<Coordinate> *pStack = new MyStack<Coordinate>(5);

    pStack->push(Coordinate(1,2));//底
    pStack->push(Coordinate(3, 4));

    pStack->stackTraverse(true);
    
    pStack->stackTraverse(false);

    cout << pStack->stackLength() << endl;
    MyStack<char> *pStack2 = new MyStack<char>(5);

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

    pStack2->stackTraverse(true);
    delete pStack;
    pStack = NULL;
    system("pause");
    return 0;
}

类模板栈运行结果

可以看到我们的类模板已经将栈改造成了通用数据类型的栈。

栈应用-进制转换

进制转换

短除法。不停除以进制数。保留余数。然后商继续除以进制保留余数。直到商为0
栈的应用：将每次的余数4 0 5 2 入栈。然后从栈顶开始打印。

#ifndef MYSTACK_H
#define MYSTACK_H
#include <iostream>
using namespace std;
template <typename T>
class MyStack
{
public:
    MyStack(int size);      //分配内存初始化栈空间，设定栈容量，栈顶
    ~MyStack();             //回收栈空间内存
    bool stackEmpty();      //判断栈是否为空
    bool stackFull();       //判断栈是否为满
    void clearStack();      //清空栈
    int stackLength();      //栈中元素的个数
    bool push(T elem);  //将元素压入栈中，栈顶上升
    bool pop(T &elem);  //将元素推出栈，栈顶下降
    void stackTraverse(bool isFromButtom);  //遍历栈中元素并输出
private:
    int m_iTop;             //栈顶，栈中元素个数
    int m_iSize;            //栈容量
    T *m_pBuffer;       //栈空间指针
};

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

}
template <typename T>
bool MyStack<T>::stackEmpty()
{
    if (m_iTop == 0)//if(0 == m_iTop)
    {
        return true;
    }
    else
    {
        return false;
    }
}
template <typename T>
bool MyStack<T>::stackFull()
{
    if (m_iTop == m_iSize)//>=
    {
        return true;
    }
    else
    {
        return false;
    }
}
template <typename T>
void MyStack<T>::clearStack()
{
    m_iTop = 0;//原栈中所有值无效
}
template <typename T>
int MyStack<T>::stackLength()
{
    return m_iTop;
}
template <typename T>
bool MyStack<T>::push(T elem)//放入栈顶
{
    if (stackFull())
    {
        return false;
    }
    m_pBuffer[m_iTop] = elem;
    //因为这里的coordinate是一个简单的复制。所以使用默认拷贝函数就可以了
    m_iTop++;
    return true;
}
template <typename T>
bool MyStack<T>::pop(T &elem)
{
    if (stackEmpty())
    {
        return false;
    }
    m_iTop--;//因为入栈时做了++，使栈顶指向下一个空位置
    elem = m_pBuffer[m_iTop];
    return true;
}

//char MyStack::pop()
//{
//  if (stackEmpty())
//  {
//      throw 1;
//  }
//  else
//  {
//      m_iTop--;
//      return m_pBuffer[m_iTop];
//  }
//}
template <typename T>
void MyStack<T>::stackTraverse(bool isFromButtom)
{
    if (isFromButtom)
    {
        for (int i = 0; i < m_iTop; i++)
        {
            cout << m_pBuffer[i];
            //m_pBuffer[i].printCoordinate();
        }
    }
    else
    {
        for (int i = m_iTop - 1; i >= 0; i--)
        {
            cout << m_pBuffer[i];
            //m_pBuffer[i].printCoordinate();
        }
    }

}
#endif

#include "Mystack.h"
#include <iostream>
#include <stdlib.h>
using namespace std;

#define BINARY 2
#define OCTONARY 8
#define HEXADECIMAL 16

int main(void)
{
    MyStack<int> *pStack = new MyStack<int>(30);
    int N = 1348;
    int mod = 0;
    while (N !=0)
    {
        mod = N % BINARY;
        pStack->push(mod);
        N = N / BINARY;
    }
    pStack->stackTraverse(false);

    delete pStack;
    pStack = NULL;
    system("pause");
    return 0;
}

二进制和8进制都没有问题了，16进制还需要进一步改造。

运行结果：

!运行结果](https://img.haomeiwen.com/i1779926/c6c62f86ff27da42.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

16进制改造

mystack.h与原来一致。

#include "Mystack.h"
#include <iostream>
#include <stdlib.h>
using namespace std;

#define BINARY 2
#define OCTONARY 8
#define HEXADECIMAL 16

int main(void)
{
    char num[] = "0123456789ABCDEF";
    MyStack<char> *pStack = new MyStack<char>(30);
    int N = 2016;
    int mod = 0;
    while (N !=0)
    {
        mod = N % HEXADECIMAL;
        pStack->push(num[mod]);
        N = N / HEXADECIMAL;
    }
    pStack->stackTraverse(false);
    /*for (int i=pStack->stackLength()-1;i>=0;i--)
    {
        num[pStack[i]]
    }*/
    /*int elem = 0;
    while (!pStack->stackEmpty())
    {
        pStack->pop(elem);
        cout << num[elem];
    }*/
    

    delete pStack;
    pStack = NULL;
    system("pause");
    return 0;
}

如果仍使栈为int型。则可以使用注释部分打印出内容。修改为char之后。可使用
pStack->push(num[mod]);

栈应用括号匹配

括号匹配

从前往后扫描。左方括号入栈，左圆括号入栈，当遇到右括号则左圆括号出栈。当遇到右方括号，左方括号出栈。字符串扫描完毕时栈为空则全部匹配。栈中还有东西则不是全部匹配

#include "Mystack.h"
#include <iostream>
#include <stdlib.h>
using namespace std;

int main(void)
{
    MyStack<char> *pStack = new MyStack<char>(30);//已存入的字符

    MyStack<char> *pNeedStack = new MyStack<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])//对于这个字符，生成它的currentneed
            {
            case '[':
                if (currentNeed !=0)//如果currentneed已经有值，不为初值。
                {
                    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;
    }
    delete pStack;
    pStack = NULL;
    delete pNeedStack;
    pNeedStack = NULL;
    system("pause");
    return 0;
}

运行过程：

最开始：currentneed为0.

str[0]为"[",此时需要的currentneed为0，不相等。
进入if内部。将"[" 存入栈1。进入switch的case内部。匹配到case:"["
此时判断到当前的currentneed = 0.不满足if。则生成currentneed "]"。并break
出循环。
str[1]为"（"，此时需要的currentneed是"]"，不相等。
进入if内部将"("存入栈1.进入switch的case内部。匹配到case："("
此时判断到当前的currentneed ="]"不等于0.将该字符存入需要栈，因为下面就要对他进行覆盖了、
生成新的的currentneed")"，并break出循环
str[2]为")"，正好与我们当前的currentneed一致。
那么我们将栈一的"("弹出。并将needstack里的上一个急需的赋值给currentneed。
进入下一次循环。

也就是currentneed变量里面存放的是当前下一次循环刚开始急需匹配的。
need栈里存放的是历史需要的。

当当前需要的和正在扫描的一致。则将栈1中出栈。

数据结构探险系列—栈篇-学习笔记

数据结构探险—栈篇

实例介绍

案例改造。

将普通栈改为类模板栈。使其可以适用于任何数据类型

栈应用-进制转换

16进制改造

栈应用括号匹配

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

数据结构与算法

C语言

程序员

C++

数据结构

c++