C/C++教程

数据结构C/C++实现——栈之顺序栈(含共享顺序栈)

本文主要是介绍数据结构C/C++实现——栈之顺序栈(含共享顺序栈),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

top指向栈顶元素本身: 

/*
栈:只允许在一段进行插入或删除操作的线性表
顺序栈:用顺序存储方式实现的栈
*/
#include<cstdio>
#include<iostream>
using namespace std;

#define MaxSize 5                                 //定义顺序栈最大长度
#define ElemType int

typedef struct {
	ElemType data[MaxSize];                        //静态数组存放栈中元素
	int top;                                       //栈顶指针
}SqStack;                                          //顺序栈类型定义   sq:sequence顺序

//初始化顺序表
void InitStack(SqStack& S) {
	S.top = -1;
}

/*
此种设定下:
    栈顶指针:S.top(指向栈顶元素)
	初始时设置:S.top = -1
	栈顶元素:S.data[S.top]
	栈空:S.top == -1
	栈满:S.top == MaxSize - 1
	栈长:S.top + 1

	进栈操作:栈不满时,栈顶指针先+1,再送值到栈顶元素
	出栈操作:栈非空时,先取栈顶元素值,再将栈顶指针-1
*/

//判空
bool StackEmpty(SqStack S) {
	if (S.top == -1) return true;
	else return false;
}

//要注意的是,需要改动栈本身的时候一定要加&

//入栈
bool Push(SqStack& S, ElemType x) {
	if (S.top == MaxSize - 1) return false;        //栈满

	S.top = S.top + 1;
	S.data[S.top] = x;
	return true;
}


bool Push2(SqStack& S, ElemType x) {
	if (S.top == MaxSize - 1) return false;        //栈满

	S.data[++S.top] = x;
	return true;
}

//出栈
bool Pop(SqStack& S, ElemType& x) {
	if (S.top == -1) return false;                //栈空

	x = S.data[S.top];
	S.top = S.top - 1;
	return true;
}

bool Pop2(SqStack& S, ElemType& x) {
	if (S.top == -1) return false;                //栈空

	x = S.data[S.top--];
	return true;
}

//读取栈顶元素
bool GetTop(SqStack S, ElemType& x) {
	if (S.top == -1) return false;

	x = S.data[S.top];
	return true;
}

//以上所有基本操作时间复杂度为O(1)
//销毁(因为采用的是变量声明的方式分配得内存空间 未使用malloc函数 存储空间的回收由系统自动完成 故只需要完成清空操作即可)
void DestroyStack(SqStack &S) {
	S.top = -1;
}

int main() {
	SqStack S;
	InitStack(S);
	int x;
	bool sign;
	cout << "请连续输入要入栈的值 空格分界 999结束:\n";
	scanf_s("%d", &x);
	while (x != 999) {
		sign = Push(S, x);
		if (sign == false) {//由于顺序栈的入栈操作受数组上界的约束,当对栈的最大使用空间估计不足时,有可能发生栈上溢,此时应及时向用户报告消息
			cout << "栈最大容量为:" << MaxSize << ",当前栈已满,超出部分未入栈\n";
			break;
		}
		scanf_s("%d", &x);
	}

	int top;
	sign = GetTop(S, top);
	if (sign == true)
		cout << "当前栈顶元素为:" << top << "\n";
	else if (sign == false)
		cout << "栈空,读取栈顶元素失败\n";

	sign = Pop(S, top);
	if (sign == true)
		cout << "出栈元素为:" << top << "\n";
	else if (sign == false)
		cout << "栈空,出栈失败\n";

	sign = GetTop(S, top);
	if (sign == true)
		cout << "当前栈顶元素为:" << top << "\n";
	else if (sign == false)
		cout << "栈空,读取栈顶元素失败\n";

	sign = Pop2(S, top);
	if (sign == true)
		cout << "出栈元素为:" << top << "\n";
	else if (sign == false)
		cout << "栈空,出栈失败\n";

	sign = GetTop(S, top);
	if (sign == true)
		cout << "当前栈顶元素为:" << top << "\n";
	else if (sign == false)
		cout << "栈空,读取栈顶元素失败\n";
	
	return 0;
}

