基于C++的数据结构-4-顺序栈

目录

基本概念

抽象数据类型

栈的实现

顺序栈的C++描述：

---

基本概念

        栈是一种插入和删除 *** 作都只能在表的同一端进行的线性表，允许进行插入和删除 *** 作的一端叫做栈顶top，又称表尾；另一端叫栈底又称表头。

当栈为空的时候又称为空栈。

最典型的栈结构就是q械的d匣，一端出入。

 

向栈中插入元素的 *** 作称为进栈或入栈；删除元素叫做退栈或出栈；总之，栈是按照先进后出，后进先出的方式工作的。

抽象数据类型

1. 创建一个空栈
2. 删除一个栈，释放栈空间
3. 判断栈是否为空
4. 判断栈是否满--因为线性栈是有数量限制的
5. 栈顶插入一个元素
6. 获取栈顶的值
7. 删除栈顶一个元素
8. 输出栈内容，依次出栈

栈的实现

采用顺序存储结构表示的栈称为顺序栈，顺序栈需要分配一块连续的存储区域来存放栈中的元素，顺序栈可以用以为数组来实现，因为栈底位置是固定不变的，所以可以把栈底设置为一维数组的任意一端，栈顶位置会随着进栈和出栈 *** 作而不断变化，因此用一个变量来指示当前栈顶位置。

并且假设栈的最大元素个数为MaxSize。

由于一个栈可能有n个数据元素，也可能是空栈，所以在顺序栈类模板成员中，除了用来实现顺序栈的动态数组外，还有两个整型成员变量来标注栈的最大长度和当前栈顶位置。

顺序栈的创建和删除是使用类的构造函数和析构函数来实现的，根据最大限额为栈申请一个用指针指向的具有特定字节的连续空间，然后栈顶赋值为-1，表示空栈；析构函数复制程序结束的时候回收申请的连续空间。

当栈中已经有最大限额的元素，此时再进行进栈 *** 作就会发生溢出，称为上溢；而对空栈执行出栈 *** 作也会产生溢出--下溢，因此在顺序栈执行出栈或进栈之前应当先检查栈的元素数量，判断是否为空或为满，这是一种良好的错误规避方法。

以出栈为例，我们都只在栈顶进行 *** 作，所以进栈出栈 *** 作的算法复杂度都是O(1)。

顺序栈的C++描述：

#include
using namespace std;

template 
class LinearStack{
	public:
		LinearStack(int LSMaxSize);
		~LinearStack();
		bool IsEmpty();
		bool IsFull();
		int GetElementNumber();
		bool Push(const T& x);
		bool Top(T& x);
		bool Pop(T& x);
		void Output(ostream& out) const;//const表示对本类的常量指针，即该成员函数只支持对本类的读，不支持写
		        //加了const的函数能被const和非const对象调用，非const函数只能被非const对象调用。



	private:
		int top;
		int MaxSize;
		T *element;
};

template
LinearStack::LinearStack(int LSMaxSize){
    MaxSize=LSMaxSize;
    element=new T[LSMaxSize];
    top=-1;
}
template
LinearStack::~LinearStack(){
	delete []element;
}
template
bool LinearStack::IsEmpty(){
	return top==-1;
}
template
bool LinearStack::IsFull(){
	return top+1==MaxSize;
}
template
bool LinearStack::Push(const T& x){
	if(IsFull()){
		return false;
	}
	else{
		top++;
		element[top]=x;
		return true;
	}
}
template
bool LinearStack::Top(T& x){
	if(IsEmpty()){
		return false;
	}
	else{
		x=element[top];
		return true;
	}
}
template
bool LinearStack::Pop(T& x){
	if(IsEmpty()){
		return false;
	}
	else{
		x=element[top];
		top--;
		return true;
	}
}
template
void LinearStack::Output(ostream& out) const{
	for(int i=0;i
ostream& operator<<(ostream& out,const LinearStack& x){
	x.Output(out);
	return out;
}

void conversion(int,int);

int main(){
	cout<<"将100转化为二进制数，顺序栈实现"< s(100);
	while(y){
		s.Push(y%base);
		y=y/base;
	}
	cout<<"十进制数100转换为2进制数为："<

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/585382.html