顺序栈的表示和实现

参考书目：《数据结构(C语言版)》，严蔚敏

/~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

思考：对于栈和栈的Pop()函数的理解。

我原本以为Pop()函数就是一个删除栈顶元素的函数，但如果这样的话，那么他和线性表中的delete函数又有啥区别呢？

思考之后我觉得应这样理解：栈可以看成是一个后进先出的buffer。数据进栈后，待栈中元素满足程序要求时，便要进行出栈操作，这时就要调用Pop()函数，当栈中所有的元素都出栈后，此时栈就空了，等待下次数据的到来，这有点类似单片机中具有LIFO(last in first out)结构的buffer。

（完全是自己悟的，也不知道理解的对不对，还请各位指正）

当然栈也可以当做线性表来用，毕竟栈就是由线性表而来的，但我感觉实际应用没有必要这样。因为既然重新定义栈这样的数据结构，在实际应用中栈的这种操作必然有其用武之地。

注意：鉴于以上分析，程序中调用的StackDisp()函数并未按照后进先出这一规定显示stack的，当然完全可以将其改为按后进先出的规定来显示stack的，不过我估计在实际应用中StackDisp()函数未必排得上用场。

/~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

common.h

#ifndef	_COMMON_H_
#define	_COMMON_H_
 
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE  -1
#define OVERFLOW    -2
 
typedef int Status;  
 
//Status Equal(int a, int b);
 
#endif

stack.h

#ifndef	_STACK_H_
#define	_STACK_H_
 
#define	STACK_INIT_SIZE		10
#define	STACKINCREMENT		10
 
typedef int	SElemType;
 
typedef struct
{
	SElemType *base;	//在栈构造之前和销毁之后，base的值为NULL
	SElemType *top;		//栈顶指针
	int stacksize;		//当前已分配的存储空间，以元素为单位
}SqStack;
 
Status	InitStack(SqStack *S);
	//构造一个空栈S
 
Status StackScanf(SqStack *S);
	//向指定的stack输入数据
 
Status StackDisp(SqStack *S);
	//显示指定的stack
 
int StackLength(SqStack *S);
	//返回指定stack的元素个数，即栈的长度
 
Status GetTop(SqStack *S,SElemType *e);
	//若栈不空，则将S的栈顶元素传递给*e，并返回OK;否则返回ERROR
 
Status Push(SqStack *S,SElemType e);
	//插入数据e为新的栈顶元素
 
Status Pop(SqStack *S,SElemType *e);
	//若栈不空，则删除指定栈的栈顶元素，并用e返回其值，并返回OK；否则返回ERROR。
 
Status DestroyStack(SqStack *S);
	//销毁指定栈
 
Status ClearStack(SqStack *S);
	//清空指定栈
 
Status StackEmpty(SqStack *S);
	//判断指定栈是否为空，若为空栈，则返回TRUE，否则返回FALSE.
 
#endif

stack.c

#include "stdio.h"
#include "stdlib.h"
#include "common.h"
#include "stack.h"
 
/*
输入参数：*S	待处理的栈地址
返回参数：OVERFLOW		存储分配失败
		   OK			成功
函数功能：初始化栈，构造一个空栈。
*/
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;
}
 
/*
输入参数：*S	待处理的栈地址
返回参数：OK	操作成功
		   OVERFLOW		stack满
		   还可以根据实际情况定义相应的返回值
函数功能：向指定的stack输入数据，约定若输入0则结束，并将0存储stack。
	注意：在stack的存储空间够用的情况下，调用该函数得到的栈顶元素都为0，若想栈顶元素不为0可以调用Push()函数。
*/
Status StackScanf(SqStack *S)
{
	SElemType *cap_max;
	cap_max = S->base + S->stacksize - 1;	//减1的原因是：留一个存储单元给栈顶指针，即当stack的存储单元用完时，使栈顶指针指向存储空间的最后一个存储单元。
	scanf("%d",S->top);
	S->top++;
	while(*(S->top-1))
	{
		scanf("%d",S->top);
		S->top++;
		if(S->top >= cap_max)
		{
			printf("The stack is full.");	//实际应用时当然还可以在这里继续为原stack扩充容量。
			return OVERFLOW;
		}
	}
	return OK;
}
 
/*
输入参数：*S	待显示的栈地址
返回参数：OK	操作成功
		   还可以根据实际情况定义相应的返回值
函数功能：显示指定的stack
注意：程序中调用的StackDisp()函数并未按照后进先出这一规定显示stack的，当然完全可以将其改为按后进先出的规定来显示stack的，不过我估计在实际应用中StackDisp()函数未必排得上用场。
*/
Status StackDisp(SqStack *S)
{
	SElemType *bottom = S->base;
	printf("\n*************** output start ***************\n");
	while(bottom<S->top)
	{
		printf("%d  ",*bottom);
		bottom++;
	}
	printf("\n*************** output end ***************\n");
	return OK;
}
 
/*
输入参数：*S	待处理的栈地址
返回参数：*S所指向的stack的长度，即该stack中的元素个数
函数功能：返回指定stack的元素个数，即栈的长度
*/
int StackLength(SqStack *S)
{
	//可根据需要在这里添加判断S是否满足一些条件，如判断*S指向的stack是否存在等，因为栈是否存在和栈是否空有时还是有区别的。
	//if(!(S->top||S->top))		//判断栈是否存在，这个当然要在销毁栈时将栈顶指针和栈底指针都清为0才能在此有所判断。
	//	return -1;
	return(S->top - S->base);
}
 