top指向栈顶元素下一位置:

/*
栈:只允许在一段进行插入或删除操作的线性表
顺序栈:用顺序存储方式实现的栈
*/
#include<cstdio>
#include<iostream>
using namespace std;

#define MaxSize 5                                 //定义顺序栈最大长度
#define ElemType int

typedef struct {
	ElemType data[MaxSize];                        //静态数组存放栈中元素
	int top;                                       //栈顶指针
}SqStack;                                          //顺序栈类型定义   sq:sequence顺序

//初始化顺序表
void InitStack(SqStack& S) {
	S.top = 0;
}

/*
此种设定下:
	栈顶元素的位置:S.top - 1
	初始时设置:S.top = 0
	栈顶元素:S.data[S.top - 1]
	栈空:S.top == 0
	栈满:S.top == MaxSize
	栈长:S.top

	进栈操作:栈不满时,先送值到栈顶元素,栈顶指针再+1
	出栈操作:栈非空时,先将栈顶指针-1,再取栈顶元素值
*/

//判空
bool StackEmpty(SqStack S) {
	if (S.top == 0) return true;
	else return false;
}

//要注意的是,需要改动栈本身的时候一定要加&

//入栈
bool Push(SqStack& S, ElemType x) {
	if (S.top == MaxSize) return false;        //栈满

	S.data[S.top] = x;
	S.top = S.top + 1;
	return true;
}


bool Push2(SqStack& S, ElemType x) {
	if (S.top == MaxSize) return false;        //栈满

	S.data[S.top++] = x;
	return true;
}

//出栈
bool Pop(SqStack& S, ElemType& x) {
	if (S.top == 0) return false;                //栈空

	S.top = S.top - 1;
	x = S.data[S.top];
	return true;
}

bool Pop2(SqStack& S, ElemType& x) {
	if (S.top == 0) return false;                //栈空

	x = S.data[--S.top];
	return true;
}

//读取栈顶元素
bool GetTop(SqStack S, ElemType& x) {
	if (S.top == 0) return false;

	x = S.data[S.top - 1];
	return true;
}

//以上所有基本操作时间复杂度为O(1)
//销毁(因为采用的是变量声明的方式分配得内存空间 未使用malloc函数 存储空间的回收由系统自动完成 故只需要完成清空操作即可)
void DestroyStack(SqStack& S) {
	S.top = 0;
}

int main() {
	SqStack S;
	InitStack(S);
	int x;
	bool sign;
	cout << "请连续输入要入栈的值 空格分界 999结束:\n";
	scanf_s("%d", &x);
	while (x != 999) {
		sign = Push(S, x);
		if (sign == false) {//由于顺序栈的入栈操作受数组上界的约束,当对栈的最大使用空间估计不足时,有可能发生栈上溢,此时应及时向用户报告消息
			cout << "栈最大容量为:" << MaxSize << ",当前栈已满,超出部分未入栈\n";
			break;
		}
		scanf_s("%d", &x);
	}

	int top;
	sign = GetTop(S, top);
	if (sign == true)
		cout << "当前栈顶元素为:" << top << "\n";
	else if (sign == false)
		cout << "栈空,读取栈顶元素失败\n";

	sign = Pop(S, top);
	if (sign == true)
		cout << "出栈元素为:" << top << "\n";
	else if (sign == false)
		cout << "栈空,出栈失败\n";

	sign = GetTop(S, top);
	if (sign == true)
		cout << "当前栈顶元素为:" << top << "\n";
	else if (sign == false)
		cout << "栈空,读取栈顶元素失败\n";

	sign = Pop2(S, top);
	if (sign == true)
		cout << "出栈元素为:" << top << "\n";
	else if (sign == false)
		cout << "栈空,出栈失败\n";

	sign = GetTop(S, top);
	if (sign == true)
		cout << "当前栈顶元素为:" << top << "\n";
	else if (sign == false)
		cout << "栈空,读取栈顶元素失败\n";

	return 0;
}

 共享顺序栈:

