当前位置:   article > 正文

【C++】【数据结构】顺序栈的基本操作(初始化、入栈、出栈、取栈顶元素、遍历输出栈)的算法实现附全代码_将程序填写完整,实现顺序栈的初始化、入栈、出栈、取栈顶元素、求栈长等基本操作

将程序填写完整,实现顺序栈的初始化、入栈、出栈、取栈顶元素、求栈长等基本操作

C++实现顺序栈的算法+步骤(附全代码):

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

顺序栈的定义如下:

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

//顺序栈的存储结构
typedef struct {
	SElemType * base;   //栈底指针
	SElemType * top;    //栈顶指针
	int stacksize;      //栈可用的最大容量
}SqStack;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

顺序栈的初始化:

【算法步骤】

① 为顺序栈动态分配一个最大容量为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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

顺序栈的入栈:

【算法步骤】

① 判断栈是否满,若满则返回ERROR。
② 将新元素放入栈顶,栈顶指针加1。

【算法描述】

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

顺序栈的出栈:

【算法步骤】

① 判断栈是否空,若空则返回ERROR。
② 栈顶指针减1,栈顶元素出栈。

【算法描述】

//顺序栈的出栈
Status Pop(SqStack& S, SElemType& e)
{ //删除S的栈顶元素,用e返回其值
	if (S.base == S.top) 
		return ERROR;
	e = *--S.top;
	return OK;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

取栈顶元素:

【算法步骤】

① 判断栈是否空,若空则返回ERROR。
② 返回e获取栈顶元素的值。

【算法描述】

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

遍历输出顺序栈:

【算法步骤】

① 判断栈是否空,若空则返回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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

全代码如下:

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

#include <iostream>
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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124

运行结果:

在这里插入图片描述
美美地解决!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/515639
推荐阅读
相关标签
  

闽ICP备14008679号