首页 > 代码库 > 堆（stack） 之 c 和 c++模板实现（空类默认成员函数 初谈引用 内联函数）
堆（stack） 之 c 和 c++模板实现（空类默认成员函数 初谈引用 内联函数）
//stack 的基本操作
#include <iostream>
using namespace std;
const int maxn = 3;
typedef struct Stack
{
//NumType num;
int num;
}Stack;
int top = 0;//当前元素位置的上一个元素
Stack stack[maxn];
bool is_empty();
bool is_full();
int pop();
void push(const int &key);
int get_top();
bool make_empty();
int main()
{
int tmp;
cout << get_top() << " " << pop() << endl;// 这句话和下面存在同样的错误
cout << "Input a set of integers:(-1 is over)" << endl;
while(cin >> tmp)
{
if(tmp == -1) break;
push(tmp);
}
tmp = get_top();
cout << tmp << endl;
tmp = pop();
cout << tmp << endl;
//cout << pop() << " " << get_top() << endl;
//cout << get_top() << " " << pop() << endl;// 这样输出会发生非常奇妙的事情的
return 0;
}
// if stack is empty return true
bool is_empty()
{
return (top == 0);
}
// if stack is full return true
bool is_full()
{
return (top == maxn);
}
// pop the top number if not empty
int pop()
{
if(is_empty())
{
cout << "The Stack is empty,Cannot pop..." << endl;
return -1;
}
else
{
top --;
return stack[top].num;
}
}
// push one number,if not full
void push(const int &key)
{
if(is_full())
{
cout << "The Stack is full,Cannot push..." << endl;
return;
}
else
{
stack[top].num = key;
top ++;
}
}
// get the top number,not pop
int get_top()
{
if(is_empty())
{
cout << "The Stack is empty,Cannot get top..." << endl;
return -1;
}
else
{
return stack[top-1].num;
}
}
bool make_empty()
{
top = 0;
}/*
学习心得：
1、 此栈用链表实现，与上面的用数组实现不一样；用到了模板类Stack<DT>
2、 此类用到了复制构造函数 Stack(const Stack<DT> &original),运算符重载函数
Stack<DT>& operator = (const Stack<DT> &original)
3、 初始化的默认构造方式Stack():top(NULL) {},记住类中声明的函数不可以有函数体的，
但是空函数体（只有{}）是可以的（即默认构造函数；所有的成员变量是不可以初试化的，
但是可以通过默认构造函数初始化，如Stack():top(NULL) {}，或者定义为static。
4、 &element引用作为参数时：（1）const Stack<DT> &original 作为不可变的变量的
引用传递 （2）DT &top_element 函数的引用型参数作为返回值（可以实现多个返回值）
5、 内联函数的引入，内联扩展是用来消除函数调用时的时间开销。它通常用于频繁
执行的函数。 一个小内存空间的函数非常受益，类似与宏定义，但是宏也有很多的不尽人意的地方：
（1）宏不能访问对象的私有成员。（2）宏的定义很容易产生二义性。
6、 template 和 typedef 不能同时使用的问题：模板不是类型！typedef只能给
类型取别名。单独的Node是模板，而Node<int>是一个实实在在的类型。
using关键字可以给模板取别名！如:template<class T>
using Test = Node<T>;Test<int> t;
等价于:Node<int> t;
7、 只要定义了任何一种构造函数，就不会自动定义默认构造函数。如果此时要用到默认构造函数，
就必须手动定义默认构造函数。所谓默认构造函数，就是调用构造函数时，不必给出实参的构造函数。
8、 如果一个类中定义了任何一种构造函数，而未定义默认构造函数，是不能够定义类的对象的如：class A{}； A aa;(这是错误的)
但是A *pa;(这是合法的，因为仅仅定义了一个指针，没有调用任何构造函数，不分配类对象的内存)
9：写一个空类;class a(){} 编译的时候会生成哪些函数?
默认构造函数
析构函数
拷贝构造函数
赋值运算符（operator=）
取址运算符（operator&）（一对，一个非const的，一个const的）
当然，所有这些只有当被需要才会产生。比如你定义了一个类，但从来定义过该类的对象，也没使用过该类型的函数参数，那么基本啥也不会产生。在比如你从来没有进行过该类型对象之间的赋值，那么operator=不会被产生。
最后那一对取址运算符是用争议的, 我记得以前是有一个贴讨论这个的,据说跟具体的编译器相关, 有的生成, 有的不生成, 只有前四个
*/
class Empty
{
public:
Empty(); // 缺省构造函数
Empty(const Empty&); // 拷贝构造函数
~Empty(); // 析构函数
Empty& perator=(const Empty&); // 赋值运算符
Empty* operator&(); // 取值运算符
const Empty* operator&() const; // 取值运算符
};下面是模板类：
#include<iostream>
#include<string>
using namespace std;
//用"链表"实现栈
//入栈，出栈的时间复杂度为O(1)
//复制、清空和遍历栈的时间复杂度为O(n)
template<class DT>
//typedef struct Node// template 中不能用typedef
struct Node
{
DT info;
Node<DT> *next;
};
template<class DT>
class Stack
{
public:
Stack():top(NULL) {};// 初试化top的构造函数...初始化的默认方式
Stack(const Stack<DT> &original);
~Stack();
Stack<DT> &operator = (const Stack<DT> &original);
void push(const DT &element);
bool pop(DT &element);
bool peek(DT &top_element);// 得到栈顶的数据
bool is_empty() const;// is empty 没有满
void make_empty();
private:
Node<DT> *top,*pre;// 私有成员,指向当前成员，指向链表的头
inline void deepCopy(const Stack<DT> &original);//深复制
};
template<class DT>
Stack<DT>::Stack(const Stack<DT> &original)
{
deepCopy(original);
}
template<class DT>
Stack<DT>::~Stack()
{
make_empty();// 直接条用类里面的函数
}
template<class DT>
void Stack<DT>::push(const DT &element)
{
pre = new Node<DT>;
pre->info = element;
pre->next = top;
top = pre;
}// 前插入法，top指向链表的头结点
template<class DT>
Stack<DT>& Stack<DT>::operator =(const Stack<DT> &original)
{
deepCopy(original);
return this;
}// 运算符重载函数，返回的是引用
template<class DT>
bool Stack<DT>::pop(DT &element)
{
if(top == NULL)
return false;
else
{
element = top->info;
pre = top;
top = top->next;
delete pre;
pre = NULL;
}
//cout << "*****pop" << endl;
return true;
}
template<class DT>
bool Stack<DT>::peek(DT &top_element)
{
if(top == NULL)
return false;
else
{
top_element = top->info;
}
//cout << "***peek" << endl;
return true;
}
template<class DT>
bool Stack<DT>::is_empty() const
{
return (top == NULL);
}
template<class DT>
void Stack<DT>::make_empty()
{
if(top == NULL)
return;
while(top != NULL)
{
pre = top;
top = top->next;
delete pre;
pre = NULL;
}
}
template<class DT>
void Stack<DT>::deepCopy(const Stack<DT> &original)
{
Node<DT> *oriPtr = original.top;
Node<DT> *copyPtr = top = new Node<DT>;
copyPtr->info = oriPtr->info;
while(oriPtr->next != NULL)
{
copyPtr->next = new Node<DT>;// 经典！！！
copyPtr = copyPtr->next;
oriPtr = oriPtr->next;
copyPtr->info = oriPtr->info;
}
copyPtr->next = NULL;
}
int main()
{
Stack<string> obj;// 模板类的构造函数
string str[5] = {"hello","the","world","welcome","to"};
string strTemp;
for(size_t ix=0;ix!=5;++ix)
{
obj.push(str[ix]);
obj.peek(strTemp);
cout<<strTemp<<",";
}
cout<<endl;
Stack<string> obj1(obj); //测试复制构造函数
for(size_t ix=0;ix!=5;++ix)
{
obj1.pop(strTemp);
cout<<strTemp<<",";
}
cout<<endl;
if(obj1.is_empty())
cout<<"Stack is empty!"<<endl;
Stack<string> obj2(obj); //测试复制构造函数
obj2.make_empty();
if(obj2.is_empty())
cout<<"Stack is empty!"<<endl;
Stack<string> obj3 = obj; //测试重载“=”操作符
for(size_t ix=0;ix!=5;++ix)
{
obj3.pop(strTemp);
cout<<strTemp<<",";
}
cout<<endl;
for(size_t ix=0;ix!=5;++ix)
{
obj.pop(strTemp);
cout<<strTemp<<",";
}
cout<<endl;
return 0;
}/*
内联函数是使用inline关键字声明的函数，也成内嵌函数，它主要的作用是解决程序的运行
效率。使用内联函数的时候要注意：
1.递归函数不能定义为内联函数
2.内联函数一般适合于不存在while和switch等复杂的结构且只有1~5条语句的小函数上，
否则编译系统将该函数视为普通函数。
3.内联函数只能先定义后使用，否则编译系统也会把它认为是普通函数。
4.对内联函数不能进行异常的接口声明。
*/
堆（stack） 之 c 和 c++模板实现（空类默认成员函数 初谈引用 内联函数）