栈的顺序存储结构

栈的顺序存储

参考《大话数据结构》——程杰

栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构。

进栈出栈变化形式

最先进栈的元素不一定最后出栈。

栈对线性表的插入和删除的位置进行了限制，并没有对元素进出的时间进行限制，在不是所有元素都进栈的情况下，事先进栈的元素也可以出栈，只要保证时栈顶元素出栈就可以。

顺序栈代码实现

当栈存又一个元素时，top等于0，因此通常把空栈的判定条件定位top等于-1。

#define MAX_SIZE 10
typedef enum Status
{
	OK=0,
	ERROR
};
typedef int SElemType;
typedef struct SqStack
{
	SElemType data[MAX_SIZE];
	int top;
};

/*线性栈初始化*/
void SqStackInit(SqStack *s)
{
	s->top = -1;
}

/*线性栈是否为空*/
bool IsStackEmpty(SqStack s)
{
	if (s.top==-1)
	{
		return true;
	}
	else
	{
		return false;
	}
}
/*线性栈入栈*/
Status Push(SqStack *s, SElemType e)
{
	if (s->top==MAX_SIZE-1)
	{
		return ERROR;
	}
	s->top++;
	s->data[s->top] = e;
	return OK;
}
/*线性表出栈*/
Status Pop(SqStack *s, SElemType &e)
{
	if (s->top==-1)
	{
		return ERROR;
	}
	else
	{
		e = s->data[s->top];
		s->top--;
		return OK;
	}
}
int main()
{
	SqStack S;
	SElemType e;
	SqStackInit(&S);
	for (int i=0;i<MAX_SIZE;i++)
	{
		Push(&S, i);
		printf("%d,", i);
	}
	printf("\n");
	for (int i = 0; i < MAX_SIZE; i++)
	{
		Pop(&S, e);
		printf("%d,", e);
	}
}

两栈共享空间

让两个栈的栈底分别位于数组的始端与末端。两个栈增加元素，就是两端点向中间延伸。

/*两栈共享空间初始化*/
void SqStackInit(SqDoubleStack *s)
{
	s->top1 = -1;
	s->top2 = MAX_SIZE;
}
/*两栈共享空间入栈*/
Status Push(SqDoubleStack *s, SElemType e,int stackNumber)
{
	if (s->top1+1 == s->top2)
	{
		return ERROR;
	}
	if (stackNumber==1)/*判断是哪个栈要压入数据*/
	{
		s->top1++;
		s->data[s->top1] = e;
	}
	else
	{
		s->top2--;
		s->data[s->top2] = e;
	}
	return OK;
}
/*两栈共享空间出栈*/
Status Pop(SqDoubleStack *s, SElemType &e, int stackNumber)
{
    if (stackNumber==1)
    {
        if (s->top1 == -1)
        {
            return ERROR;
        }
        else
        {
            e = s->data[s->top1];
            s->top1--;
        }
    }
    else if (stackNumber==2)
    {
        if (s->top2 == MAX_SIZE)
        {
            return ERROR;
        }
        else
        {
            e = s->data[s->top2];
            s->top2++;
        }
    }
    return OK;
}

int main()
{
	SqDoubleStack S1;
	SElemType e;
	SqStackInit(&S1);
	for (int i=0;i<3;i++)
	{
		Push(&S1, i,1);
		printf("%d,", i);
	}
	printf("\n");
	for (int i = 3; i < 5; i++)
	{
		Push(&S1, i, 2);
		printf("%d,", i);
	}
	printf("\n");
	for (int i = 0; i < MAX_SIZE; i++)
	{
		if (Pop(&S1, e, 1)==ERROR)
		{
			break;
		}
		printf("%d,", e);
	}
	printf("\n");
	for (int i = 0; i < MAX_SIZE; i++)
	{
		if (Pop(&S1, e, 2) == ERROR)
		{
			break;
		}
		printf("%d,", e);
	}
}