栈的基本操作的实现——C++类封装

Knuth学徒

线性表主要是栈和队列，一般情况下用STL库来模拟就可以了，但是STL的实现方式我觉得有必要研究下。

       这里先讨论下简单的栈 stack的实现.

       一般栈有一下几种操作： push , pop , top , empty , size

      这里我之所以介绍栈，是为了之后构想的 算法三部曲 做铺垫，不然跳跃度太大很唐突。。。。

      我的写法用了模板，可以适应各种结构。

      头文件：　stack.h:

1.      template<class type>
   
2.       class  stack{
   
3.               private:
   
4.                        type  val[MAX];
   
5.                        int  cnt;
   
6.                        int point;
   
7.              public:
   
8.                        stack();   //构造函数
   
9.                        ~stack(); //析构函数
   
10.                        void push(type data);    //压栈操作
    
11.                        void pop();        //出栈操作
    
12.                        type top();       //取栈顶元素
    
13.                        bool empty();
    
14.                        int size();
    
15.        }

复制代码

实现文件： stack.cpp

1.        template<class type>
   
2.        /////////////////////////////////////////////////////////////////////
   
3.        //          函数名：stack()
   
4.        //          参数：None
   
5.        //          前提：None
   
6.        //          描述：None
   
7.        //          用法：None
   
8.        /////////////////////////////////////////////////////////////////////
   
9.        stack<type>:: stack(){
   
10.                  cnt = 0;
    
11.                  point = 0;
    
12.                  memset(val , 0 , sizeof(val));
    
13.        }
    
14.        template<class type>
    
15.        /////////////////////////////////////////////////////////////////////
    
16.        //          函数名：push()
    
17.        //          参数：data
    
18.        //          前提：栈未满
    
19.        //          描述：将元素压入栈
    
20.        //          用法：对象名. push( xx );
    
21.        /////////////////////////////////////////////////////////////////////
    
22.        void  stack<type>::push( type  data)
    
23.        {
    
24.                 point ++;
    
25.                 val [point] = data;
    
26.                 cnt ++;
    
27.        }
    
28.       
    
29.        template<class type>
    
30.        /////////////////////////////////////////////////////////////////////
    
31.        //          函数名：pop()
    
32.        //          参数：None
    
33.        //          前提：栈非空
    
34.        //          描述：将栈顶元素弹出
    
35.        //          用法：对象名. pop( );
    
36.        /////////////////////////////////////////////////////////////////////
    
37.        void stack<type>::pop(){
    
38.                  point --;
    
39.                  cnt --;
    
40.        }
    
41. 
    
42.        template<class type>
    
43.        /////////////////////////////////////////////////////////////////////
    
44.        //          函数名：top()
    
45.        //          参数：None
    
46.        //          前提：栈非空
    
47.        //          描述：将栈顶元素读出
    
48.        //          用法：对象名. top( );
    
49.        /////////////////////////////////////////////////////////////////////
    
50.        type stack<type>:: top()
    
51.        {
    
52.                  return val[point];
    
53.        }
    
54. 
    
55.        template<class type>
    
56.        /////////////////////////////////////////////////////////////////////
    
57.        //          函数名：empty()
    
58.        //          参数：None
    
59.        //          前提：None
    
60.        //          描述：判断栈是否为空
    
61.        //          用法：对象名. empty();
    
62.        /////////////////////////////////////////////////////////////////////
    
63.        bool stack<type>:: empty()
    
64.        {
    
65.                   return (cnt == 0);
    
66.        }
    
67. 
    
68.        template<class type>
    
69.        /////////////////////////////////////////////////////////////////////
    
70.        //          函数名：size()
    
71.        //          参数：None
    
72.        //          前提：None
    
73.        //          描述：返回栈的大小
    
74.        //          用法：对象名.size();
    
75.        /////////////////////////////////////////////////////////////////////
    
76.        int stack<type>:: size()
    
77.        {
    
78.                    return cnt;
    
79.        }

复制代码

///////////////////////////////////////////////// End  ////////////////////////////////////////////


    我的写法和STL的写法相类似，只是功能没有那么多，用法和STL库也一样。

    声明方法:   stack<类型> 对象名;
   

    栈的实现有了介绍之后，接下去会是队列，等到队列和栈的操作都写好后，就能发 算法的三部曲了——包括深度优先搜索、广度优先搜索、图算法等

Knuth学徒

自己先顶一个。

Knuth学徒

栈的应用非常广泛，必须要学会基本写法，这样才能够有深刻的理解

whypro

学习了，楼主加油！

Knuth学徒

回复 4# whypro


    谢谢关注，一起努力！