大话数据结构-4.4 栈的顺序存储结构及实现 92- 高飞网

4.4 栈的顺序存储结构及实现 92

2016-12-20 23:35:29.0

4.4 栈的顺序存储结构及实现

4.4.1 栈的顺序存储结构

    用数组来表示栈,以下标为0的一端作为栈底。

栈的结构定义:

/* 顺序栈 */

#define MAXSIZE 5
typedef int SElemType;
typedef struct
{
	SElemType data[MAXSIZE];
	int top;
}SqStack;

    若现在有一个栈,StackSize是5,则栈普通情况、空栈和栈满的情况示意图如下:

4.4.2 栈的顺序存储结构——进栈操作


Status Push(SqStack *S,SElemType e)	//若栈S存在,将新元素e插入栈S中并成为栈顶元素
{
	if(S->top == MAXSIZE -1)
	{
		return ERROR;//已满
	}
	S->top++;
	S->data[S->top] = e;
	return OK;
}

4.4.3 栈的顺序存储结构——出栈操作

Status Pop(SqStack *S,SElemType *e)	//删除栈S中栈顶元素,并用e返回其值
{
	if(StackEmpty(*S))
	{
		return ERROR;//为空
	}
	*e = S->data[S->top];
	S->top--;
	return OK;
}

4.5 两栈共享空间

    栈的顺序存储相比顺序链表来说,要方便的多,因为没有了插入或删除操作时的移动元素问题。但它也有缺陷,就是数组大小是固定的,默认情况下只能存储有限的元素个数。

    如果能让两个栈共用存储空间,那么如果一个栈已满,不用再开辟新的空间,用另一个栈的空间即可,这样会提高空间的利用率。

    数组有两个端点,两个栈有两个栈底,让一个栈的栈底为数组的始端,即下标为0处,另一个栈为栈的末端,即下标为数组长度n-1处。这样,两个栈如果增加元素,就是两端点向中间延伸。

    关键思路:它们是在数组的两端,向中间靠拢。top1和top2是栈1和栈2的栈顶指针,可以想象,只要它们不见面,两个栈就可以一直使用。

    栈空间的结构代码:

/*两栈共享空间--顺序栈结构 */

#define MAXSIZE 5
typedef int SElemType;
typedef struct
{
	SElemType data[MAXSIZE];
	int top1;	//栈1 栈顶指针
	int top2;	//栈2 栈顶指针
}SqDoubleStack;

    对于两栈空间的push方法,除了要插入元素值参数外,还需要一个判断是栈1还是栈2的栈号参数stackNumber。

Status Push(SqDoubleStack *S,SElemType e,int stackNumber)
{//若栈S存在,将新元素e插入栈S中并成为栈顶元素
if(S->top1 +1 == S->top2) { return ERROR;//已满 } if(1==stackNumber) { S->top1++; S->data[S->top1] = e; return OK; } else if(2==stackNumber) { S->top2--; S->data[S->top2] = e; return OK; } return ERROR; }

    因为这里判断了栈满的情况,所以top1+1和top2-1是不担心溢出问题。

    对于两栈的pop方法:

Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)	//删除栈S中栈顶元素,并用e返回其值
{
	if(StackEmpty(*S,stackNumber))
	{
		return ERROR;//为空
	}
	if(1==stackNumber)
	{
		*e = S->data[S->top1];
		S->top1--;
		return OK;

	}
	else if(2==stackNumber)
	{
		*e = S->data[S->top2];
		S->top2++;
		return OK;
	}
	return ERROR;
}

    使用这样的数据结构,通常都是当两个栈空间需求有相反关系时,也就是一个栈增长时另一个栈在缩短的情况。如卖股票一样,有买有卖。否则两个栈都在不停地增长,很快会因栈满而溢出了。