我们的Stack和Queue其实就是顺序表或者链表,并且在顺序表或者链表的基础上实现一些专门面对栈或者队列的操作,那么我们也可以制作一个模板,使一个栈可以是顺序表构成的栈/队列,也可以是链表构成的栈/队列

这里我们以栈为例:

template <class T,class Container>

栈的模板定义为如上的形式

第一个class T表示的是该栈中存储的是什么类型的数据,可以是整型(int),字符型(char),当然也可以是字符串类型(string)

第二个class Container表示的是这个栈容器是什么类型的,这里可以是我们之前实现的动态顺序表,也可以是链表

既然是形参我们就可以给他缺省的类型,如下

template <class T,class Container = Vector>

完整代码:

template <class T,class Container> //缺省参数
class Stack
{
public:
	void Push(const T& x)
	{
		_con.PushBack(x);
	}

	void Pop()
	{
		_con.PopBack();
	}

	const T& Top()
	{
		return _con.Back();
	}

	bool Empty()
	{
		return _con.Empty();
	}

	size_t Size()
	{
		return _con.Size();
	}

	void Print()
	{
		_con.Show();
	}
protected:
    Container _con;
};

以上代码中的PushBack,PopBack等关于顺序表的操作均在上一篇博客 <<利用C++模板实现Vector和List>>

但是,有时候会出现这样一个问题,栈的第一个类型和容器适配器的类型并不一致

int main()
{
    Stack<char,Vector<int>> s1;
    s1.Push(1);
    s1.Push(2);
    s1.Push(3);
    s1.Push(200);
    s1.Print();
    return 0;
}

上面的代码最后一次在栈中push了一个值为200的元素,我们看一下打印结果

很显然,因为类型的不匹配造成了我们数据的不正确,为了避免这种情况发生,c++又提供了一下的定义适配器的方式

template <class T,template<class> class Container = Vector>

这里我们也使用了默认缺省的类型,Vector

完整代码:

template <class T,template<class> class Container = Vector>
class Stack
{
public:
    void Push(const T& x)
    {
        _con.PushBack(x);
    }

    void Pop()
    {
        _con.PopBack();
    }

    const T& Top()
    {
        return _con.Back();
    }

    bool Empty()
    {
        return _con.Empty();
    }

    size_t Size()
    {
        return _con.Size();
    }

    void Print()
    {
        _con.Show();
    }
protected:
    Container<T> _con;
};

这样的定义方法限制了我们给配置器类型传参数

int main()
{
	Stack<int, Vector> s1;
	s1.Push(1);
	s1.Push(200);
	return 0;
}

这样我们就不会出现适配器类型参数和模板类型参数不符的情况了

不过一般这样的定义方式还是不是很常用,程序员需要自己传一个正确的类型来避免上面情况的发生

实现Queue的代码如下

#pragma once
#include "List.h"
#include "Vector.h"

/*template<class T,class Container = List<T>> //默认参数
class Queue
{
protected:
    Container _con;
}*/

template<class T,template<class> class Container = List>
class Queue
{
public:
    void Push(const T& x)
    {
        _con.PushBack(x);
    }

    void Pop()
    {
        _con.PopFront();
    }

    const T& Front()const
    {
        return _con.Front();
    }

    bool Empty()
    {
        return _con.Empty();
    }

    size_t Size()
    {
        return Size();
    }
protected:
    Container<T> _con;
};