顺序栈与链栈的实现与区别

1
2
3
4
5
6
7
8
#define MAXSIZE 100
typedef struct
{
	SElemType *base;//栈底指针
	SElemType *top;//栈顶指针
	int stacksize;//栈可用的最大容量
}SqStack;

1
2
3
4
5
6
7
8
9
Status InitStack(SqStack &S)
{//构造一个空栈S
	S.base = new SElemType[MAXSIZE];//为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
	if(!S.base) exit(OVERFLOW);//存储分配失败
	S.top = S.base;//top初始为base，空栈
	S.stacksize = MAXSIZE;//stacksize置为栈的最大容量MZXSIZE
	return OK;
}

1
2
3
4
5
6
7
8
9
Status Push(SqStack &S,SElemType e)
{//插入元素e为新的栈顶元素
	if(S.top - S.base ==S.stacksize)
		return ERROR;//栈慢
	*S.top = e;
	S.top++;//元素e压入栈顶，栈顶指针加1
	return OK;
}

1
2
3
4
5
6
7
8
9
Status Pop(SqStack &S,SElemType &e)
{//删除S的栈顶元素，用e返回其值
	if(S.top == S.base)
		return ERROR;//栈空
	S.top--;
	e=*S.top;//栈顶指针减1，将栈顶元素赋给e
	return OK;
}

1
2
3
4
5
6
SElemType GetTop(SqStack S)
{//返回栈顶元素，不修改栈顶指针
	if(S.top != S.base)//栈非空
		return *(S.top-1)//返回栈顶元素的值，栈顶指针不变
}

1
2
3
4
5
6
typedef struct StackNode
{
	ElemType data;
	struct StackNode *next;
}StackNode,*LinkStack;

1
2
3
4
5
6
Ststus InitStack(LinkStack &S)
{//构造一个空栈S，栈顶指针置空
	S=NULL:
	return OK:
}

1
2
3
4
5
6
7
8
9
Status Push(LinkStack &S,SElemType e)
{// 在栈顶插入元素e
	p=new StackNode;//生成新节点
	p->data = e;//将新节点数据域置为e
	p->next = S;//将新节点插入栈顶
	S = p;//修改栈顶指针p
	return OK;
}

1
2
3
4
5
6
7
8
9
10
11
Status Pop(LinkStack &S,SElemType &e)
{//删除S的栈顶元素，用e返回其值 
	if(S==NULL)
		return ERROR;//栈空 
	e = S->data;//将栈顶元素赋给e 
	p=S;//用p临时保存栈顶元素空间，以备释放 
	S=S->next;//修改栈顶指针 
	delete p;//释放原栈顶元素的空间 
	return OK;
} 

1
2
3
4
5
6
SElemType GetTop(LinkStack S)
{//返回S的栈顶元素，不修改栈顶指针 
	if(S!=NULL)//栈非空 
		return S->data;//返回栈顶元素的值，栈顶指针不变 
}