数据结构基础——栈的C++实现

一、存储基本数据类型的栈的实现1、创建文件MyStatck.h#ifndef MYSTATCK_H#define MYSTATCK_Hclass MyStatck{public:MyStatck(int size);~MyStatck();bool statckEmpty()const;bool statckFull()const ;

Lavi_qq_2910138025

1873人浏览 · 2016-09-15 23:15:14

Lavi_qq_2910138025 · 2016-09-15 23:15:14 发布

一、存储基本数据类型的栈的实现

1、创建文件MyStatck.h

#ifndef MYSTATCK_H
#define MYSTATCK_H
class MyStatck{
public:
    MyStatck(int size);
    ~MyStatck();
    bool statckEmpty()const;
    bool statckFull()const ;
    int statckLen();
    void clearStatck();
    bool push(char element);
    bool pop(char &element);
    void statckTraverse();
private:
    char *m_pstatck;
    int m_iTop;
    int m_iSize;

};
#endif // MYSTATCK_H

2、创建文件MyStatck.cpp

#include "MyStatck.h"
#include <iostream>
using namespace std;
MyStatck::MyStatck(int size){
    m_pstatck = new char[size];
    m_iSize = size;
    m_iTop = 0;
}
MyStatck::~MyStatck(){
    delete[] m_pstatck;
    m_pstatck = NULL;
}

bool MyStatck::statckFull()const{
    return m_iTop == m_iSize ? true:false;
}
bool MyStatck::statckEmpty()const{
    return m_iTop == 0 ? true:false;
}
void MyStatck::clearStatck(){
    m_iTop = 0;
}
int MyStatck::statckLen(){
    return m_iTop;
}
bool MyStatck::push(char element){
    if(statckFull())
        return false;
    m_pstatck[m_iTop] = element;
    m_iTop++;
    return true;
}
bool MyStatck::pop(char &element){
    if(statckEmpty())
        return false;
    m_iTop--;
    element = m_pstatck[m_iTop];
    return true;
}
void MyStatck::statckTraverse(){
    cout<<"开始遍历-----------------------------"<<endl;
    for(int i = 0 ;i < m_iTop;i++){
        cout<<m_pstatck[i]<<endl;
    }
    cout<<"结束遍历-----------------------------"<<endl;
}

3、在main函数写入如下代码测试定义的栈是否正确

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

int main()
{
    MyStatck *p = new MyStatck(5);
    p->push('h');
    p->push('e');
    p->push('l');
    p->push('l');
    p->push('o');
    p->statckTraverse();
    char elem;
    p->pop(elem);
    cout<<elem<<endl;
    p->statckTraverse();
    /**注意此处是delete p    不能写成delete[] p**/
    delete p;
    p = NULL;
    return 0;
}

二、定义栈模板

1、创建文件MyStatck.h

#ifndef MYSTATCK_H
#define MYSTATCK_H
#include <iostream>
using namespace std;
template <typename T>
class MyStatck{
public:
    MyStatck(int size);
    ~MyStatck();
    bool statckEmpty()const;
    bool statckFull()const ;
    int statckLen();
    void clearStatck();
    bool push(T element);
    bool pop(T &element);
    void statckTraverse();
private:
    T *m_pstatck;
    int m_iTop;
    int m_iSize;

};
/**类模板的定义和实现放在一起可能会出现问题，所以在此将定义和实现放在一起**/
template <typename T> //每个成员函数的上方都要加这段代码
MyStatck<T>::MyStatck(int size){
    m_pstatck = new T[size];
    m_iSize = size;
    m_iTop = 0;
}

template <typename T>
MyStatck<T>::~MyStatck(){
    delete[] m_pstatck;
    m_pstatck = NULL;
}

template <typename T>
bool MyStatck<T>::statckFull()const{
    return m_iTop == m_iSize ? true:false;
}

template <typename T>
bool MyStatck<T>::statckEmpty()const{
    return m_iTop == 0 ? true:false;
}

template <typename T>
void MyStatck<T>::clearStatck(){
    m_iTop = 0;
}

template <typename T>
int MyStatck<T>::statckLen(){
    return m_iTop;
}

template <typename T>
bool MyStatck<T>::push(T element){
    if(statckFull())
        return false;
    m_pstatck[m_iTop] = element;
    m_iTop++;
    return true;
}

template <typename T>
bool MyStatck<T>::pop(T &element){
    if(statckEmpty())
        return false;
    m_iTop--;
    element = m_pstatck[m_iTop];
    return true;
}

template <typename T>
void MyStatck<T>::statckTraverse(){
    cout<<"开始遍历-----------------------------"<<endl;
    for(int i = 0 ;i < m_iTop;i++){
        cout<<m_pstatck[i]<<endl;
    }
    cout<<"结束遍历-----------------------------"<<endl;
}
#endif // MYSTATCK_H

