顺序栈

谁借莪１个温暖的怀抱￠ 2022-06-18 01:56 143阅读 0赞

顺序栈(C++)

//
    //Description:顺序栈
    //
    #include <iostream>
    #include <malloc.h>
    
    using namespace std;
    
    #define STACK_INIT_SIZE 100
    #define STACKINCREMENT 10
    
    typedef int Status;
    typedef int SElemType;
    
    //顺序栈的定义
    typedef struct
    {
    	SElemType *base;
    	SElemType *top;
    	int stacksize;
    }SqStack;
    
    
    //---------------以下为基本操作
    
    //构造一个栈
    Status InitStack(SqStack &S)
    {
    	S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    	if (!S.base)
    	{
    		cout << "存储空间分配失败！" << endl;
    		return 0;
    	}
    	S.top = S.base;
    	S.stacksize = STACK_INIT_SIZE;
    	return 1;
    }
    
    //初始化一个栈
    Status Input(SqStack &S, int n)
    {
    	int i;
    	if (n>0)
    	{
    		cout << "请输入第" << 1 << "个元素的值" << endl;
    		cin >> *S.base;
    		S.top++;
    		for (i = 2; i <= n; i++)
    		{
    			cout << "请输入第" << i << "个元素的值" << endl;
    			cin >> *S.top;
    			S.top++;
    		}
    		return 1;
    	}
    	else
    	{
    		cout << "输入数据不合法！" << endl;
    		return 0;
    	}
    
    }
    
    //查看栈顶元素
    Status GetTop(SqStack S, SElemType &e)
    {
    	if (S.top == S.base)
    	{
    		cout << "目前为空栈，无栈顶元素！" << endl;
    		return 0;
    	}
    	e = *(S.top - 1);
    	cout << "当前栈顶元素为" << e << endl;
    
    	return 1;
    }
    
    //向栈顶插入一个元素
    Status Push(SqStack &S, SElemType e)
    {
    	if (S.top - S.base >= S.stacksize)
    	{
    		S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(SElemType));
    		if (!S.base)
    		{
    			cout << "执行插入操作分配存储空间时失败！" << endl;
    			return 0;
    		}
    		S.top = S.base + S.stacksize;
    		S.stacksize += STACKINCREMENT;
    	}
    	*S.top++ = e;
    	return 1;
    }
    
    //删除栈顶元素
    Status Pop(SqStack &S, SElemType &e)
    {
    	if (S.top == S.base)
    	{
    		cout << "目前为空栈，无法执行删除栈顶元素的操作!" << endl;
    		return 0;
    	}
    	e = *--S.top;
    	return 1;
    }
    
    //--------------主函数
    void main()
    {
    
    	cout << "\n--------------------顺序栈-----------------" << endl;
    	SqStack stc;
    	InitStack(stc);
    	int num;
    	cout << "请输入初始时欲在栈中放入的元素的个数" << endl;
    	cin >> num;
    	cout << endl;
    	Input(stc, num);
    	SElemType value;
    	cout << endl;
    	GetTop(stc, value);
    	cout << "请输入欲插入元素的值" << endl;
    	cin >> value;
    	cout << endl;
    	Push(stc, value);
    	cout << "插入的元素的值为" << value << endl; GetTop(stc, value);
    	cout << endl;
    	Pop(stc, value);
    	cout << "刚刚删除的栈顶元素的值为" << value << endl; GetTop(stc, value);
    }