LV010-顺序栈简介

一、顺序栈

1. 存储结构

顺序栈，即用顺序表实现栈存储结构。顺序表（底层实现是数组）和栈的存储数据的方式非常想似，只不过栈对数据的存取过程有特殊的限制，而顺序表没有。

2. 结构体实现

可以把顺序栈看做是顺序表的一种，具有顺序表同样的存储结构，由数组定义，配合用数组下标表示的栈顶指针 top （相对指针）完成各种操作。顺序栈数据类型定义的 C 语言实现如下：

typedef int data_t; /* 定义栈中数据元素的数据类型 */

typedef struct 
{
	data_t *data;  /* 用指针指向栈的存储空间 */
	int maxlen;    /* 当前栈的最大元素个数 */
	int top;       /* 指示栈顶位置(数组下标)的变量 */
}seqstack;         /* 顺序栈类型定义 */

3. 顺序栈基本操作

相关的源代码可以在这里下载：

数据结构	栈 (密码: du8k)

#### 3.1 创建顺序栈

/**
 * @Function: seqstack_create
 * @Description: 顺序栈创建
 * @param len: 顺序栈的最大长度 
 * @return  : 返回一个地址
 *            NULL, 创建失败;
 *            other, 创建成功
 */
seqstack * seqstack_create(int len) 
{
	/* 定义一个顺序栈结构体变量 */
	seqstack * S;
	/* 1.申请栈空间 */
	if ((S =(seqstack *)malloc(sizeof(seqstack))) == NULL) 
	{
		printf("seqstack malloc failed!\n");
		return NULL;
	}
	/* 2.申请栈中元素数据空间 */
	if ((S->data = (data_t *)malloc(len * sizeof(data_t)))==NULL) 
	{
		printf("seqstack data malloc data failed！\n");
		free(S); /* 申请失败后，释放前边申请的栈空间 */
		return NULL;
	}
	
	/* 3.申请的内存空间位于堆上，需要进行初始化 */
	memset(S->data, 0, len * sizeof(data_t));
	S->maxlen = len;
	S->top = -1;

	return S;
}

3.2 栈状态检测

3.2.1 栈是否为空

/**
 * @Function: seqstack_empty
 * @Description: 顺序栈是否为空
 * @param s : 顺序栈地址
 * @return  : 返回一个数值
 *            0, 顺序栈非空;
 *            1, 顺序栈为空;
 *            -1, 顺序栈不存在
 */
int seqstack_empty(seqstack * S)
{
	/* 1.判断栈空间是否存在 */
	if (S == NULL) 
	{
		printf("seqstack is not existed!\n");
		return -1;
	}
	
	/* 2.判断栈的状态 */
	if(S->top == -1) 
		return 1;
	else
		return 0;
	/* 或者写成下边的 */
	//return (s-> top == -1 ? 1 : 0); 
}

3.2.2 栈是否已满

/**
 * @Function: seqstack_full
 * @Description: 顺序栈是否已满
 * @param s : 顺序栈地址
 * @return  : 返回一个数值
 *            0, 顺序栈未满;
 *            1, 顺序栈已满;
 *            -1, 顺序栈不存在
 */
int seqstack_full(seqstack * S)
{
	/* 1.判断栈空间是否存在 */
	if (S == NULL) 
	{
		printf("seqstack is not existed!\n");
		return -1;
	}
	
	/* 2.判断栈的状态 */
	if(S->top == S->maxlen-1) 
		return 1;
	else
		return 0;
	/* 或者写成下边的 */
	//return (s-> top == -1 ? 1 : 0); 
}

3.3 数据入栈

/**
 * @Function: seqstack_push
 * @Description: 入栈
 * @param S : 顺序栈地址
 * @param value : 要入栈的数据
 * @return  : 返回一个数值
 *            0, 释放成功;
 *            -1, 顺序栈不存在或者栈已满
 */
int seqstack_push(seqstack * S, data_t value) 
{
	/* 1.判断栈空间是否存在 */
	if (S == NULL) 
	{
		printf("seqstack is not existed!\n");
		return -1;
	}
	/* 2.判断栈空间是否已满 */
	if (S->top == S->maxlen-1) 
	{
		printf("seqstack is full!\n");
		return -1;
	}
	/* 3.更新数据 */
	S->top++;
	S->data[S->top] = value;

	return 0;
}

3.4 数据出栈

【注意】这里出栈的时候不要做栈是否存在以及是否为空的判断，这两个判断若是有返回值的话程序会认为返回值就是出栈的元素，所以栈的存在性以及是否为空，要在使用出栈函数前进行判断。

/**
 * @Function: seqstack_push
 * @Description: 出栈
 * @param S : 顺序栈地址
 * @return  : 返回一个栈中数据
 */
data_t seqstack_pop(seqstack * S) 
{
	/* 1. 判断栈空间为否为空 */
	/* 这一步不需要，因为栈中元素可能是任意数值，所以这里做判断并不合适，需要在函数外判断 */
	/* 2. 数据出栈 */
	S->top--;
	return (S->data[S->top+1]);
}

3.5 清空栈

/**
 * @Function: seqstack_clear
 * @Description: 顺序栈清空
 * @param s : 顺序栈地址
 * @return  : 返回一个数值
 *            0, 顺序栈清空成功;
 *            -1, 顺序栈不存在
 */
int seqstack_clear(seqstack * S)
{
	/* 1.判断栈空间是否存在 */
	if (S == NULL) 
	{
		printf("seqstack is not existed!\n");
		return -1;
	}
	
	/* 2.清空栈，可以说是认为没有数据，那么它就没有数据 */
	S->top = -1; 
	return 0;
}

3.6 释放顺序栈

/**
 * @Function: seqstack_free
 * @Description: 释放顺序栈空间及数据空间
 * @param S : 顺序栈地址
 * @return  : 返回一个数值
 *            0, 释放成功;
 *            -1, 顺序栈不存在 
 */
int seqstack_free(seqstack * S) 
{
	/* 1.判断顺序栈空间是否存在 */
	if (S == NULL) 
	{
		printf("seqstack is not existed!\n");
		return -1;
	}
	/* 2.释放顺序栈中所有元素空间 */
	if (S->data != NULL)
	{
		free(S->data);
	}	
	/* 3.释放顺序栈结构体变量空间 */
	free(S);
	printf("seqstack free completed!\n");

	return 0;
}

3.7 显示顺序栈

/**
 * @Function: seqstack_show
 * @Description: 顺序栈数据显示
 * @param s : 顺序栈地址
 * @return  : 返回一个数值
 *            0, 顺序栈显示成功;
 *            -1, 顺序栈不存在或者顺序栈为空
 */
int seqstack_show(seqstack * S)
{
	int i = 0;
	/* 1.判断栈空间是否存在 */
	if (S == NULL) 
	{
		printf("seqstack is not existed!\n");
		return -1;
	}
	/* 2. 判断顺序栈是否为空 */
	if (S->top == -1) 
	{
		printf("seqstack is empty!\n");
		return -1;
	}
	/* 2. 显示顺序栈元素 */
	printf("seqstack: ");
	while(i <= S->top)
	{
		printf("%d ", S->data[i]);
		i++;
	}
	puts("");
	 
	return 0;
}