上海中学门户网站,菠菜网站搭建怎么做,合肥公司建站模板,成都网站开发等项目外包公司栈的基本概念
1. 栈的定义#xff1a;只允许在一端进行插入或删除操作的线性表#xff08;可以理解为操作受限的线性表#xff09;。
2. 栈的特点#xff1a;后进先出#xff08;LIFO#xff09;。
3. 栈的基本操作#xff1a;初始化、销毁、进栈、出栈、读栈顶元素等…栈的基本概念
1. 栈的定义只允许在一端进行插入或删除操作的线性表可以理解为操作受限的线性表。
2. 栈的特点后进先出LIFO。
3. 栈的基本操作初始化、销毁、进栈、出栈、读栈顶元素等。
InitStack(S)初始化栈。构造一个空栈 S分配内存空间。
DestroyStack(S)销毁栈。销毁并释放栈 S 所占用的内存空间。
Push(S,x)进栈若栈S未满则将x加入使之成为新栈顶。
Pop(S,x)出栈若栈S非空则弹出栈顶元素并用x返回。
GetTop(S, x)读栈顶元素。若栈 S 非空则用 x 返回栈顶元素
StackEmpty(S)判断一个栈 S 是否为空。若S为空则返回true否则返回false。 栈的常考题型进栈顺序与出栈顺序的关系。 n个不同的元素进栈出栈元素不同排列的个数为 栈的顺序存储实现顺序栈
顺序存储给各个数据元素分配连续的存储空间大小为MaxSize*sizeof(ElemType)。
顺序栈的定义
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{ElemType data[MaxSize]; //静态链表中存放栈中元素int top; //指向栈顶元素
} SqStack;
我们通过top的值指向栈顶元素即top的范围数组索引值[0,n-1]。因此如果栈是空栈就令top-1。
顺序栈的初始化与判断栈空
void InitStack(SqStack S){S.top-1; //初始化栈顶指针
}
bool StackEmpty(SqStack S){if(S.top-1)return true;elsereturn false;
}
新元素入栈
bool PushStack(SqStack S,ElemType x){if(S.topMaxSize-1) //判断是否满栈return false;S.data[S.top]x;return true;
}
由于S.top是索引指向当前的栈顶位置因此S.data[S.top]x而不是S.data[S.top]x。对于后者我们可以采取另一种方式——让top指向下一个可以插入的位置这时需要将top初始化为0判断栈满的条件也变成了topMaxSize。
出栈
bool PopStack(SqStack S,ElemType x){if(S.top-1) //栈空报错return false;xS.data[S.top--];return true;
}
读取栈顶元素
bool GetTop(SqStack S,ElemType x){if(S.top-1)return false;xS.data[S.top]; //记录栈顶元素引用返回return true;
}
顺序栈的缺点栈的大小不可变。
共享栈
共享栈两个栈共享同一片存储空间这片存储空间不单独属于任何一个栈某个栈需要的多一点它就可能得到更多的存储空间两个栈的栈底在这片存储空间的两端当元素入栈时两个栈的栈顶指针相向而行。
栈满的条件top01top1(top是int类型是数组的索引值) #define MaxSize 10
typedef struct{ElemType data[MaxSize];int top0; //0号栈栈顶指针int top1; //1号栈栈顶指针
} ShStack;
void InitStack(ShStack S){S.top0-1;S.top1MaxSize;
}
链栈
1. 栈的链式存储实现通过单链表模拟进栈采用头插法。
2. 出栈操作对应单链表的删除操作需对头结点进行“后删”处理。
3. 链栈定义及初始化带头结点的链栈便于操作。
#includestdlib.h
#includestdio.h#define MAXSIZE 10typedef int ElemType;typedef struct Linknode {ElemType data;struct Linknode*next;
}*LiStack;带头结点的链栈 //初始化
void InitLiStack(LiStack s){s(Linknode*)malloc(sizeof(Linknode));if(sNULL){printf(内存分配失败!\n);return ;}s-nextNULL;printf(空间申请成功!\n);
} //销毁
void DestryLiStack(LiStack s){Linknode* ps-next;while(p!NULL){Linknode* rp;p-nextr-next;free(r);}free(s);printf(销毁成功!\n);
} //入栈
void PushLiStack(LiStack s,ElemType e){Linknode* r(Linknode*)malloc(sizeof(Linknode));r-datae;r-nexts-next;s-nextr;printf(插入节点成功!\n);
} //出栈
void PopLiStack(LiStack s,ElemType e){if(s-nextNULL){printf(栈空!\n);return;}Linknode* ps-next;ep-data;s-nextp-next;free(p);printf(出栈成功!\n);
} //获取栈顶节点
Linknode* GetElem(LiStack s,ElemType e){if(s-nextNULL){printf(栈空!\n);return NULL;}Linknode* ps-next;ep-data;
}
不带头结点的链栈 //初始化
void InitLiStack(LiStack s){sNULL;printf(申请空间成功!\n);
} //销毁
void DestryLiStack(LiStacks){Linknode* ps;while(p-next!NULL){Linknode* rp;pr-next;free(r);}//最后一个节点特殊处理free(p); printf(销毁成功!\n);
} //入栈
void PushLiStack(LiStack s,ElemType e){//如果开始没有节点特殊处理 if(sNULL){Linknode* r(Linknode*)malloc(sizeof(Linknode));r-datae;r-nextNULL;sr;printf(插入节点成功!\n); return ; } Linknode* r(Linknode*)malloc(sizeof(Linknode));//首先将头结点的值修改为要插入的值e将r-datas-data,最后直接在头结点后面插入节点r即可 r-datas-data;s-datae;r-nexts-next;s-nextr;printf(插入节点成功!\n);
} //出栈
void PopLiStack(LiStack s,ElemType e){if(sNULL){printf(栈空!\n);return;}//只有一个节点的时候特殊处理 if(s-nextNULL){es-data; free(s);return ;} Linknode* ps;ep-data;s-nextp-next;free(p);printf(出栈成功!\n);
} //获取栈顶节点
Linknode* GetElem(LiStack s,ElemType e){if(sNULL){printf(栈空!\n);return NULL;}Linknode* ps;ep-data;
}