/*
栈:只允许在一段进行插入或删除操作的线性表
共享顺序栈:用顺序存储方式实现的栈,且两个栈共享同一个存储空间
*/
#include<cstdio>
#include<iostream>
using namespace std;

#define MaxSize 10                                 //定义顺序栈最大长度
#define ElemType int

typedef struct {
	ElemType data[MaxSize];                        //静态数组存放栈中元素
	int top0;                                      //0号栈栈顶指针
	int top1;                                      //1号栈栈顶指针
}SqStack;                                          //顺序栈类型定义   sq:sequence顺序

//初始化顺序表
void InitStack(SqStack& S) {
	S.top0 = -1;
	S.top1 = MaxSize;
}

/*
此种设定下:
	栈顶指针:S.top0、S.top1  (分别指向各自栈顶元素)
	初始时设置:S.top0 = -1 S.top1 = MaxSize
	栈顶元素:S.data[S.top0]、S.data[S.top1]
	栈空:S.top0 == -1/S.top1 == MaxSize
	栈满:S.top0 + 1 == S.top1

	进栈操作:栈不满时,栈顶指针先+1(对0号栈) -1(对1号栈),再送值到栈顶元素
	出栈操作:栈非空时,先取栈顶元素值,再将栈顶指针-1(对0号栈)   +1(对1号栈)
*/

//判空
bool StackEmpty(SqStack S,int i) {
	if (i != 0 && i != 1) {
		cout << "栈号指定错误 程序退出\n";
		exit(0);
	}

	if (i == 0) {
		if (S.top0 == -1) return true;
		else return false;
	}
	else if (i == 1) {
		if (S.top1 == MaxSize) return true;
		else return false;
	}
}

//要注意的是,需要改动栈本身的时候一定要加&

//入栈
bool Push(SqStack& S,int i, ElemType x) {
	if (i != 0 && i != 1) {
		cout << "栈号指定错误 程序退出\n";
		exit(0);
	}
	if (S.top0 + 1 == S.top1) return false;        //栈满
	if (i == 0) {
		S.top0 = S.top0 + 1;
		S.data[S.top0] = x;
		return true;
	}
	else if (i == 1) {
		S.top1 = S.top1 - 1;
		S.data[S.top1] = x;
		return true;
	}
	
}


bool Push2(SqStack& S,int i, ElemType x) {
	if (i != 0 && i != 1) {
		cout << "栈号指定错误 程序退出\n";
		exit(0);
	}

	if (S.top0 + 1 == S.top1) return false;        //栈满

	if(i == 0)
		S.data[++S.top0] = x;
	else if (i == 1)
		S.data[--S.top0] = x;
	
	return true;
}

//出栈
bool Pop(SqStack& S,int i, ElemType& x) {
	if (i != 0 && i != 1) {
		cout << "栈号指定错误 程序退出\n";
		exit(0);
	}
	if (i == 0) {
		if (S.top0 == -1) return false;                //栈空

		x = S.data[S.top0];
		S.top0 = S.top0 - 1;
		return true;
	}
	else if (i == 1) {
		if (S.top1 == MaxSize) return false;                //栈空

		x = S.data[S.top1];
		S.top1 = S.top1 + 1;
		return true;
	}
}

bool Pop2(SqStack& S,int i, ElemType& x) {
	if (i != 0 && i != 1) {
		cout << "栈号指定错误 程序退出\n";
		exit(0);
	}

	if (i == 0) {
		if (S.top0 == -1) return false;                //栈空

		x = S.data[S.top0--];
		return true;
	}
	else if (i == 1) {
		if (S.top1 == MaxSize) return false;                //栈空

		x = S.data[S.top1++];
		return true;
	}
}

//读取栈顶元素
bool GetTop(SqStack S,int i, ElemType& x) {
	if (i != 0 && i != 1) {
		cout << "栈号指定错误 程序退出\n";
		exit(0);
	}

	if (i == 0) {
		if (S.top0 == -1) return false;                //栈空

		x = S.data[S.top0];
		return true;
	}
	else if (i == 1) {
		if (S.top1 == MaxSize) return false;                //栈空

		x = S.data[S.top1];
		return true;
	}
}

