C++ 栈和队列的实现超详细解析

可算是把链表给结束了很多小伙伴已经迫不及待想看到栈和队列了那么它来了相信有了顺序表和链表的基础栈和队列对于你们来讲也是轻轻松松那我就废话不多说直接进入今天的重点1、栈的介绍栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。出栈栈的删除操作叫做出栈。出数据也在栈顶。栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上 插入数据的代价比较小。本次我们是用动态数组来实现栈静态栈在实际中一般不实用2、栈的常用接口实现 首先是我们动态栈的结构有了顺序表和链表的基础我就直接上代码了12345678typedefintSTDataType;typedefstructStack{STDataType* a;inttop;intcapacity;}ST; 栈的初始化⛳ 入栈操作 出栈操作出栈就很简单了我们直接使top--就可以了因为我们插入数据是先在top位置插入然后再top这样我们下次插入数据就会覆盖pos位置的数据注意当栈没有初始化没有数据的情况下不能进行出栈操作123456voidStackPop(ST* ps){assert(ps);assert(ps-top 0);ps-top--;} 取栈顶元素操作我们知道top是栈顶元素的后一个所以我们直接取top-1下标位置的数据就可以123456STDataType StackTop(ST* ps){assert(ps);assert(ps-top 0);returnps-a[ps-top - 1];} 求栈的节点个数12345intStackSize(ST* ps){assert(ps);returnps-top;} 判断栈是否为空我们使用返回值为bool型的函数bool类型只会返回true或false见下代码12345boolStackEmpty(ST* ps){assert(ps);returnps-top 0;} 销毁栈操作记得养成释放动态内存的习惯哦1234567voidStackDestroy(ST* ps){assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;}栈相对来说还是比较简单了栈的基本接口就到这里了下面我们来实现队列的基本接口操作3、队列的介绍队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out) 入队列进行插入操作的一端称为队尾出队列进行删除操作的一 端称为队头