【数据结构】回顾栈ADT和队ADT

2015/09/08 21:51
阅读数 116

1.简单的说,栈就是只在一个位置上进行插入和删除操作的表,而这个特殊的位置就是表的末端,但这却不被成为栈的末端,而是顶(Top)。

2.栈的基本操作时进栈和出栈,英文名分别是push和pop,分别相当于插入和删除。切记对空栈进行pop和top操作在栈ADT被认为是错误的,而如果push在空间之外进行操作也是有实现限制的,但这并不是ADT错误。

3.栈的特点是后进先出,对于学生来说可能用食堂里堆砌起来的餐盘做形容更加合适。

4.栈既可以用单向链表来实现,也可以用数组来实现。用单向链表自然是比较简单的,但用数组来实现的话,由于可以用vector的back、push_back 和 pop _back,因此也算是比较简单的。而且用数组的话,每个栈就会有一个theArray和topOfStack,对于空栈这topOfStack为-1,如果要添加一个元素x,则topOfStack加1,并且theArray[topOfStack]=x。如果要删除一个元素x,那么pop函数的返回值就是theArray[topOfStack],还要记得将topOfStack减1。

5.以上的操作都运行得飞快,而且如果是有自增和自减寻址功能的寄存器,那么对整数的push和pop操作都可以写成一条机器指令哦。

6.所存储的信息被称为活动记录,或称为栈帧。

7.关于递归,有兴趣的话可以看看这一篇,极有可能会扩充你的知识面。

传送门:【Scheme归纳】3 比较do, let, loop

8.队列和栈类似,基本上有2个操作:入队(enqueue),在表的末端(队尾)插入一个元素;出队(dequeue),删除并返回表的头部(队头)的元素。



感谢您的访问,希望对您有所帮助。

欢迎大家关注或收藏、评论或点赞。


为使本文得到斧正和提问,转载请注明出处:
http://blog.csdn.net/nomasp


版权声明:本文为 NoMasp柯于旺 原创文章,未经许可严禁转载!欢迎访问我的博客:http://blog.csdn.net/nomasp

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部