12.4 类模板

堆栈独立于栈中数据项的类型，这一点不难理解。但是，用程序实现堆栈的时候又必须提供数据类型，这为实现软件的复用性提供了一次很好的机会。所用的方法是描述一个通常意义上的堆栈，然后建立这个类的实例类。所建的实例类虽然是通用类的副本，但是它具有指定的类型。C++ 的模板类提供了这种功能。

软件工程视点 12.2
类模板通过实例化通用类的特定版本提高了软件的复用性。

为了说明如何定制通用类的模板以形成指定的模板类，模板类需要一种或多种类型参数，所以模板类也常常称为参数化类型。

需要生成多种模板类的程序员只需简单地编写—个通用类模板的定义。在需要用模板建立一个新类的时候，程序员只需要用一种简洁的表示方法，编译器就会写出模板类的源代码。例如，堆栈类的模板可以作为编写各种类型堆栈的基础(如 float 类型、int 类型或 char 类型的堆栈等等)。

图 12.3 中的程序定义了 Stack(堆栈)的类模板。模板类与通常的类定义没有什么不同，只是以如下所示的首部开头(第8行)：

template<class T>

上述首部指出了这是一个类模板的定义，它有一类型参数T(表示所要建立的 Stack 类的类型)。程序员不需要专门使用标识符 T，任何标识符都可以使用。Stack 中存储的元素类型在Stack类首部和成员函数定义中一般表示为T。稍后将介绍如何将T与特定类型(如 double 或 id)相关联。

I // Fig. 12.3: tstackl.h
2 // Class template Stack
3 #ifndef TSTACK1_H
4 #define TSTACK1 H
5
6 #include <iostream.h>
7
8 template< class T >
9 class Stack {
10 public:
1l Stack( int = 10 ); // default constructor (stack size 10)
12 ~Stack() { delete [] stackPtr; } // destructor
13 bool push( const T& ); // push an element onto the stack
14 bool pop( T& ); // pop an element off the stack
15 private:
16 int size; // # of elements in the stack
17 int top; // location of the top element
18 T *stackPtr; // pointer to the stack
19
20 bool isEmpty() const { return top == -1; } // utility
21 bool isFull() const { return top == size - 1; } // functions
22 };
23
24 // Constructor with default size 10
25 template< class T >
26 Stack< T >::Stack( int S )
27 {
28 size = S > 0 ? S : 10;
29 top = -1; // Stack is initially empty
30 stackPtr = new T[ size ]; // allocate space for elements
31 }
32
33 // Push an element onto the stack
34 // return true if successful, false otherwise
35 template<class T>
36 bool Stack< T >::push( const T &pushValue )
37 {
38 if (!isFull() ) {
39 stackPtr[ ++top ] = pushValue; // place item in Stack
40 return true; // push successful
41 }
42 return false; // push unsuccessful
43 }
44
45 // Pop an element off the stack
46 template<class T>
47 bool Stack< T >::pop( T &popValue )
48 {
49 if (!isEmpty() ) {
50 popValue = stackPtr[ top-- ]; // remove item from Stack
51 return true; // pop successful
52 }
53 return ffalse; // pop unsuccessfu
54 }
55
56 #endif
57 // Fig. 12.3: fig12_03.cpp
58 // Test drive for stack template
59 #include <iostream.h>
60 #include "tstackl.h"
61
62 int main()
63 {
64 Stack< double > doubleStack( 5 );
65 double f = 1.1;
66 cout << "Pushing elements onto doubleStack\n";
67
68 while ( doubleStack.push( f ) ) { // success true returned
69 cout << f << ' ';
70 f += 1.1;
71 }
72
73 coout << "\nStack is full. cannot push "<< f
74 << "\n\nPopping elements from doubleStack\n";
75
76 while ( doubleStack.pop( f ) ) // success true returned
77 cout << f << ' ';
78
79 cout << "\nStack is empty. Cannot pop\n";
80
81 Stack< int > intStack;
82 int i = 1;
83 cout << "\nPushing elements onto intStack\n";
84
85 while ( intStack.push( i ) ) { // success true returned
86 cout << i << ' ';
87 ++i;
88 }
89
90 cout << "\nStack is full. Cannot push " << i
91 << "\n\nPopping elements from intStack\n";
92
93 while ( intStack.pop( i ) ) // success true returne
94 cout << i << ' ';
95
96 cout << "\nStack is empty. Cannot pop\n";
97 return O;
98 }

输出结果：

Pushing elements onto doubleStack
1.1 2.2 3.3 4.4 5.5
Stack is full. Caunot push 6.6

Pepping elements from doubleStack
5.5 4.4 3.3 2.2 1.1
Stack is empty. Cannot pop

