【C++】【数据结构】顺序栈的基本 *** 作（初始化、入栈、出栈、取栈顶元素、遍历输出栈）的算法实现附全代码_C

C++实现顺序栈的算法+步骤（附全代码）：

使用c++完成数据结构顺序栈的基本 *** 作，包括（初始化、入栈、出栈、取栈顶元素、遍历输出栈等），可直接编译运行。

顺序栈的定义如下：

#define MAXSIZE 100
typedef int Status;
typedef int SElemType;

//顺序栈的存储结构
typedef struct {
	SElemType * base;   //栈顶指针
	SElemType * top;    //栈底指针
	int stacksize;      //栈可用的最大容量
}SqStack;

顺序栈的初始化：

【算法步骤】

① 为顺序栈动态分配一个最大容量为MAXSIZE的数组空间，使base指向栈底。

② 栈顶指针top初始为base，表示栈为空。

③ stacksize置为栈的最大容量MAXSIZE。

【算法描述】

//顺序栈的初始化
Status InitStack(SqStack& S)
{
	S.base = new SElemType[MAXSIZE];   //构造一个空栈S
	if (!S.base) 
		return ERROR;
	S.top = S.base;
	S.stacksize = MAXSIZE;
	return OK;
}

顺序栈的入栈：

【算法步骤】

① 判断栈是否满，若满则返回ERROR。

② 将新元素放入栈顶，栈顶指针加1。

【算法描述】

//顺序栈的入栈
Status Push(SqStack& S, SElemType e)
{ //插入元素e为新的栈顶元素
	if (S.top - S.base == S.stacksize)
		return ERROR;
	*S.top++ = e;
	return OK;
}

顺序栈的出栈：

【算法步骤】

① 判断栈是否空，若空则返回ERROR。

② 栈顶指针减1，栈顶元素出栈。

【算法描述】

//顺序栈的出栈
Status Pop(SqStack& S, SElemType& e)
{ //删除S的栈顶元素，用e返回其值
	if (S.base == S.top) 
		return ERROR;
	e = *--S.top;
	return OK;
}

取栈顶元素：

【算法步骤】

① 判断栈是否空，若空则返回ERROR。

② 返回e获取栈顶元素的值。

【算法描述】

//取顺序栈的栈顶元素
Status GetTop(SqStack S, SElemType& e)
{ //返回S的栈顶元素，不修改栈顶指针
	if (S.top == S.base) 
		return ERROR;
	e = *(S.top - 1);
	return OK;
}

遍历输出顺序栈：

【算法步骤】

① 判断栈是否空，若空则返回ERROR。

② 循环输出栈顶元素。

【算法描述】

//遍历输出顺序栈
Status StackTraverse(SqStack S)
{
	SElemType* p;
	p = S.top;
	if (S.base == p)
	{
		cout << "顺序栈为空！" << endl;
		return ERROR;
	}	
	cout << "栈顶->";
	for (p--; p >= S.base; p--)
		cout << *p << " ";
	cout << endl;
	return OK;
}

全代码如下：

//顺序栈的基本 *** 作.cpp

#include 
using namespace std;
#define ERROR 0
#define OK 1
#define MAXSIZE 100
typedef int Status;
typedef int SElemType;

//顺序栈的存储结构
typedef struct {
	SElemType * base;  //栈顶指针
	SElemType* top;    //栈底指针
	int stacksize;     //栈可用的最大容量
}SqStack;

Status InitStack(SqStack&);	//空栈 
Status Push(SqStack&, SElemType);	//入栈 
Status Pop(SqStack&, SElemType&);	//出栈 
Status GetTop(SqStack, SElemType&);	//读栈顶元素 
Status StackTraverse(SqStack);	//遍历
Status StackLength(SqStack);	//栈的长度 

int main()
{
	SqStack S;
	int a;
	SElemType e;
	if (!InitStack(S))
		cout << "顺序栈初始化失败！" << endl;
	else
		cout << "顺序栈初始化成功！" << endl;
	while (1)
	{
		cout << "\n【1】入栈  【2】出栈  【3】读栈顶元素  【4】输出栈  【0】退出" << endl;
		cout << "请选择要进行的 *** 作：";
		cin >> a;
		switch (a)
		{
		case 1: 
			cout << "请输入入栈元素：";
			cin >> e;
			if (!Push(S, e))
				cout << "入栈失败！" << endl;
			else 
				cout << "元素" << e << "入栈成功！" << endl;
			break;
		case 2: 
			if (!Pop(S, e))
				cout << "出栈失败！" << endl;
			else
				cout << "元素" << e << "出栈成功！" << endl;
			break;
		case 3:
			if (!GetTop(S, e))
				cout << "读栈顶元素失败！" << endl;
			else
				cout << "栈顶元素为：" << e << endl;
			break;
		case 4:
			StackTraverse(S);
			break;
		case 0: return OK;
		default:
			return OK;
		}
	}
}

//顺序栈的初始化
Status InitStack(SqStack& S)
{
	S.base = new SElemType[MAXSIZE];   //构造一个空栈S
	if (!S.base) 
		return ERROR;
	S.top = S.base;
	S.stacksize = MAXSIZE;
	return OK;
}

//顺序栈的入栈
Status Push(SqStack& S, SElemType e)
{ //插入元素e为新的栈顶元素
	if (S.top - S.base == S.stacksize)
		return ERROR;
	*S.top++ = e;
	return OK;
}

//顺序栈的出栈
Status Pop(SqStack& S, SElemType& e)
{ //删除S的栈顶元素，用e返回其值
	if (S.base == S.top) 
		return ERROR;
	e = *--S.top;
	return OK;
}

//取顺序栈的栈顶元素
Status GetTop(SqStack S, SElemType& e)
{ //返回S的栈顶元素，不修改栈顶指针
	if (S.top == S.base) 
		return ERROR;
	e = *(S.top - 1);
	return OK;
}

//遍历输出顺序栈
Status StackTraverse(SqStack S)
{
	SElemType* p;
	p = S.top;
	if (S.base == p)
	{
		cout << "顺序栈为空！" << endl;
		return ERROR;
	}	
	cout << "栈顶->";
	for (p--; p >= S.base; p--)
		cout << *p << " ";
	cout << endl;
	return OK;
}