//销毁(因为采用的是变量声明的方式分配得内存空间 未使用malloc函数 存储空间的回收由系统自动完成 故只需要完成清空操作即可)
void DestroyStack(SqStack& S) {
	S.top0 = -1;
	S.top1 = MaxSize;
}

int main() {
	SqStack S;
	InitStack(S);
	int x;
	bool sign;
	cout << "请连续输入要入栈0的值 空格分界 999结束:\n";
	scanf_s("%d", &x);
	while (x != 999) {       //实际测试发现,如果此处数值数就已经超过MaxSize break,则后续包含999在内的屏幕数值并未被读取,但会被下面的scanf_s继续读取,其实算个小bug
		sign = Push(S,0, x);
		if (sign == false) {//由于顺序栈的入栈操作受数组上界的约束,当对栈的最大使用空间估计不足时,有可能发生栈上溢,此时应及时向用户报告消息
			cout << "栈最大容量为:" << MaxSize << ",当前栈已满,超出部分未入栈\n";
			break;
		}
		scanf_s("%d", &x);
	}
	cout << "请连续输入要入栈1的值 空格分界 999结束:\n";
	scanf_s("%d", &x);
	while (x != 999) {
		sign = Push(S, 1, x);
		if (sign == false) {//由于顺序栈的入栈操作受数组上界的约束,当对栈的最大使用空间估计不足时,有可能发生栈上溢,此时应及时向用户报告消息
			cout << "栈最大容量为:" << MaxSize << ",当前栈已满,超出部分未入栈\n";
			break;
		}
		scanf_s("%d", &x);
	}

	int top;
	cout << "------下面操作栈0------\n";
	sign = GetTop(S,0, top);
	if (sign == true)
		cout << "当前栈顶元素为:" << top << "\n";
	else if (sign == false)
		cout << "栈空,读取栈顶元素失败\n";

	sign = Pop(S,0, top);
	if (sign == true)
		cout << "出栈元素为:" << top << "\n";
	else if (sign == false)
		cout << "栈空,出栈失败\n";

	sign = GetTop(S,0, top);
	if (sign == true)
		cout << "当前栈顶元素为:" << top << "\n";
	else if (sign == false)
		cout << "栈空,读取栈顶元素失败\n";

	sign = Pop2(S,0, top);
	if (sign == true)
		cout << "出栈元素为:" << top << "\n";
	else if (sign == false)
		cout << "栈空,出栈失败\n";

	sign = GetTop(S,0, top);
	if (sign == true)
		cout << "当前栈顶元素为:" << top << "\n";
	else if (sign == false)
		cout << "栈空,读取栈顶元素失败\n";

	cout << "------下面操作栈1------\n";
	
	sign = GetTop(S, 1, top);
	if (sign == true)
		cout << "当前栈顶元素为:" << top << "\n";
	else if (sign == false)
		cout << "栈空,读取栈顶元素失败\n";

	sign = Pop(S, 1, top);
	if (sign == true)
		cout << "出栈元素为:" << top << "\n";
	else if (sign == false)
		cout << "栈空,出栈失败\n";

	sign = GetTop(S, 1, top);
	if (sign == true)
		cout << "当前栈顶元素为:" << top << "\n";
	else if (sign == false)
		cout << "栈空,读取栈顶元素失败\n";

	sign = Pop2(S, 1, top);
	if (sign == true)
		cout << "出栈元素为:" << top << "\n";
	else if (sign == false)
		cout << "栈空,出栈失败\n";

	sign = GetTop(S, 1, top);
	if (sign == true)
		cout << "当前栈顶元素为:" << top << "\n";
	else if (sign == false)
		cout << "栈空,读取栈顶元素失败\n";

	return 0;
}

这篇关于数据结构C/C++实现——栈之顺序栈(含共享顺序栈)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!