淘先锋技术网

首页 1 2 3 4 5 6 7

顺序栈的实现

和之前的线性表的实现一样,此处定义的数据类型还是以学生的学号和姓名为例子。

#include <iostream>
#include <string>
using namespace std;
#define MAXNUM 10

typedef struct{
	int num;
	string name;
}ElemType;

typedef struct{
	ElemType *base;
	ElemType *top;
	int stacksize;
}SeqStack;

符号解释:

  • MAXNUM:栈的最大容量
  • ∗ * base, ∗ * top:一个指向数组的指针,但容量仍未确定。在初始化的时候会去确定为MAXNUM,也就是10。可以理解为类似数组a[10]中的a。
  • stacksize:栈的最大容量,实质和MAXNUM是一样的。

理解完符号,那下面就去实现它的功能。栈的主要功能是用于实现后进先出的线性表,应用场景有进制转换,括号匹配检验和表达式求值等。接着下去看代码吧~

void InitialSeqStack(SeqStack &S){
	S.base = new ElemType[MAXNUM];
	if(!S.base)
		exit(OVERFLOW);
	S.top = S.base;
	S.stacksize = MAXNUM;
}

int SeqStack_length(SeqStack S){
	return S.top-S.base;
}

bool SeqStackIsEmpty(SeqStack S){
	if(S.base == S.top)
		return true;
	return false;
}

void ClearSeqStack(SeqStack &S){
	S.top = S.base;
	cout << "顺序栈已清空!" << endl;
}

void DestroySeqStack(SeqStack &S){
	if(S.base){
		delete S.base;
		S.stacksize = 0;
		S.top = S.base = NULL;
		cout << "顺序栈已销毁!"<< endl;
	}
}

void PushSeqStack(SeqStack &S,ElemType e){
	if(S.top-S.base == S.stacksize)
		cout << "栈已满!" << endl;
	else{
		*S.top++ = e;
		cout << "入栈成功!" << endl;
	}
}

void PopSeqStack(SeqStack &S,ElemType &e){
	if(S.base == S.top)
		cout << "栈为空!" << endl;
	else{
		e = *--S.top;
		cout << "出栈成功!" << endl;
	}
}

ElemType GetTopSeqStack(SeqStack S){
	return *--S.top;
}

int main(){
	SeqStack S;
	InitialSeqStack(S);
	if(SeqStackIsEmpty(S))
		cout << "栈为空!" << endl;
	ElemType e1 = {1,"张三"};
	ElemType e2 = {2,"李四"};
	PushSeqStack(S,e1);
	PushSeqStack(S,e2);
	cout << "栈里内容长度为:" << SeqStack_length(S) << endl;
	ElemType e3,e4;
	PopSeqStack(S,e3);
	PopSeqStack(S,e4);
	cout << "学号:" << e3.num << " 姓名:" << e3.name << endl;
	cout << "学号:" << e4.num << " 姓名:" << e4.name << endl;
	cout << "栈里内容长度为:" << SeqStack_length(S) << endl;
	system("pause");
	return 0;
}

下面主要给大家介绍一下进栈和出栈的实现过程,理解了这个其他的功能就都能解决了。

  • 进栈过程。先把top->data赋值为e,再将top指针向上移动一位。
    在这里插入图片描述

  • 出栈过程。先把top下移一位,再把top->data赋值给e。
    在这里插入图片描述

关于顺序栈的实现就到这里。若大家有不懂的地方可以在评论区提问噢~