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

一、 顺序栈

顺序栈是指利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设有指针top指示栈顶元素在顺序栈中的位置；另设指针base指示栈底元素在顺序栈中的位置。当top和base的值相等时，表示空栈。

1.1、顺序栈的存储实现

#define MAXSIZE 100
typedef struct
{
	SElemType *base;//栈底指针
	SElemType *top;//栈顶指针
	int stacksize;//栈可用的最大容量
}SqStack;

1.2、顺序栈的初始化

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.3、顺序栈的入栈

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.4、顺序栈的出栈

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.5、取顺序栈的栈顶元素

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

二、链栈

链栈是指采用链式存储结构实现的栈，通常链栈用单链表表示。
没有特殊要去，顺序栈比链栈更实用。

2.1、链栈的存储结构

typedef struct StackNode
{
	ElemType data;
	struct StackNode *next;
}StackNode,*LinkStack;

2.2、链栈的初始化

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

2.3、链栈的入栈
和顺序栈入栈操作不同的是，链栈在入栈前不需要判断栈是否满，只需要为入栈元素动态分配一个节点空间。

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

2.4、链栈的出栈
和顺序栈一样，链栈在出栈前也需要判空，不同的是，链栈在出栈后需要释放出栈元素的栈顶空间。

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;
} 

2.5、取链栈的栈顶元素
与顺序栈一样，当栈非空时，此操作返回当前栈顶元素的值，栈顶指针S保持不变。

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

三、顺序栈和链栈的区别

顺序栈：是静态分配的，最大空间容量受到限制。
链栈：是静态分配的，不需要考虑空间不够。

最后

以上就是无聊黄蜂为你收集整理的顺序栈与链栈的实现与区别的全部内容，希望文章能够帮你解决顺序栈与链栈的实现与区别所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。