栈 |
您所在的位置：网站首页 › 堆栈的top › 栈 |
栈
|
文章目录
栈的定义栈的存储栈上的基本操作初始化判空操作进栈操作出栈操作读栈顶元素遍历栈销毁栈
完整代码及实例共享栈
栈的定义
栈（Stack）是只允许在一端进行插入或删除操作的线性表。 栈的示意图： 假设某个栈S={a1,a2, … ,an}，如上图所示，则a1为栈底元素，an为栈顶元素。由于只能在栈顶进行插入和删除操作，故进栈顺序为a1,a2, … ,an，出栈顺序为an, … ,a2,a1。故栈的操作特性是后进先出LIFO（Last In First Out），称为后进先出的线性表。 空栈：不含任何元素的空表。 栈的存储栈的存储方式有两种：顺序栈和链栈，即栈的顺序存储和链式存储。 采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的元素，同时附设一个指针（top）指示当前栈顶的位置。 栈的顺序存储类型描述： #define MaxSize 100 //定义栈中元素的最大个数 typedef struct SqStack{ int data[MaxSize]; //存放栈中的元素 int top; //栈顶指针 }SqStack;采用链式存储的栈称为链栈，链栈便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并且所有操作都是在单链表的表头进行的。在本文中主要是介绍了顺序栈下的一些基本操作，关于链栈的实现与单链表类似，可以参考单链表的定义及其基本操作。 栈的链式存储类型描述： typedef struct LinkNode{ int data; //数据域 struct LinkNode *next; //指针域 }*LiStack; //栈类型定义 栈上的基本操作栈的基本操作包括： 初始化InitStack(&S);判空Empty(S);进栈Push(&S, x);出栈Pop(&S, &x);读栈顶元素GetTop(S);遍历栈PrintStack(&S);销毁栈DestroyStack(&S);[注]以上操作均采用顺序栈来实现。 初始化初始时设置S.top = -1。 //初始化 void InitStack(SqStack &S){ S.top = -1; } 判空操作栈空条件：S.top == -1; 栈满条件：S.top ==MaxSize-1。 //判栈空 bool Empty(SqStack S){ if(S.top == -1){ return true; }else{ return false; } } 进栈操作由于初始设置S.top=-1，故栈顶指针先加一，再入栈。
|
【本文地址】