前言
经过前面对线性表的顺序存储结构和链式存储结构的熟悉,那么面对接下来栈的这两种存储结构也应该得心应手了。其实接下来的栈、队列、树、图结构都是基于线性表的顺序、链式存储结构构建的。
栈结构在网页跳转、游戏页面等场景中常用到,其“先进后出”“后进先出”的数据访问特点也使其在寻路问题中有一席之地。
1.认识栈
1.1栈
栈是一种特殊的线性表,只能在表的“端点”进行操作,即栈的插入、删除等操作只允许在线性表固定一端进行。
栈的几种状态:
进栈(入栈):把新的元素插入到顶端
出栈:获取顶端元素、并删除该元素
栈顶:允许插入、删除的一端称为栈顶(Top)
栈底:不能插入、删除的另一端称为栈底(Bottom)
空栈
像下图,按A、B、C、D依次压栈得出图中结果,出栈顺序是D、C、B、A。
如果我按ABCD顺序压栈,但是不考虑出栈时机,我能得出多少种结果呢?
ABCD(压A出A,压B出B……)
DCBA(压完ABCD,才执行出栈)
BACD(压完AB出BA,压C出C,压D出D)
BDCA(压AB,出B,压CD,出DCA)
CDBA(压ABC,出C压D,出BA)
…………共14种
1.2栈的操作
InitStack(&S) 初始化一个空栈
DestroyStack(&S) 销毁一个栈
ClearStack(&S) 清空一个栈
StackEmpty(S) 判断栈是否为空
StackLength(S) 获取栈的长度
GetTop(S, &e) 获得栈顶元素
Pop(&S, &e) 出栈
Push(&S, e) 入栈
…………
2.栈的顺序存储
2.1操作原理
利用一组地址连续的存储单元(一维数组),依次存放从栈底到栈顶的数据元素,(简称“顺序栈”)。此外,还需要定义一个(栈顶)标记,表示它前面是有效元素。
如果观察仔细的话,可以发现顺序栈的结构与线性表顺序存储结构无异,线性表的length属性可用作顺序栈的top以作为栈顶指针。
2.2代码
typedef int ElemType;
struct Stack{
ElemType *elem;
int length;//用长度作为栈顶指针
int volume;
};
//1.初始化栈
bool Init_Stack( Stack &S )
{
if(!S.elem) return false;
S.elem=new ElemType[size];
S.length=0;
S.volume=size;
return true;
}
//2.销毁栈
bool Destroy_Stack( Stack &S )
{
delete S.elem;
return true;
}
//3.清空栈
bool Clear_Stack( Stack &S )
{
S.length=0;
return true;
}
//4.判断栈是否为空
bool Stack_Empty( const Stack &S )
{
return S.length==0;
}
//5.求栈长
int Stack_Length( const Stack &S )
{
return S.length;
}
//6.取栈顶元素,返回栈顶元素
ElemType GetTop( const Stack &S )
{
if(S.length==0) return false;
return S.elem[S.length-1];
}
//7.入栈
bool Push( Stack &S, ElemType e)
{
if(S.length>=S.volume)
{
cout<<"栈满";
return false;
}
S.elem[S.length]=e;
++S.length;
return true;
}
//8.出栈
bool Pop( Stack &S, ElemType &e )
{
if(S.length==0) return false;
e=S.elem[S.length-1];
--S.length;
return true;
}
3.栈的链式存储
3.1操作原理
就是线性表的链式存储,只不过插入和删除都在头部进行(头插法和头删法)。
3.2代
typedef int ElemType;
struct Stack{
ElemType data;
Stack *next;
};
typedef Stack* myStack;
//1.初始栈
bool InitStack(myStack &S)
{
if(S)
{
cout<<"fail to init stack";
return false;
}
S=new Stack;
S->next=NULL;
return true;
}
//2.销毁栈
bool DestroyStack(myStack &S)
{
if(S->next!=NULL)
{
cout<<"请先执行清空表操作";
return false;
}
delete S;
return true;
}
//3.清空栈
bool ClearStack(myStack &S)
{
Stack *p=S->next;
Stack *del;
while(p)
{
del=p;
p=p->next;
delete del;
}
return true;
}
//4.判断栈是否为空
bool StackEmpty(const myStack &S)
{
if(S->next!=NULL)
return false;
cout<<"the stack is empty";
return true;
}
//5.获取栈的长度
int StackLength(const myStack &S)
{
int count=0;
Stack *p=S;
while(p->next)
{
p=p->next;
++count;
}
return count;
}
//6.获得栈顶元素
bool GetTop(const myStack &S, ElemType &e)
{
e=S->next->data;
return true;
}
//7.出栈
bool Pop(myStack &S, ElemType &e)
{
if(StackEmpty(S)==false)
{
e=S->next->data;
Stack *del=S->next;
S=S->next;
//S->next=S->next;这话其实是多余的
return true;
}
return false;
}
//8.入栈
bool Push(myStack &S, ElemType e)
{
Stack *p=new Stack;
p->data=e;
p->next=S->next;
S->next=p;
return true;
}
标签:存储,return,ElemType,next,length,bool,链式,数据结构,Stack
From: https://blog.csdn.net/QiQi_sviper/article/details/145310879