C++实现顺序栈

古城微笑少年丶 2022-05-26 13:53 170阅读 0赞

用C++简单地实现了顺序栈，这种实现方法其实是把一个数组看成是两个栈，左右各一个，这样就可以更加合理的利用数组的空间，尤其是当两个栈的数据类型一样，一个栈增加另一个减小两个栈这样交替时。实现代码如下：

#include<iostream>
    #include<cstdio>
    #define maxsize 1000
    using namespace std;
    
    class stack{
    	private:
    		int *data=new int[maxsize];
    		//int data[maxsize];用delete释放的只能是用new动态分配的数组空间，
    		//若数组不是动态分配的则不能用delete释放。否则会停止工作。 
    		int probe1;
    		int probe2;
    	public:
    		stack(){
    			probe1=-1;
    			probe2=maxsize;
    		}
    		void destorystack();
    		void cleanall();
    		void pop(int which);
    		void push(int which,int num);
    		bool isempity(int which);
    		int  length(int which);
    		int gettop(int which);
    };
    void stack:: cleanall(){
    	probe1=-1;
    	probe2=maxsize;
    }
    void stack:: destorystack(){
         delete []data; 
    	
    }
    void stack:: pop(int which){
    	if(which==1){
    		if(probe1!=-1)
    		probe1-=1;
    		else
    		cout<<"此栈为空！";
    	}
    	else if(which==2){
    	 	if(probe2!=maxsize)
    		probe2+=1;
    		else
    		cout<<"此栈为空！"; 
    	}
    	else{
    		cout<<"输入1或者2" ;
    	} 
    }
    void stack:: push(int which,int num){
    	if(which==1){
    		if(probe1+1!=probe2){
    		
    		probe1++;
    		data[probe1]=num;
    	}
    		else
    		cout<<"此栈已满！";
    	}
    	else if(which==2){
    	 	if(probe2-1!=probe1){
    	 			probe2--;
    	 			data[probe2]=num;
    		 } 
    	
    		else
    		cout<<"此栈已满！"; 
    	}
    	else{
    		cout<<"输入1或者2" ;
    	} 
    }
    bool stack:: isempity(int which){
    	if(which==1){
    		if(probe1==-1)
    		return true;
    		else
    		 return false;
    	}
    	else if(which==2){
    	 	if(probe2==maxsize)
    			return true;
    		else
    	return false;
    	}
    	else{
    		cout<<"输入1或者2" ;
    	} 
    }
    int stack::length(int which){
    	if(which==1){
    		 return probe1+1;
    	}
    	else if(which==2){
    	 	return maxsize-probe2;
    	}
    	else{
    		cout<<"输入1或者2" ;
    	} 
    }
    int stack::gettop(int which){
    	if(which==1){
    		 return data[probe1];
    	}
    	else if(which==2){
    	 	return data[probe2];
    	}
    	else{
    		cout<<"输入1或者2" ;
    	} 
    }
    int main(){
    	stack test;
    	if(test.isempity(1))cout<<"1 is eempity!"<<endl; 
    	if(test.isempity(2))cout<<"2 is eempity!"<<endl;
    	for(int i=0;i<100;i++){
    		test.push(1,i);
    		test.push(2,i+1);
    	}
    	cout<<"1的top为"<<test.gettop(1)<<endl<<"2的top为"<<test.gettop(2)<<endl;
    	cout<<"此时1长度为"<<test.length(1)<<"\t此时2长度为"<<test.length(2)<<endl;
    	for(int i=0;i<10;i++){
    	    test.pop(1);
    		test.pop(2);
    	}
    	cout<<"1的top为"<<test.gettop(1)<<"    "<<"1的top为"<<test.gettop(2)<<endl;
    	cout<<"此时1长度为"<<test.length(1)<<"\t此时2长度为"<<test.length(2)<<endl;
        test.destorystack();
    	return 0;
    }

输出结果为：

1 is eempity!
    2 is eempity!
    1的top为99
    2的top为100
    此时1长度为100  此时2长度为100
    1的top为89    1的top为90
    此时1长度为90   此时2长度为90

在实现的过程中有一些小毛病：

1.总是把else if两个词连在一起来写

2.使用define 时

\#define maxsize 1000

没有加分号，相当于给1000取了一个maxsize的别名

3.直接用free或者delete给一个已经声明了大小的数组释放空间是不行的，程序结束会自动释放空间。

也就是delete只能释放由new分配的数组空间

举例：

int a[100];
    //这个数组a是不能用delete释放空间的，因为这个数组a在声明时就已经说明了空间的大小，在最后程序会自动释放这个空间。
    int *b;
    b=new int[100];
    //这个要在最后用delete []b; 语句来动态释放，因为数组b是一个动态数组，数组空间是动态分配的，程序是不能自动释放的，所以要自己用delete来释放。