数据结构栈和队列常见问题（学习数据结构--第三章）

数据结构栈和队列常见问题（学习数据结构--第三章）判满： tpp1-top0==1判空：顺序栈：采用顺序存储的栈#define MaxSize 50typedef struct{ ElemType date[MaxSize]; int top; //数组的下标}SqStack;3.1判断栈空&满&长度栈空条件：S.top==-1 ，在栈里面没有内容的时候top代表数组的下标此时值为-1；栈的长度：S.top 1 ，top代表数据下标，所以栈的长度等于数组下标 1；栈满条件：S.top==MaxSize-1，如果栈的top下标为数组长度-1说明栈满了。void InitStack(SqStack &S){ S.top == -1;}3.2.2判断栈空boll StackEmpty(SqStack &S){ if(S.top == -1){ return true; }else{

第三章：栈和队列

1.栈的基本概念

栈(Stack) 只允许在 一端 (这一端叫做栈顶) 进行插入或者删除操作的 线性表

在栈中先进入栈的元素会后出栈即：先进后出 (LIFO)

2.栈的基本操作

InitStack(&s) 初始化一个空栈SStackEmpty(S) 判断一个栈是否为空 若栈为空则返回true 否则返回 falsePush(&S x) 进栈 若栈S未满 则将加入使之成为新栈顶。Pop(&S &x) 出栈 若栈非空 则弹出栈顶元素 并用x返回。Gettop(S &x) 读栈顶元素，若栈非空则用x返回栈顶元素。ClearStack(&S) 销毁栈，并释放S占用的内存空间。

这里发现：Pop 和 GetTop 这两个函数都可以返回栈顶元素，不同的是Pop 会移除栈顶元素，而 GetTop只会获取栈顶元素的值，而不会出栈。

3.栈的顺序存储结构

顺序栈：采用顺序存储的栈

#define MaxSize 50typedef struct{ ElemType date[MaxSize]; int top; //数组的下标}SqStack;

3.1判断栈空&满&长度

栈空条件：S.top==-1 ，在栈里面没有内容的时候top代表数组的下标此时值为-1；栈的长度：S.top 1 ，top代表数据下标，所以栈的长度等于数组下标 1；栈满条件：S.top==MaxSize-1，如果栈的top下标为数组长度-1说明栈满了。

3.2 栈的基本操作

3.2.1初始化

void InitStack(SqStack &S){ S.top == -1;}

3.2.2判断栈空

boll StackEmpty(SqStack &S){ if(S.top == -1){ return true; }else{ return false; }}

3.2.3进栈

boll Push(SqStack &S ElemType x){ if(S.top == MaxSize-1){ //栈满 return fase; } S.data[ S.top] = x; return true;}

3.2.4出栈

boll Pop(SqStack &S ElemType &x){ if(S.top == -1){ //栈空 return fase; } x = S.data[S.top--]; return true;}

3.2.5获取栈顶元素

boll GetTop(SqStack S ElemType &x){ if(S.top == -1){ //栈空 return fase; } x = S.data[S.top] //只需读取，不需移动下标 return true; }

3.3.共享栈

共享栈：将两个栈底设置在共享空间的两端，栈顶向空间中间延伸；

判空：

• 0号栈 top==-1
• 1号栈 top==MaxSize

判满： tpp1-top0==1

共享栈的优点：存取时间复杂度仍为O(1)，且空间利用更加有效。

4.栈的链式存储结构

链栈 采用链式存储的栈

这里不需要头节点，这里规定了第一个结点为栈顶结点所以：所有的操作都要在表头进行。

4.1链栈基本操作

因为相当于是单链表，所以链栈的判空，出栈，栈的长度和单链表的操作基本相同。

关于数据结构的知识，持续更新中，欢迎关注公众号理木客