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

2022-09-18 12:32:04

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;
}

码农公寓

相关文章