栈的抽象数据结构。栈的成员函数需要包括这几个基本的函数：initializeStack(),isEmptyStack(),isFullStack,push(),pop(),top()
其功能如下：
- initializeStack():初始化栈
- isEmptyStack():判断栈是否为空
- isFullStack():判断栈是否已满
- push():将一个元素压入栈中
- pop():删除栈顶元素
- top():获得栈顶元素
C++中用抽象类作为基类实现ADT如下：
|
1
2
3
4
5
6
7
8
9
10
|
template<class Type> class stackADT { virtual void initializeStack()=0;//virtual和=0表明都是纯虚函数，抽象类中只能声明纯虚函数，不能定义 virtual bool isEmptyStack() const=0;//const放在函数后面，表明该函数是常成员函数，在函数执行过程中不能改变函数内部变量的值 virtual bool isFullStack() const=0; virtual void push(const Type&)=0;//引用常量，该函数不会自动对输入进行赋值，同时在函数内的操作也不能改变输入的值 virtual void pop()=0; virtual Type top() const=0;//这里也采用常成员函数，因为函数不会对变量进行修改，只是返回变量 }; |
补充说明：
- 抽象类：一个类中只要有一个纯虚函数，那么该类就是抽象类，抽象类通常作为基类，纯虚函数在抽象类中只能声明不能定义。
- 常成员函数：什么时候才使用常成员函数？一般在如果该函数在执行过程中不会有改变变量值的操作，就会把该函数定义为常成员函数。
- 常引用：常引用一般用于函数输入，或者函数返回值。如函数输入是常引用类型，那么说明该函数只会用到引用的值，而不会改变引用变量的值，同时可能引用变量的类型可能很大比较占内存，所以用引用可以避免输入参数的复制，从而节约了空间；若函数返回值为常引用类型，那么有两个原因，首先const表示返回值不能被修改（注意和常成员函数做区分），引用则表示函数返回时不会对返回变量进行拷贝，从而不会触发拷贝函数，因此经常被用于运算符重载，但是要注意返回值不能是函数局部变量，因为局部变量在函数结束后会被释放，从而引用了不合法的内存，会报错，像如果是运算符重载返回的基本是this指向的对象，这对于函数来说则是全局的，所以是没问题的，一般如果返回值是对象，且要避免拷贝，那么就把返回值类型设置为常引用。总之引用作为输入参数或者返回值时就是为了避免产生副本，而const则是为了保证变量不被修改。
- 栈的动态数组实现
直接继承抽象类，不管是动态数组实现还是链表实现，抽象类的那几个成员函数都是需要的，但是函数实现的内容不一样
这就体现了多态了。
下面是派生栈类的定义：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
template <class Type> class stackType:public stackADT<Type> //一定要记住每次用到模板类时不要忘记后面的<Type> { public: stackType(int stackSize=100);//注意这里用到了参数缺省构造函数中的参数缺省必须在声明函数时给出默认值而不能在定义函数时给出默认值；stackType作为函数名，因此后面不要加<Type> stackType(const stackType<Type>&); //拷贝构造函数 ~stackType(); const stackType<Type>& operator=(const stackType<Type>&);//重载赋值运算符 void initializeStack(); bool isEmptyStack()const; bool isFullStack()const; void push(const Type&); void pop(); Type top()const; private: Type* list;//指向栈的首地址 int maxStackSize;//栈的最大容量 int stackTop;//栈顶元素的位置(从1开始) void copyStack(const stackType<Type>&);//执行深拷贝过程 };//注意不要忘记分号 |
成员函数的实现如下：
initializeStack():
|
1
2
3
4
5
|
template<class Type>//在类外定义函数必须使用template，并且每定义一个函数就要写一次void stackType<Type>::initializeStack() //命名空间也不要忘记::,因为命名空间的名字是模板类，所以后面要有<Type>{ stackTop=0;//不需要把元素全部置零，只需要把栈顶元素的索引变成0即可} |
isEmptyStack():
|
1
2
3
4
5
|
template<class Type>bool stackType<Type>::isEmptyStack()const{ return !stackTop;//可以认为stackTop表示栈中目前元素的个数，为0则表示空栈} |
isFullStack():
|
1
2
3
4
5
|
template<class Type>bool stackType<Type>::isFullStack()const{ return stackTop==maxStackSize;} |
push():
|
1
2
3
4
5
6
7
8
|
template<class Type>void stackType<Type>::pop(){ if(!isEmptyStack()) stackTop--; else cout<<"The stack is empty,cannot add to an item"<<endl;} |
pop():
|
1
2
3
4
5
6
7
8
|
template<class Type>void stackType<Type>::pop(){ if(!isEmptyStack()) stackTop--; else cout<<"The stack is empty,cannot add to an item"<<endl;} |
top():
|
1
2
3
4
5
6
|
template<class Type>Type stackType<Type>::top()const{ assert(!isEmptyStack());//如果栈为空那么必须终止程序，reuturn 返回的会是乱码，push和pop不需要这个操作是因为他们没有返回值，所以如果不满足执行的条件只需要在终端上显示出现异常就行。 return list[stackTop-1];} |
copyStack():
|
1
2
3
4
5
6
7
8
9
10
|
template<class Type>void stackType<Type>::copyStack(const stackType<Type>& otherStack){ delete [] list; //释放当前栈的内存,注意如果delete的是一个空指针，那么delete不会执行，因此就不需要判断是否为空指针 stackTop=otherStack.stackTop; maxStackSize=otherStack.maxStackSize; list=new Type[maxStackSize]; // for(int i=0;i<stackTop;i++) list[i]=otherStack.list[i];} |
stackType():构造函数
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
template<class Type>stackType<Type>::stackType(int stackSize){ if(stackSize<=0) { cout<<"The size must be positive"<<endl; cout<<"creating an array of size 100"<<endl; maxStackSize=100; } else { maxStackSize=stackSize; } stackTop=0; list=new Type[maxStackSize];} |
stackType():拷贝构造函数
|
1
2
3
4
5
6
|
template<class Type>stackType<Type>::stackType(const stackType<Type>& otherStack){ list=nullptr; //这里list必须置为空，因为在这个程序中，赋值栈的赋值触发的是运算符重载，而拷贝构造函数只有在作为函数输入参数时或者返回参数时才会被触发，同时由于拷贝构造函数是构造函数重载，所以在触发拷贝构造函数前并不会触发构造函数，也意味着并没有给list分配内存，那么list就是一个野指针，如果不置为空那么调用copyStack()时,由于copyStack中第一条语句就是delete []list;删除没有分配内存的野指针就会报错，所以list置为空是必须的 copyStack(otherStack);} |
operator=():赋值运算符重载
|
1
2
3
4
5
6
7
|
template<class Type>const stackType<Type>& stackType<Type>::operator=(const stackType<Type>& otherStack){ if(this!=&otherStack) //避免自我复制 copyStack(otherStack); return *this;} |
~stackType():析构函数
|
1
2
3
4
5
|
template<class Type>stackType<Type>::~stackType(){ delete [] list;} |
文件构成有两种方式
stackADT单独一个头文件，stackADT.h，stackType类在头文件stackArr.h中定义，在.cpp文件中实现。
stackArr.h
|
1
2
|
#include "stackADT.h"//类的定义放在这里 |
stacArr.cpp
|
1
2
3
4
5
|
#include<iostream>#include<cassert>#include "stackArr.h"using namespace std;//类的实现放在这里 |
main.cpp
|
1
2
3
4
5
6
|
#include "stackArr.cpp" //这里不能include "stackArr.h"，因为这里是模板类，模板类需要编译两次，int main(){ //主函数的内容 return 0;} |
2.把stackArr类的定义和实现都放进一个头文件stackArr.h
|
1
2
3
4
5
6
7
8
9
|
#ifndef H_StackType#define H_StackType#include<iostream>#include<cassert>#include "stackADT"using namespace std;//类的定义如下//此处写类的成员函数的实现#endif |
总结：使用模板实现栈的一些要点
首先栈最重要的特征就是先入后出，有一端相当于是封闭的，另外栈的一个重要标识就是栈顶，如果用数组实现栈，那么就通过栈顶元素的索引+1(因为索引从0开始)来表示栈顶。
2.把对象复制过程进行了分离，这里用copyStack函数实现了对象成员变量的复制，由于成员变量中有指针，而且指针指向的是动态内存所以必须进行深拷贝，而在拷贝构造函数中直接调用copyStack函数即可，同时这里将赋值运算符进行了重载，那么对于语句a=b，调用的就不是拷贝构造函数了，而是调用运算符重载，只有在作为函数输入或者返回参数时生成对象副本次才会调用拷贝构造函数，还有析构函数要把内存释放，否则会导致内存泄漏。
3.注意push，pop，top的异常判断，这也是初学最容易忽视的点，不要嫌麻烦，对于会导致程序出错的输入要终止程序，像本程序中top函数是有返回值的所以如果是空栈的话返回的就是乱码所以遇到空栈用了assert函数退出程序，像如果只是输入不合法，像push函数，因为是先判断的栈是否已经满了，而且没有返回值，假如栈已满，我们不进行压栈操作就行了，只需要在终端打印错误信息就行，因此就没必要终止程序。
4.特别注意类模板的定义和实现，对于模板类而言最好还是把定义和实现的代码放在同一个头文件，同样采取类内声明，类外定义的方法。对非模板类而言，类的定义和实现通常不在同一个头文件，一般就是在头文件中定义类，然后在同名的.cpp文件中实现成员函数。
[[栈的链表实现]]
到此这篇关于C++栈的数组实现的文章就介绍到这了,更多相关C++栈的数组实现内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://blog.csdn.net/a1291714103/article/details/124590474
