博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
数据结构探险系列—栈篇-学习笔记
阅读量：6249 次
发布时间：2019-06-22

本文共 14028 字，大约阅读时间需要 46 分钟。

数据结构探险—栈篇

什么是栈？

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

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

电梯

栈要素

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

  • 通过demo说明栈的基本原理
  • 热身运动-进制转换：十进制转换到二进制，八进制，十六进制
N = (N div d) * d + N mod d
  • 步步为营- 括号匹配检测：检测一个字符串中的各种括号是否匹配
[()]  [()()]  [()[()]]

实例介绍

栈要求

mystack.h:

#ifndef MYSTACK_H#define MYSTACK_Hclass 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 
     
      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 
     
      #include 
      
       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 
     
      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_Hclass Coordinate{public:    Coordinate(int x=0,int y=0);    void printCoordinate();private:    int m_iX;    int m_iY;};#endif#include "Coordinate.h"#include 
     
      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 
     
      #include 
      
       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 
     
      using namespace std;template 
      
       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 
       
        MyStack
        
         ::MyStack(int size){    m_iSize = size;    m_pBuffer = new T[size];    m_iTop = 0;}template 
         
          MyStack
          
           ::~MyStack(){ delete[]m_pBuffer; m_pBuffer = NULL;}template 
           
            bool MyStack
            
             ::stackEmpty(){ if (m_iTop == 0)//if(0 == m_iTop) { return true; } else { return false; }}template 
             
              bool MyStack
              
               ::stackFull(){ if (m_iTop == m_iSize)//>= { return true; } else { return false; }}template 
               
                void MyStack
                
                 ::clearStack(){ m_iTop = 0;//原栈中所有值无效}template 
                 
                  int MyStack
                  
                   ::stackLength(){ return m_iTop;}template 
                   
                    bool MyStack
                    
                     ::push(T elem)//放入栈顶{ if (stackFull()) { return false; } m_pBuffer[m_iTop] = elem; //因为这里的coordinate是一个简单的复制。所以使用默认拷贝函数就可以了 m_iTop++; return true;}template 
                     
                      bool MyStack
                      
                       ::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 
                       
                        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(); } }}#endif
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
#ifndef COORDINATE_H#define COORDINATE_H#include 
     
      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 
      
       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 
     
      #include 
      
       #include "Coordinate.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;    MyStack
         
           *pStack2 = new MyStack
          
           (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 
     
      using namespace std;template 
      
       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 
       
        MyStack
        
         ::MyStack(int size){    m_iSize = size;    m_pBuffer = new T[size];    m_iTop = 0;}template 
         
          MyStack
          
           ::~MyStack(){ delete[]m_pBuffer; m_pBuffer = NULL;}template 
           
            bool MyStack
            
             ::stackEmpty(){ if (m_iTop == 0)//if(0 == m_iTop) { return true; } else { return false; }}template 
             
              bool MyStack
              
               ::stackFull(){ if (m_iTop == m_iSize)//>= { return true; } else { return false; }}template 
               
                void MyStack
                
                 ::clearStack(){ m_iTop = 0;//原栈中所有值无效}template 
                 
                  int MyStack
                  
                   ::stackLength(){ return m_iTop;}template 
                   
                    bool MyStack
                    
                     ::push(T elem)//放入栈顶{ if (stackFull()) { return false; } m_pBuffer[m_iTop] = elem; //因为这里的coordinate是一个简单的复制。所以使用默认拷贝函数就可以了 m_iTop++; return true;}template 
                     
                      bool MyStack
                      
                       ::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 
                       
                        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(); } }}#endif#include "Mystack.h"#include 
                         
                          #include 
                          
                           using namespace std;#define BINARY 2#define OCTONARY 8#define HEXADECIMAL 16int main(void){ MyStack
                           
                             *pStack = new MyStack
                            
                             (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进制还需要进一步改造。

运行结果：

!运行结果]()

16进制改造

mystack.h与原来一致。

#include "Mystack.h"#include 
     
      #include 
      
       using namespace std;#define BINARY 2#define OCTONARY 8#define HEXADECIMAL 16int main(void){    char num[] = "0123456789ABCDEF";    MyStack
       
         *pStack = new MyStack
        
         (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 
     
      #include 
      
       using namespace std;int main(void){    MyStack
       
         *pStack = new MyStack
        
         (30);//已存入的字符    MyStack
         
           *pNeedStack = new MyStack
          
           (30);//需要的字符。 char str[] = "[()]]"; char currentNeed = 0; for (int i=0;i
           
            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中出栈。

转载地址：http://nngia.baihongyu.com/

你可能感兴趣的文章
Spring Cloud实战系列(八) - 微服务监控Spring Boot Admin
查看>>
MySql相关语句总结
查看>>
史上最全面的React-react基础
查看>>
聊聊Git原理
查看>>
如何评价Normalize.css
查看>>
CSS实现元素居中原理解析
查看>>
React 快速上手 - 08 redux 状态管理 react-redux
查看>>
当程序员有了中年危机 你会发现你就是个屁
查看>>
关于同步的一点思考-上
查看>>
阿里云函数计算
查看>>
Java 10 新特性全览
查看>>
你真的会正确使用断言吗？
查看>>
Android点将台：济世儒侠[-ContentProvider-]
查看>>
java基础学习：JavaWeb之Cookie和Session
查看>>
骨架屏（Skeleton Screen）在Android中的应用
查看>>
Spring源码分析（三）手写简单的IOC容器和解决循环依赖问题
查看>>
MySQL索引笔记
查看>>
vue-router 嵌套路由
查看>>
java注解基础与使用
查看>>
Java 8中的Optional: 如何正确使用？
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2025-01-09 02:53:41   当前IP: 18.218.27.145   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我