【问题描述】

下面程序定义栈类模板StackTemplate，创建栈对象存储斐波那契数列的前10项数值，并以后进先出的方式取出元素并输出，输出结果为：55 34 21 13 8 5 3 2 1 1。其中void push(const T& i)函数为添加元素、T pop()函数为取出栈顶元素，int fibonacci(int n)函数为计算斐波那契数列的第n项值。在计算斐波那契数列值、添加元素和取出元素的过程中要进行上溢OverFlow或者下溢UnderFlow的异常处理。

【样例输入】

无

【样例输出】

55 34 21 13 8 5 3 2 1 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <iomanip>
using namespace std;

// 定义枚举类型ERROR，其包含两个枚举常量UnderFlow和OverFlow，值分别默认为0和1，表示下溢和上溢
enum ERROR { UnderFlow, OverFlow };

int fibonacci(int n);

template<typename T>
class  StackTemplate {
	enum { size = 100 };
	T stack[size];
	int top;
public:
	StackTemplate() : top(0) {}

	void push(const T &i)
	{
		if (top >= size)	
			throw OverFlow;
		stack[top++] = i;		// 先赋值再自增，栈顶指针指向的是还没有初始化的位置
	}

	T pop()
	{
		if (top <= 0)
			throw UnderFlow;
		return stack[--top];	// 注意这里栈顶指针应该先减再取值
	}

	int getTop() const
	{
		return top;
	}
};

int main()
{
	try
	{
		StackTemplate<int> is;
		for (int i = 0; i < 10; i++)
			is.push(fibonacci(i+1));
		for (int k = 0; k < 10; k++)
			cout << setw(5) << left << is.pop();
	}
	catch (ERROR e)
	{
		switch (e)
		{
		case  OverFlow: 
                cout << "触发上溢错误！" << endl;
                exit(0);
		case  UnderFlow: 
                cout << "触发下溢错误！" << endl;
                exit(0);
		}
	}
	catch (...)	// 通用捕获异常
	{
		cout << "未知错误！" << endl;
		exit(0);
	}
	return 0;
}

int fibonacci(int n)
{
	const int sz = 100;
	int i;
	static int f[sz];	// 注意这里应该定义为静态变量，储存之间计算出的结果

	if (n > sz)
		throw OverFlow;

	f[0] = f[1] = 1;
	for (i = 0; i < sz; i++)
		if (f[i] == 0)
			break;	// i >= 2
	
    // 当n==1或2时，不进入循环，返回的都是f[1](f[0] == f[1]，所以结果不影响)
	while (i < n)	
	{
		f[i] = f[i - 1] + f[i - 2];	
		i++;	
	}
	return f[i - 1];	
}