从零开始学C++之模板(二):类模板、Stack的类模板实现(自定义链栈方式,自定义数组方式)

一、类模板

类模板:将类定义中的数据类型参数化 类模板实际上是函数模板的推广,可以用相同的类模板来组建任意类型的对象集合

(一)、类模板的定义

template  <类型形参表> class  <类名> {     //类说明体  }; template  <类型形参表> <返回类型> <类名> <类型名表>::<成员函数1>(形参表) {     //成员函数定义体  } template  <类型形参表> <返回类型> <类名> <类型名表>::<成员函数2>(形参表) {     //成员函数定义体  } … template  <类型形参表> <返回类型> <类名> <类型名表>::<成员函数n>(形参表) {     //成员函数定义体  }

(二)、使用类模板

类模板的实例化:用具体的数据类型替换模板的参数以得到具体的类(模板类) 模板类也可以实例化为对象 用下列方式创建类模板的实例: 类名 <类型实参表>  对象名称;

对于函数模板与类模板,模板参数并不局限于类型(类类型,基本类型,模板类实例),普通值也可以作为模板参数

二、Stack类的模板实现

前面曾经分别使用C/C++实现了一个链栈,栈中只能放进int类型数据,现在使用模板来重新实现Stack,可以存放多种数据类型,分别使用自定义链栈方式以及自定义数组实现。

(一)、自定义链栈方式:

stack.h:

/*************************************************************************
> File Name: stack.h
> Author: Simba
> Mail: dameng34@163.com
> Created Time: 2012年11月03日 星期六 19时28分25秒
************************************************************************/

#include<iostream>
using namespace std;
template < class T > class Node
{
    //< >里面是模板参数,可以有多个,虽然T用class 声明,但可以是内建类型也可以是class类型
    //模板的定义一般写在头文件里
public:

    Node(T invalue): m_Value(invalue), m_Next(NULL) {}
    ~Node();

    T getValue() const
    {
        return m_Value;
    }
    void setValue(T value)
    {
        m_Value = value;
    }

    Node < T > *getNext() const
    {
        return m_Next;
    }
    void setNext(Node < T > *next)
    {
        m_Next = next;
    }

private:
    T m_Value;
    Node < T > *m_Next;
};

template < class T > Node < T >::~Node()
{
    if (m_Next)
    {
        delete m_Next;  //自动内存管理,接着找到m_Next指向的下一个结点,一直找到最后的一个结点
        //故先释放最后一个结点(当然是最先压栈的结点),然后依次返回释放每一个途中的结点
    }
    cout << m_Value << " deleted " << endl;
}

template < class T > class Stack
{

public:
    Stack(): m_Head(NULL), m_Count(0) {}
    ~Stack()
    {
        delete m_Head;  //自动内存管理
    }
    void push(const T &t);
    T pop();
    T top() const;
    int count() const;
private:
    Node < T > *m_Head;
    int m_Count;
};

template < class T > void Stack < T >::push(const T &value)
{
    Node < T > *newNode = new Node < T > (value);
    newNode->setNext(m_Head);
    m_Head = newNode;
    ++m_Count;
}

template < class T > T Stack < T >::pop()
{
    Node < T > *popped = m_Head;
    if (m_Head != NULL)
    {

        m_Head = m_Head->getNext();
        T retval = popped->getValue();
        popped->setNext(NULL);
        delete popped;
        --m_Count;
        return retval;
    }
    return 0;
}

template < class T > inline T Stack < T >::top() const
//模板前缀template < class T >  || 函数限定符inline  函数返回值T ||
//命名空间前缀 Stack < T > //一个类型  || 函数名(函数参数)const 限定符
{
    return m_Head->getValue();

}

template < class T > inline int Stack < T >::count() const
{
    return m_Count;
}

main.cpp:

#include "stack.h"

int main(void)
{
    Stack < int >intstack1, intstack2;

    int val;
    for (val = 0; val < 4; ++val)
    {
        intstack1.push(val);
        intstack2.push(2 * val);
    }

    while (intstack1.count())
    {
        val = intstack1.pop();
        cout << val << endl;
    }

    Stack < char >stringstack;

    stringstack.push('A');
    stringstack.push('B');
    stringstack.push('C');

    char val2;
    while (stringstack.count())
    {
        val2 = stringstack.pop();
        cout << val2 << endl;
    }
    cout << "Now intstack2 will be destructed." << endl;
    return 0;
}

可以看到虽然intstack2 没有pop 出元素,但程序结束时,局部对象会被析构,调用析构函数,在析构函数内delete 头指针,顺藤摸瓜一直找到最后一个节点,即首先压栈的节点,依次返回释放掉。

(二)、自定义数组方式

Stack2.h:

#ifndef _STACK2_H_
#define _STACK2_H_

#include <exception>

template <typename T, int MAX_SIZE>
class Stack2
{
public:
    Stack2();
    ~Stack2();

    void Push(const T &elem);
    void Pop();
    T &Top();
    const T &Top() const;
    bool Empty() const;
private:
    T *elems_;
    int top_;
};

template <typename T, int MAX_SIZE>
Stack2<T, MAX_SIZE>::Stack2() : top_(-1)
{
    elems_ = new T[MAX_SIZE];
}

template <typename T, int MAX_SIZE>
Stack2<T, MAX_SIZE>::~Stack2()
{
    delete[] elems_;
}

template <typename T, int MAX_SIZE>
void Stack2<T, MAX_SIZE>::Push(const T &elem)
{
    if (top_ + 1 >= MAX_SIZE)
        throw out_of_range("Stack2<>::Push() Stack2 full");

    elems_[++top_] = elem;
}

template <typename T, int MAX_SIZE>
void Stack2<T, MAX_SIZE>::Pop()
{
    if (top_ + 1 == 0)
        throw out_of_range("Stack2<>::Push() Stack2 empty");

    --top_;
}

template <typename T, int MAX_SIZE>
T &Stack2<T, MAX_SIZE>::Top()
{
    if (top_ + 1 == 0)
        throw out_of_range("Stack2<>::Push() Stack2 empty");

    return elems_[top_];
}

template <typename T, int MAX_SIZE>
const T &Stack2<T, MAX_SIZE>::Top() const
{
    if (top_ + 1 == 0)
        throw out_of_range("Stack2<>::Push() Stack2 empty");

    return elems_[top_];
}

template <typename T, int MAX_SIZE>
bool Stack2<T, MAX_SIZE>::Empty() const
{
    return top_ + 1 == 0;
}
#endif // _STACK2_H_

main.cpp:

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

int main(void)
{
    Stack2<int, 5> s;
    s.Push(1);
    s.Push(2);
    s.Push(3);

    while (!s.Empty())
    {
        cout << s.Top() << endl;
        s.Pop();
    }
    return 0;
}

输出为 3 2 1 

注意,用数组实现时pop 操作并没有删除元素的操作,只是移动了top 指针,下次push 的时候直接覆盖即可。再者因为实现了Top 返回栈顶元素,故pop 没有返回值。

参考:

C++ primer 第四版 Effective C++ 3rd C++编程规范

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏阮一峰的网络日志

Javascript编程风格

Douglas Crockford是Javascript权威,Json格式就是他的发明。 去年11月他有一个演讲(Youtube),谈到了好的Javascrip...

3206
来自专栏数据之美

java 中 16 进制 HEX 转换成字节码形式的 UTF-8

恩,又碰到个蛋疼的编码转换问题了:要把形如 \xE9\xBB 的字符串转成中文。。。 在python中我们直接 print "\xE9\xBB\x84" ...

2015
来自专栏Java帮帮-微信公众号-技术文章全总结

【编程题】Java编程题五(10道)

【编程题】Java编程题六(10道) 【程序41】 题目:海滩上有一堆桃子,五只猴子来分。第一只猴子把这堆桃子凭据分为五份,多了一个,这只猴子把多的一个扔入海...

43012
来自专栏小詹同学

【记录帖】(No.003)从零打卡刷Leetcode

小詹一直觉得自己编程能力不强,想在网上刷题,又怕不能坚持。不知道有木有和小伙伴和小詹一样想找个人一起刷题呢?欢迎和小詹一起定期刷leetcode,每周一周五更新...

1382
来自专栏杨熹的专栏

2 天入门 Java-Day 2

第二天的课程明显就比第一天的要难了,? 表示很吃力,脑子不够用的节奏。 各种概念绕来绕去,脑袋都要绕成了壳。 不过还好没有放弃,想个办法画出各概念间的联系,...

3269
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-21(02)总结字符流,IO流编码问题,实用案例必做一遍

C:把集合中的数据存储到文本文件 package cn.itcast_02; import java.io.BufferedWriter; import jav...

3624
来自专栏鬼谷君

python datetime模块参数详解

1162
来自专栏hbbliyong

看到他我一下子就悟了-- 泛型(2)

   先说些题外话,只所以写这些东西。是看了CSDN上的曹版主的一篇:手把手教编程,不知道有没有人愿意参与。说实话,我工作四年,总感觉晕晕乎乎的,好多技术都 懂...

2759
来自专栏编程

程序员C语言C加加新手小白入门基础最容易犯的17种错误,你中了几个?

相信这么努力的你 已经置顶了我 C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考...

1775
来自专栏Android知识点总结

Java总结之容器家族--Collection

Set的操作比较少,基本上也就是Collection传下来的方法 Set一般基于Map来实现:HashSet、LinkedHashSet、TreeSet的特性...

792

扫码关注云+社区