Pushing elements onto intStack
1 2 3 4 5 6 7 8 9 10
Stack is full. Cannot push 11

Popping elements form intStack
10 9 8 7 6 5 4 3 2 1
Stack is empty. Cannot pop

图12.3 演示类模板 Stack

下面建立一个测试堆栈类模板(见图12.5的输出)的驱动程序(函数main)。程序在开始的时候实例化了一个大小为5的对象doublestack。该对象声明为类Stack<double><称为double类型的Stack类)的对象。为了产生出double类型的Stack类的源代码，编译器会自动把模板中的参数类型T替换成double。尽管程序看不到这个源代码，但仍将其放进源代码中编译。

然后程序成功地把1.1、2.2、3.3、4.4和5.5这几个double值压入(push)堆栈doubleStack。当试图将第六个值压人堆栈中的时候，push循环中止(栈已经满了，因为它只能容纳5个元素)。

然后程序再将这5个元素弹出(pop)堆栈(以LIFO顺序)。在试图弹出第六个元素的时，出栈循环中止，因为这时堆栈已经空了。
接下来，程序用下面的声明语句实例化了一个int类型的堆栈intStaek：

Stack<int>intStack

因为没有指定堆栈的大小，所以使用默认构造函数(第11行)中的默认值10作为堆栈的大小。重复上述操作，用循环结构不断向intStaek中压入整数值，直到栈满为止，然后再循环从堆栈中弹出数值，直到栈空为止。

在类模板首部以外的成员函数定义都要以下面的形式开头：

template<class T>

然后，成员函数的定义与普通成员函数的定义相似，只是Stack元素的类型要用类型参数T表示。二元作用域运算符和Stack<T>类模板将成员函数的定义与正确的类模板范围联系起来。本例中，类名是Stack<T>。当建立类型为Stack<double>的对象doubleStack的时候，Stack的构造函数使用new建立了一个表示堆栈的double类型数组。因此，对于语句：

stackPtr = new T [size];

编译器将在模板类Stack<double>中生成下面的代码：

stackPtr new double[size]；

注意图12.3函数main中的代码即main上半部分的doubleStack操作和main下半部分的intStaek操作基本相同。这里又可以使用函数模板。图12.4的程序用函数模板testStack进行与图12.3相同的工作，将一系列值压入Stack<T>中并从Stack<T>中弹出数值。函数模板testStack用参数T表示Stack<T>中保存的数据类型。

该函数模板取4个参数：Stack<T>类型对象的引用、类型为T的值用作压入Stack<T>的第一个值、类型为T的值用作压入Stack<T>的增量值以及const char*类型的字符串表示输出的Stack<T>对象名。函数main只是实例化Stack<double>类型对象doubleStack和实例化Stack<int>类型对象intStaek，如下所示(第37行到第38行)：

testStack(doubleStack，1.1，1.1，"doubleStack")；
teststack(intStack，1，1，"intstack")；

注意图 12.4 的输出与图 12.3 的输出一致。

1 // Fig. 12.4: fig12_04.cpp
2 // Test driver for Stack template.
3 // Function main uses a function template to manipulate
4 // objects of type Stack< T >.
5 #include <iostream.h>
6 #include "tstack1.h"
7
8 // Function template to manipulate Stack< T >
9 template< class T >
10 void testStack(
11 Stack< T > &theStack, // reference to the Stack< T >
12 T value, // initial value to be pushed
13 T increment, // increment for subsequent values
14 const char *stackName ) // name of the Stack < T > object
15 {
16 cout << "\nPushing elements onto "<< stackName << '\n';
17
18 while ( theStack.push( value ) ) { // success true returned
19 cout << value << ' ';
20 value += increment;
21 }
22
23 cout << "\nStack is full. Cannot push" << value
24 << "\n\nPopping elements from" << stackName << '\n';
25
26 while ( theStack.pop( value ) ) // success true returned
27 cout << value << ' ';
28
29 cout << "\nStack is empty. Cannot pop\n";
3O }
31
32 int main()
33 {
34 Stack< double > doubleStack( 5 );
35 Stack< int > intStack;
36
37 testStack( doubleStack, 1.1, 1.1, "doubleStack" );
30 testStack( intStack, 1, 1, "intStack" );
39
40 return O;
41 }

输出结果：

Pushing elements onto doubleStack
1.2 2.2 3.3 4.4 5.5
Stack is full. Cannot push 6.6

Popping elements from doubleStack
5.5 4.4 3.3 2.2 1.1
Stack is empty. Cannot pop

Pushing elements onto intStack
1 2 3 4 5 6 7 8 9 10
Stack is full. Cannot push 11

Popping elements form intStack
10 9 8 7 6 5 4 3 2 1
Stack is empty. Cannot pop

图 12.4 向函数模板传递 Stack 模板对象