栈的基本操作的实现——C++类封装
本帖最后由 Knuth学徒 于 2011-2-7 11:03 编辑线性表主要是栈和队列，一般情况下用STL库来模拟就可以了，但是STL的实现方式我觉得有必要研究下。
这里先讨论下简单的栈 stack的实现.
一般栈有一下几种操作： push , pop , top , empty , size
这里我之所以介绍栈，是为了之后构想的 算法三部曲 做铺垫，不然跳跃度太大很唐突。。。。
我的写法用了模板，可以适应各种结构。
头文件： stack.h: template<class type>
classstack{
private:
typeval;
intcnt;
int point;
public:
stack(); //构造函数
~stack(); //析构函数
void push(type data); //压栈操作
void pop(); //出栈操作
type top(); //取栈顶元素
bool empty();
int size();
}实现文件： stack.cpp template<class type>
/////////////////////////////////////////////////////////////////////
// 函数名：stack()
// 参数：None
// 前提：None
// 描述：None
// 用法：None
/////////////////////////////////////////////////////////////////////
stack<type>:: stack(){
cnt = 0;
point = 0;
memset(val , 0 , sizeof(val));
}
template<class type>
/////////////////////////////////////////////////////////////////////
// 函数名：push()
// 参数：data
// 前提：栈未满
// 描述：将元素压入栈
// 用法：对象名. push( xx );
/////////////////////////////////////////////////////////////////////
voidstack<type>::push( typedata)
{
point ++;
val = data;
cnt ++;
}
template<class type>
/////////////////////////////////////////////////////////////////////
// 函数名：pop()
// 参数：None
// 前提：栈非空
// 描述：将栈顶元素弹出
// 用法：对象名. pop( );
/////////////////////////////////////////////////////////////////////
void stack<type>::pop(){
point --;
cnt --;
}
template<class type>
/////////////////////////////////////////////////////////////////////
// 函数名：top()
// 参数：None
// 前提：栈非空
// 描述：将栈顶元素读出
// 用法：对象名. top( );
/////////////////////////////////////////////////////////////////////
type stack<type>:: top()
{
return val;
}
template<class type>
/////////////////////////////////////////////////////////////////////
// 函数名：empty()
// 参数：None
// 前提：None
// 描述：判断栈是否为空
// 用法：对象名. empty();
/////////////////////////////////////////////////////////////////////
bool stack<type>:: empty()
{
return (cnt == 0);
}
template<class type>
/////////////////////////////////////////////////////////////////////
// 函数名：size()
// 参数：None
// 前提：None
// 描述：返回栈的大小
// 用法：对象名.size();
/////////////////////////////////////////////////////////////////////
int stack<type>:: size()
{
return cnt;
}///////////////////////////////////////////////// End////////////////////////////////////////////
我的写法和STL的写法相类似，只是功能没有那么多，用法和STL库也一样。
声明方法: stack<类型> 对象名;
栈的实现有了介绍之后，接下去会是队列，等到队列和栈的操作都写好后，就能发 算法的三部曲了——包括深度优先搜索、广度优先搜索、图算法等 自己先顶一个。 本帖最后由 Knuth学徒 于 2011-2-7 11:09 编辑
栈的应用非常广泛，必须要学会基本写法，这样才能够有深刻的理解 学习了，楼主加油！ 回复 4# whypro
谢谢关注，一起努力！
页:
[1]