/*
输入参数：*S	待处理的栈地址
		   *e	用于存储栈顶元素
返回参数：ERROR		该栈为空
		   OK			操作成功
函数功能：若栈不空，则将S的栈顶元素传递给*e，并返回OK;否则返回ERROR.
*/
Status GetTop(SqStack *S,SElemType *e)
{
	if(!StackLength(S))
		return ERROR;
	else
	{
		*e = *(S->top - 1);
	}
	return OK;
}
 
/*
输入参数：*S	待处理的栈地址
		   e	待插入的数据
返回参数：OVERFLOW		stack满
		   OK			操作成功
函数功能：插入数据e为新的栈顶元素
*/
Status Push(SqStack *S,SElemType e)
{
	if(StackLength(S) >= 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;
}
 
/*
输入参数：*S	待处理的栈地址
		   *e	待返回的栈顶元素
返回参数：ERROR	操作失败
		   OK		操作成功
函数功能：若栈不空，则删除指定栈的栈顶元素，并用e返回其值，并返回OK；否则返回ERROR。
*/
Status Pop(SqStack *S,SElemType *e)
{
	if(StackLength(S) <= 0)
		return ERROR;
	*e = * --S->top;
	return OK;
}
 
/*
输入参数：*S	待销毁的栈地址
返回参数：OK	操作成功
		   还可根据需要加入别的返回值
函数功能：销毁指定栈
*/
Status DestroyStack(SqStack *S)
{
	free(S->base);
	S->base = NULL;
	S->top = NULL;
	S->stacksize = 0;
	return OK;
}
 
/*
输入参数：待清空的栈地址
返回参数：OK	操作成功
函数功能：清空指定栈
*/
Status ClearStack(SqStack *S)
{
	S->top = S->base;
	return OK;
}
 
/*
输入参数：*S	待处理的栈地址
返回参数：FALSE	指定的栈非空
		   OK		指定的栈为空
函数功能：判断指定栈是否为空，若为空栈，则返回TRUE，否则返回FALSE.
*/
Status StackEmpty(SqStack *S)
{
	//if(!(S->top||S->top))		//判断栈是否存在，这个当然要在销毁栈时将栈顶指针和栈底指针都清为0才能在此有所判断。
	//	return -1;
	if(S->top - S->base)
	{return FALSE;}
	return TRUE;
}

 

main.c

//>>>第3章/3.1节
#include "stdio.h"
#include "stdlib.h"
#include "common.h"	//这个头文件一定要包含在stack.h前，因为在头文件stack.h中会用到common.h头文件中的定义。
#include "stack.h"
 
int main(void)
{
	int top_elem=0;
	SqStack stack;
	InitStack(&stack);
	StackScanf(&stack);
	
	StackDisp(&stack);
	printf("The current stack length is %d.\n",StackLength(&stack));
	GetTop(&stack,&top_elem);
	printf("The top element is %d.\n",top_elem);
	
	Push(&stack,1010);
	
	StackDisp(&stack);
	printf("The current stack length is %d.\n",StackLength(&stack));
	GetTop(&stack,&top_elem);
	printf("The top element is %d.\n",top_elem);
 
	Pop(&stack,&top_elem);
 
	StackDisp(&stack);
	printf("The current stack length is %d.\n",StackLength(&stack));
	GetTop(&stack,&top_elem);
	printf("The top element is %d.\n",top_elem);
	printf("~~~~~~~~~~~~~~~~\n");
	printf("%d\n",*stack.top);	//之前的栈顶元素还存在，只不过是栈顶指针后退了一位而已。
	printf("~~~~~~~~~~~~~~~~\n");
 
	Push(&stack,2020);
	Push(&stack,3030);
	Push(&stack,4040);
	Push(&stack,5050);
	
	StackDisp(&stack);
	printf("The current stack length is %d.\n",StackLength(&stack));
	GetTop(&stack,&top_elem);
	printf("The top element is %d.\n",top_elem);
	top_elem = 0;
 
	ClearStack(&stack);
	printf("\nAfter clear stack:\n");
	StackDisp(&stack);
	printf("The current stack length is %d.\n",StackLength(&stack));
	GetTop(&stack,&top_elem);
	printf("The top element is %d.\n",top_elem);
	top_elem = 0;
 
	DestroyStack(&stack);
	printf("\nAfter destroy stack:\n");
	StackDisp(&stack);
	printf("The current stack length is %d.\n",StackLength(&stack));
	GetTop(&stack,&top_elem);
	printf("The top element is %d.\n",top_elem);
 
	return 0;
}

 

下面这个是后来调试所加的，当然可以将两个main文件合并。

main.c

//第3章/3.2节
#include "stdio.h"
#include "stdlib.h"
#include "common.h"		//这个头文件一定要包含在stack.h前，因为在头文件stack.h中会用到common.h头文件中的定义。
#include "stack.h"
#include "example.h"
 
int main(void)
{
	Conversion(1348,8);
	return 0;
}

运算结果如下（第一个main文件）：