首页 > 代码库 > 07.栈(一)栈的存储结构及操作
07.栈(一)栈的存储结构及操作
一、栈
1.栈(stack):是限定仅在表尾进行插入和删除操作的线性表。其中,允许插入和删除的一端被称为栈顶(top),另一端被称为栈底(bottom),不含任何数据元素的栈被称为空栈。栈又被称为后进先出(Last In First Out)的线性表,简称LIFO结构。
栈的插入操作为进栈,栈的删除操作为出栈。
2.栈的抽象数据类型
ADT 栈(stack)
Data
同线性表。元素具有相同类型,相邻元素具有前驱和后继关系。
Operation
InitStack(*S):初始化操作,建立一个空栈S。
DestoryStack(*S):若栈存在,则销毁它。
ClearStack(*S):将栈清空。
StackEmpty(S):若栈为空,返回true,否则返回false。
GetTop(S,*e):若栈存在且非空,用e返回S的栈顶元素。
Push(*S,e):若栈S存在,插入新元素e到栈S中并称为栈顶元素
Pop(*S,*e):删除栈S中栈顶元素,并用e返回其值
StackLength(S):返回栈S的元素个数
endADT
1.栈的顺序存储结构及实现(复杂度均为O(1))(3)出栈操作(从栈顶删除一个元素)(4)两栈共享空间
(1)栈顺序结构定义
#define OK 1
#define ERROR 0
typedef int SElemType; //SElemType类型根据实际情况而定,这里假设为int
typedef struct
{
SElemType data[MAXSIZE]; //栈存储空间大小MAXSIZE
int top; //用于栈顶指针
}SqStack;
(2)进栈操作(从栈顶插入一个元素)
算法思路:
a.判定是否栈满;
b.栈顶加1;
c.将元素插入到
实现:插入元素e为新的栈顶元素
Status Push(SqStack *S,SElemType e) { if(S->top==MAXSIZE-1) //栈顶=MAXSIZE-1,即数组的最后一个存储位置,说明栈满 { return ERROR; } S->top++; //栈顶加1 S->data[S->top]=e; //将元素入栈 return OK; }
算法思路:
a.判定栈是否为空;
b.将栈顶元素保存到指针变量e所指向的存储位置中;
c.栈顶减1.
实现:若栈不为空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
Status Pop(SqStack *S,SElemType *e) { if(S->top==-1) //空栈 { return ERROR; } *e=S->data[S->top]; S->top--; return OK; }
栈的顺序存储只准栈顶进出元素,所以不存在线性表插入和删除时需要移动大量的元素,但是有个缺陷是必须事先确定数组存储空间大小。当两个栈数据类型一样是,我们可以将两个栈所开辟的空间共享使用。
A.思想:将栈1的栈底,即为共享空间的栈底(下标为0);另一个栈的栈底为共享栈的末端(下标为数组长度n-1处),其中top1和top2是栈1和栈2的栈顶指针。对于共享栈,若栈2是空栈(top2=n),栈1的top1=n-1,说明栈1满了;若栈1是空栈(top=-1),栈2的top2=0,说明栈2满了。即共享栈满条件:top1+1==top2。
B.共享栈空间结构
typedef struct
{
SElemType data[MAXSIZE]; //定义一个数组存储空间,大小为MAXSIZE即为栈大小
int top1; //栈1栈顶指针
int top2; //栈2栈顶指针
}SqDoubleStack;
C.共享栈元素入栈操作
算法思路:
a.首先判断共享栈是否栈满;
b.通过stackNumber参数判断插入哪个栈
若为栈1,则栈顶top1增1,再将元素e入栈;若为栈2,则栈顶top2减1,在将元素e入栈。
实现:插入元素e为新的栈顶元素
Status Push(SqDoubleStack *S,SElemType e,int stackNumber) { if(S->top1+1==S->top2) //判定共享栈是否栈满(top1+1=top2) { return ERROR; } if(stackNumber==1) //栈1有元素进栈,栈顶top1加1 S->data[++S->top1]=e; else if(stackNumber==2) S->data[--S->top2]=e; //栈2有元素进栈,栈顶top2减1 return OK; }
D.共享栈元素出栈操作
算法思想:
a.判断哪一个栈;
b.若为栈1,则先将元素赋值给指针变量e指向的空间位置,再栈顶top1减1;
若为栈2,则先将元素赋值给指针变量e指向的空间位置,再栈顶top2增1;
实现:若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber) { if(stackNumber==1) //若删除元素属于栈1 { if(S->top1==-1) //空栈 return ERROR; *e=S->data[S->top1--]; //将元素赋值给e,栈顶再减1 } else if(stackNumber==2)//若删除元素属于栈1 { if(S->top2==MAXSIZE) //空栈 return ERROR; *e=S->data[S->top2++]; //将元素赋值给e,栈顶再减1 } return OK; }
升华笔记1:
1.栈的顺序存储结构是通过数组来实现的,下标为0为栈底,因为首元素都哦存在栈底变化最小。当栈存在一个元素时,栈顶top为0,如果为空栈则top=-1,这也是判断栈是否为空栈的条件。另外,要区别存储栈的长度StackSize(MAXSIZE)和存储位置。
2.两栈共享空间只适用于元素数据类型相同的两个栈,且入栈是先修改栈顶再元素入栈;出栈是先元素出栈再修改栈顶。2.栈的链式存储结构及实现
(1)链栈的结构
//链结点:包含数据域和指针域
typedef struct StackNode
{
SElemType data; //数据域
struct StackNode *next; //指针域
}StackNode,*LinkStackPtr;
//链栈结构
typedef struct LinkStack
{
LinkStackPtr top; //链栈头结点
int count; //结点个数
}LinkStack;
(2)链栈的进栈操作算法思想:
a.先为新结点s开辟一段空间,空间的大小为结点结构大小;
b.将要插入的元素值e赋值给新结点s的数据域;
c.将原来的栈顶元素赋值给新结点s的后继
d.使栈顶指针指向新结点e
e.链栈元素增1
实现:插入元素e为新的栈顶元素
Status Push(LinkStack *S,SElemType e) { LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode)); //开辟一个新的结点空间,大小为结构体StackNode大小 s->data=http://www.mamicode.com/e; //将元素e赋值给新结点s的数据域>
算法思想:
a.首先判定链栈是否为空栈
b.将栈顶指针指向元素数据域数据赋值给e
c.将栈顶指针原先指向的元素赋值给p
d.再将栈顶指针指向后一个结点,释放p
e.链栈元素数目减1
实现:若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK
Status Pop(LinkStack *S,SElemType *e) { LinkStackPtr p; if(StackEmty(*S)) //若空栈 return ERROR; *e=S->top->data; //将栈顶元素数据赋值给指针变量e指向空间 p=S->top; //将栈顶指针指向的结点(栈顶元素)赋值给p S->top=S->top->next; //使得栈顶指针下移一位,即此时栈顶指针指向后一个结点 free(p); //释放结点p S->count; //链栈元素数目减1 return OK; }
3.性能分析
(1)时间复杂度:栈的顺序结构和链式结构均为O(1);
(2)空间复杂度
栈的顺序结构只有数据域,空间复杂度小,但事先需要确定一个固定的长度,可能会存在内存空间浪费问题;
栈的链式存储结构每个元素具有数据域和指针域,空间复杂度稍复杂,同时也增加了一些内存开销,但对于栈的长度无限制。
(3)如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈;反之,如果它的变化在可控范围内,建议使用顺序栈性能会更高些。
07.栈(一)栈的存储结构及操作
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。