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

2023-08-04 18:22| 来源: 网络整理| 查看: 265

一、顺序栈

顺序栈是指利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设有指针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;//返回栈顶元素的值，栈顶指针不变 } 三、顺序栈和链栈的区别

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

【本文地址】

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

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

今日新闻

推荐新闻