典型数据结构的模板实现

栈和数组

1.使用类模板实现数组结构
- 定长数组（未完待续..）
- 可变数组
2.使用类模板实现栈结构

在我们初步了解编写模板类后，应当做一下代码练习。这节我们就做一个编写代码的补充，方便大家继续学习模板类的嵌套。作为新手而言，建议大家先写一个具体类，调试好后再去修改成模板类，因为调试模板类会相对复杂。

1.使用类模板实现数组结构

数组是我们常用的一种数据类型，我们今天的内容就先从编写一个数组类模板开始。数组有定长数组和边长数组的区别，我们只来实现它们的部分功能。

定长数组（未完待续…）

首先我们先学习编写一个int类型的定长数组数组类。我们只实现查看和改写数组的元素即可。这个过程中涉及到重载[]运算符：

#define Arraysize 10
class Array
{
    private:
        int items[Arraysize]; // 声明一个数组，这里的[]不是运算符
    public:
        int sign=0; // 用于标记重载的[]运算符使用了几次
        Array(){memset(items,0,sizeof(items));} // 使用memset函数初始化数组，需要知道首地址、初始化值、数组元素类型所占空间
        int& operator[] (int ii) // 重载[]运算符，返回值类型为int的引用
        {
            this->sign++; // this指针类似于python中的self，他默认标记类地址，可以查找类内容
            return *(items+ii);
        }
        const int& operator[] (int ii) // 如果是const修饰的数组，上面的函数将不会被调用
        const{
            return *(items+ii);
        }
};

这段代码里我偷偷用了一些没有讲到的函数和知识点。包括重载运算符，初始化函数和类的this指针。当然这段代码当然没有使用this指针的必要，this->sign++直接写成sign++效果也是一样的。
写好之后我们来测试一下：

int main()
{
    Array a;
    a[0]=1;a[1]=2;a[2]=3;a[3]=4;
    for(int i=0;i<5;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<"\n"<<a.sign<<endl;
}
// 输出为：1 2 3 4 0 
//		  9

可变数组

2.使用类模板实现栈结构

栈是一种先进后出的数据结构，我们主要通过类模板实现它的入栈、出栈、判空、判满功能。首先我们编写一个函数实现int类型的栈：

class Stack
{
    private:
        int *items; // 由数组结构定义的栈
        int stacksize; // 栈含元素数量
        int top; // 栈顶指针，并非指针类型，而是类似于数组下标
    public:
        // 初始化栈
        Stack(int size):stacksize(size),top(0)
        {
            items=new int[stacksize];
        }
        // 析构函数，删除动态空间
        ~Stack()
        {
            delete items;
            items=nullptr;
        }
        // 判空函数，即判断栈顶指针是否为0
        bool isempty() const // 不允许在函数内修改任何变量值
        {
            return top==0;
        }
        // 判满函数
        bool isfull() const
        {
            return top==stacksize;
        }
        // 压栈函数
        bool push(const int& item)
        {
            if(!isfull())
            {
                items[top++]=item;
                return true;
            }
            else return false;
        }
        // 出栈函数
        bool pop(int &item)
        {
            if(!isempty())
            {
                item=items[--top];
                return true;
            }
            else return false;
        }
};

这样我们就实现了定义一个功能简单的处理类型int栈。下面我们先来测试一下各个功能是否正常，然后再看看如何把这个具体类制作成类模板：

int main()
{
    Stack ss(5);
    cout<<ss.isempty()<<" "<<ss.isfull()<<endl;
    ss.push(1);ss.push(2);ss.push(3);ss.push(4);ss.push(5);
    cout<<ss.isempty()<<" "<<ss.isfull()<<endl;
    int item;
    while(ss.pop(item))
    {
        cout<<item<<" ";
    }
}
// 输出为：1 0
//		  0 1
//		  5 4 3 2 1

这样看起来，我们的功能实现的还不错。接下来我们把它定义成可以处理不同数据类型的栈类。我们可以使用

typedef *** Mydata

在星号处填入想要处理的类型，然后将与items有关的代码全都改成Mydata（或Mydata*）类。这样做的缺点是我们经常要手动去调整类所处理的数据类型。
在有了类模板之后，我们就可以更方便的解决这些问题了：

template<class T>
class Stack
{
    private:
        T *items; // 由数组结构定义的栈
        int stacksize; // 栈含元素数量
        int top; // 栈顶指针，并非指针类型，而是类似于数组下标
    public:
        // 初始化栈
        Stack(int size):stacksize(size),top(0)
        {
            items=new T[stacksize];
        }

		// 判空和判满不需要改动

		 // 压栈函数
        bool push(const T& item)
        {
            if(!isfull())
            {
                items[top++]=item;
                return true;
            }
            else return false;
        }
        // 出栈函数
        bool pop(T &item)
        {
            if(!isempty())
            {
                item=items[--top];
                return true;
            }
            else return false;
        }