大话数据结构笔记：栈的顺序存储结构和链式存储结构

一、栈的顺序存储结构

       栈的结构定义：

#define MAXSIZE 20          //20后不能加分号
typedef struct
{
	int data[MAXSIZE];
	int top;                //栈顶指针
}SqStack;

       栈顶位置必须小于存储栈的长度，当栈存在一个元素时，top=0，因此通常把空栈的判定条件定为top=-1。

1.进栈操作

//插入元素e为新的栈顶元素
int Push(SqStack *S, int e)
{
	if(S->top == MAXSIZE -1)       //栈满
		return 0;

	S->top++;                      //栈顶指针加一
	S->data[S->top] = e;           //将新插入元素赋值给栈顶空间
	return 1;
}

2.出栈操作

//若栈不为空，则删除S的栈顶元素，用e返回其值，并返回1，否则返回0

int Pop(SqStack *S, int *e)
{
	if(S->top == -1)
		return 0;

	*e = S->data[S->top];               //将要删除的栈顶元素赋值给e
	S->top--;                           //栈顶指针减一
	return 1;
}

       两个函数的时间复杂度均是O(1)。

3.两栈共享空间

       有两个栈，栈顶指针分别为top1和top2，当两栈都为空时，两个栈的栈顶指针都在栈的两端，并且top1等于-1，top2等于n。栈1入栈栈顶指针top1++，栈2入栈栈顶指针top2–，栈满的情况下top1 + 1等于top2，即极端情况下，栈满时，若栈2是空的，则top1等于n-1，即栈1满了，相反栈满时，栈1为空，top2等于0，即栈2满。

       两栈共享空间的结构代码：

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

①入栈操作

//插入元素e为新的栈顶元素，stackNumber为判断对栈1操作还是对栈2操作
int Push(SqDoubleStack *S, int e, int stackNumber)
{
	if(S->top1+1 == S->top2)            //栈已满，不能再push新元素了
		return 0;

	if(stackNumber == 1)                //栈1有元素进栈
		S->data[++S->top1] = e;         //top1+1后给数组元素赋值
	else if(stackNumber == 2)           //栈2有元素进栈
		S->data[--S->top2] = e;         //top2+1后给数组元素赋值
	return 1;
}

②出栈操作

int Pop(SqDoubleStack *S, int *e, int stackNumber)
{
	if(stackNumber == 1)
	{
		if(S->top1 == -1)
			return 0;                   //说明栈1已经是空栈，溢出
		*e = S->data[S->top1--];
	}
	else if(stackNumber == 2)
	{
		if(S->top2 == MAXSIZE)
			return 0;                  //说明栈1已经是空栈，溢出
		*e = S->data[S->top2++];
	}
	return 1;
}

二、栈的链式存储结构

       单链表的头指针是必须的，栈顶指针也是必须的，所以可以将两者合二为一，对于链栈，也就不需要头结点了。当链栈为空时，top=NULL。

       链栈的结构代码：

typedef struct StackNode
{
	int data;
	struct StackNode *next;
}StackNode,*LinkStackPtr;

typedef struct LinkStack
{
	LinkStackPtr top;
	int count;
}LinkStack;

1.进栈操作

int Push(LinkStack *S, int e)
{
	LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
	s->data = e;
	s->next = S->top;                    //把当前的栈顶元素赋值给新结点的直接后继
	S->top = s;                          //将新结点s当作栈顶指针
	S->count++;
	return 1;
}

2.出栈操作

//若栈不空，则删除S的栈顶元素，用e返回其值，并返回1，否则返回0
int Pop(LinkStack *S, int *e)
{
	LinkStackPtr p;
	if(StackEmpty(*S))
		return 0;

	*e = S->top->data;
	p = S->top;                          //将栈顶结点赋值给p
	S->top = S->top->next;               //栈顶指针下移一位，指向后一结点
	free(p);                             //释放结点p
	S->count--;

	return 1;
}

       如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。