2、创建文件 Coordinate.h

#ifndef COORDINATE_H
#define COORDINATE_H
#include <ostream>
/**
使用ostream，istream，iostream一定要引入std命名空间否则会找不到类型
**/
using namespace std;
class Coordinate{
    /**运算符一般重载为友元函数，输入输出运算符重载的返回值的类型和参数类型都是引用**/
    friend ostream &operator<<(ostream &out,Coordinate &coor);
public:
    Coordinate(int x=0,int y=0);
    void printInfo();
private:
    int m_iX;
    int m_iY;
};
#endif // COORDINATE_H

3、创建文件Coordinate.cpp

#include "Coordinate.h"
#include <iostream>
using namespace std;
Coordinate::Coordinate(int x,int y){
    m_iX = x;
    m_iY = y;
}
void Coordinate::printInfo(){
    cout<<"("<<m_iX<<","<<m_iY<<")"<<endl;
}
/**注意输出运算符的重载**/
ostream &operator<<(ostream &out,Coordinate &coor){
    out<<"("<<coor.m_iX<<","<<coor.m_iY<<")"<<endl;
    return out;
}

5、测试定义的栈模板，并使用栈完成进制转换和检查括号是否匹配

#include <iostream>
#include <cstring>
#include "MyStatck.h"
#include "Coordinate.h"
#define BINARY 2
#define OCTONARY 8
#define HEXADECTMAL 16
using namespace std;
/**栈应用一：完成进制转换**/
void jinZhiZhuanHuan(int n,int jinZhi){
    char num[] = "0123456789ABCDEF";
    MyStatck<int> *p = new MyStatck<int>(30);
    int mod = 0;
    while(n != 0){
        mod = n % jinZhi;
        p->push(mod);
        n = n / jinZhi;
    }
    int elem = 0;
    while(!p->statckEmpty()){

        p->pop(elem);
        cout<<num[elem];
    }
    cout<<endl;
    delete p;
    p = NULL;
}
/**栈应用二：判断括号是否匹配**/
void piPeiKuohao(){
    //char str[] = "[()]";
    //char str[] = "[[()]";
    char str[] = "[()]]";
    //char str[] = "[([(]]))";
    MyStatck<char> *p = new MyStatck<char>(30);
    for(int i = 0;i < strlen(str);i++){
        char elem = 0;
        switch(str[i]){
            case '[':
                p->push(str[i]);
                break;
            case '(':
                p->push(str[i]);
                break;
            case ')':
                p->pop(elem);
                if(elem != '('){
                    cout<<"括号不匹配"<<endl;
                    return;
                }
                break;
            case ']':
                p->pop(elem);
                if(elem != '['){
                    cout<<"括号不匹配"<<endl;
                    return;
                }
                break;
            default:
                cout<<"default"<<endl;
                break;
        }
    }
    if(p->statckEmpty()){
        cout<<"括号匹配"<<endl;
    }else{
        cout<<"括号不匹配"<<endl;
    }

}
int main()
{
    MyStatck<Coordinate> *p = new MyStatck<Coordinate>(5);
    p->push(Coordinate(1,2));
    p->push(Coordinate(3,4));
    p->push(Coordinate(5,6));

    p->statckTraverse();

    Coordinate c(0,0);
    p->pop(c);
    c.printInfo();
    p->statckTraverse();
    delete p;
    p = NULL;
    /**栈应用一：完成进制转换**/
    jinZhiZhuanHuan(1348,OCTONARY);
    /**栈应用二：判断括号是否匹配**/
    piPeiKuohao();
    return 0;
}

DAMO开发者矩阵

DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。

更多推荐

宇树 Go2 + NaVILA 全栈导航系统详解 (新手入门版)

本文详细介绍了宇树Go2机器人搭配NaVILA全栈导航系统的技术架构与实现方案。系统采用分层设计，包含仿真环境(Go2描述与Gazebo模拟)、底层控制(quadropted_controller)、导航定位(Nav2+Cartographer)和核心VLA(视觉语言动作)模块。重点对比了官方NaVILA方案(依赖高性能GPU)与优化后的轻量化方案(基于llama.cpp的Client-Serve

DAMO开发者矩阵

【路径规划】基于Fast-RRT二维空间移动机器人改进的运动规划器附Matlab复现含文献

移动机器人路径规划旨在解决从起始状态到目标状态在给定空间内创建无碰撞路径的问题，这是无人作业的关键支撑技术。为解决渐近最优快速扩展随机树星形算法（RRT *算法）存在的收敛速度慢、规划效率低及路径成本高等问题，本文提出了一种基于混合采样策略和回溯选择父节点的改进运动规划器（Fast- RRT *算法）。首先，在采样阶段结合目标偏置策略与约束采样以降低采样盲目性；其次，在选择新节点父节点时，通过追溯