集约化网站数据库建设规范,大学生做网站和做app,php电商网站开发流程,湖南广源建设工程有限公司网站目录
3.1栈
3.1.1栈的基本概念
【栈的特点#xff08;2017#xff09;】
【入栈序列和出栈序列之间的关系(2022)】
【特定条件下的出栈序列分析(2010、2011、2013、2018、2020)】
3.1.2栈的顺序存储结构
【出/入栈操作的模拟(2009)】 3.1栈
3.1.1栈的基本概念
【栈…目录
3.1栈
3.1.1栈的基本概念
【栈的特点2017】
【入栈序列和出栈序列之间的关系(2022)】
【特定条件下的出栈序列分析(2010、2011、2013、2018、2020)】
3.1.2栈的顺序存储结构
【出/入栈操作的模拟(2009)】 3.1栈
3.1.1栈的基本概念
【栈的特点2017】
栈(Stack)是只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表但限定这种线性表只能在某一端进行插入和删除操作。 栈顶(Top)。线性表允许进行插入删除的那一端栈底(Bottom)。固定的不允许进行插入和删除的另一端。空栈。不含任何元素的空表。 每接触一种新的数据结构都应从其逻辑结构、存储结构和运算三个方面着手。 【入栈序列和出栈序列之间的关系(2022)】
【特定条件下的出栈序列分析(2010、2011、2013、2018、2020)】
假设某个栈S(a1, a2, a3, a4,a5)如图 3.1 所示则 a1 为栈底元素a5为栈顶元素。
栈只能在栈顶进行插入和删除操作进栈次序依次为a1,a2,a3,a4,a5而出栈次序为 a5,a4,a3,a2,a1。
由此可见栈的操作特性可以明显地概括为后进先出(Last In First OutLIFO)。
3.1.2栈的顺序存储结构
【出/入栈操作的模拟(2009)】
栈操作的示意图如图 3.2 所示图 3.2(a)是空栈图 3.2(c)是A、B、C、D、E共5个元素依次入栈后的结果图 3.2(d)是在图 3.2(c)之后E、D、C的相继出栈此时栈中还有2个元素或许最近出栈的元素 C、D、E仍在原先的单元存储着但 top 指针已经指向了新的栈顶元素 C、D、E已不在栈中读者应通过该示意图深刻理解栈顶指针的作用。 下面是顺序栈上常用的基本操作实现
1初始化
void InitStack(SqStack S){S.top-1; //初始化栈顶指针
}2判栈空
bool StackEmpty(SqStack S){if(S.top-1) //栈空return true; else //不空return false;
}
3进栈
bool Push(SqStack S,ElemType x){if(S.topMaxSize-1) //栈满报错return false;S.data[S.top]x; //指针先加1再入栈return true;
}
4出栈
bool Pop(SqStack S,ElemType x){if(S.top-1) //栈空报错return false;xS.data[S.top--]; //先出栈指针再减1return true;
}5读取栈顶元素
bool GetTop(SqStack S,ElemType x){if(S.top-1) //栈空报错return false;xS.data[S.top];//x记录栈顶元素return true;
}仅为读取栈顶元素并没有出栈操作因此原栈顶元素依然保留在栈中。
注意 这里的 top 指的是栈顶元素。于是进栈操作为 S.data[S.top]x出栈操作为xS.data[S.top--]。若栈顶指针初始化为S.top0即 top 指向栈顶元素的下一位置则入栈操作变为S.data[S.top]x出栈操作变为xS.data[--S.top]。相应的栈空栈满条件也会发生变化。
