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

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），删除并返回表的头部（队头）的元素。

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