顺序栈的表示和实现

顺序栈的定义

typedef struct{

SElemType *base; //存储空间基址

SElemType *top; //栈指针

int stacksize; //分配容量

)SqStack;

2.基本操作的函数原型

1）创建

Status InitStack(SqStack &S);

操作结果：构造一个空栈S

2)销毁

Status DestroyStack(SqStack &S)；

操作结果：销毁栈S，S不再存在

3）探空

Status StackEmpty(SqStack S)；

操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE

4）清空栈

Status ClearStack(SqStack &S)；

操作结果：把S置为空栈

5）求栈长

Status StackLength(SqStack S)；

操作结果：返回S的元素个数

6）获取栈顶元素

Status GetTop(SqStack S,SElemType &e)；

操作结果：若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR

7）入栈

Status Push(SqStack &S,SElemType e)；

操作结果：插入元素e为新的栈顶元素

8）出栈

Status GetTop(SqStack S,SElemType &e)；

操作结果：若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR

9）输出栈中全部元素

void Print(SqStack S)；

操作结果：输出栈中的全部元素

顺序栈的表示和实现

3.附录（代码）

//------*-----*------
//程序名称：顺序栈的实现
//编译环境：VC++ 6.0
//作者：Bee_darker
//修改日期：2018-10-22

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define  OVERFLOW  -1
#define  OK         1
#define  ERROR      0
#define  TRUE       1
#define  FALSE      0


#include<stdio.h>
#include<stdlib.h>

typedef  int  Status;
typedef  int  SElemType;

//定义顺序栈
typedef struct{
  SElemType  *base;
  SElemType  *top;
  int   stacksize;
}SqStack;

//初始化
Status InitStack(SqStack &S)
{
	S.base = (SElemType * )malloc(STACK_INIT_SIZE*sizeof(SElemType));
	if(!S.base)
		exit (OVERFLOW);
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
	return OK;
}

//入栈操作
Status Push(SqStack  &S,SElemType e)
{
	if(S.top-S.base >= S.stacksize)
	{
		S.base = (SElemType * )realloc(S.base,
					  (S.stacksize+STACKINCREMENT)*sizeof(SElemType));
		if(!S.base)
			exit  (OVERFLOW);
		S.top = S.base+S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;
	return OK;
}

//获取栈顶元素
Status GetTop(SqStack S,SElemType &e)
{
	if(S.top == S.base)
		return ERROR;
	e = *(S.top-1);
	return OK;
}

//出栈操作
Status Pop(SqStack &S,SElemType &e)
{
	if(S.top == S.base)
		return  ERROR;
	e = * --S.top;
		return OK;
}

//求栈长
Status StackLength(SqStack S)
{
	return S.top-S.base;
}

//清空栈
Status ClearStack(SqStack &S)
{
	S.top = S.base;
	return OK;
}

//探空
Status StackEmpty(SqStack S)
{
	if(S.top == S.base)
		return TRUE;
	else
		return FALSE;
}

//输出栈中元素
void Print(SqStack S)
{
	SElemType x;
	while(S.top-S.base != 0)
	{
		x = * --S.top;
		printf("%d\t",x);
	}
}

//销毁栈
Status DestroyStack(SqStack &S)
{
	S.base == NULL;
	return OK;
}

int main()
{
	SqStack S;
	int x,e;
	InitStack(S);
	Push(S,1);
	Push(S,2);
	Push(S,3);
	printf("%d\n",StackLength(S));
	Print(S);
	printf("\n");
	Pop(S,x);
	printf("%d\n",x);
	Print(S);
	printf("%d\n",StackEmpty(S));
	printf("%d\n",GetTop(S,e));
	ClearStack(S);
	printf("%d\n",StackLength(S));
	DestroyStack(S);
	return 0;
}

顺序栈的表示和实现

相关推荐