堆栈
JVM中的堆栈
入栈出栈。
假设序列为abcdefg等，
- 如果abc 出栈。a，b，c没有入，或a入a出，b入b出，c入c出。此时defg同上。
- bc出栈，则a依然入，位于栈底。a出栈时，栈为空。即不可能在此后出现a之后的元素。
例子：
123456789
987651234是不可能的。只有1234，1位于首位才行。
所以，判断依据。第一个元素要么位于首位，其后元素才能在其后出栈。 - 最后一个元素第一个出栈，则意味着之前元素都在站内。
- 某个原始位于第一个出栈，则其之前元素都在站内，则输出时，只会反序出现在之后。
牛客网：
-
两个顺序栈共享数组S【0…n-1】，其中第一个栈的栈顶指针top1的初始值为-1，第二个栈的栈顶指针top2的初始值为n，则判断该共享栈满的条件是（ ）
就是两个栈共用一个数组。满的一种情况：top1=-1，top2=0。所以top1+1=top2。 -
若已知一个栈的入栈序列是 1,2,3,„,n,其输出序列为 p1,p2,p3,„,pn,若 p1=n,则pi 为（）
推论4 。 p1=n pi=pn+1-i。 合为n+1 -
采用顺序存储的栈，执行入栈运算，栈顶指针的变化是（）
进来一个，指针后移 -
若栈采用链式存储结构, 链表不需要判满，只需要判定是否为空即可
-
输入序列为ABC,可以变为CBA时,经过的栈操作为()
push 入，pop出 -
假设栈初始为空，将中缀表达式
image
转换为等价后缀表达式的过程中，当扫描到f时，栈中的元素依次是 （）
-
下列关于堆和栈的区别描述错误的有？
下面都是正确的。
栈的大小是固定的，堆的大小受限于系统中有效的虚拟内存
栈的空间由系统决定何时释放，堆需要自己决定何时去释放
堆的使用容易产生碎片，但是用起来最方便 -
下列数据结构具有记忆功能的是
栈
将一个递归算法改为对应的非递归算法时 -
递归工作栈里面包括返回地址、本层的局部变量和递归调用的形参代换用实参，所以正常情况下，无论递归过程有没有使用局部变量，转换为非递归过程都需要用栈来模拟这个递归调用过程
当然，有一些特殊递归不用栈就可以直接转换，比如尾递归、常系数递推等，无论是否有局部变量 -
X、Y、Z 一共有6中出来结果，只有 zxy是不可能的。
-
以下与数据的存储结构无关的术语是
存储结构是数据的逻辑结构用计算机语言的实现，
常见的存储结构有： 顺序存储 ， 链式存储 ， 索引存储 ，以及 散列存储 。
其中散列所形成的存储结构叫 散列表（又叫哈希表） ，因此哈希表也是一种存储结构。
栈只是一种抽象数据类型，是一种逻辑结构，栈逻辑结构对应的顺序存储结构为顺序栈，对应的链式存储结构为链栈，
循环队列是顺序存储结构，链表是线性表的链式存储结构。
1.vector 底层数据结构为数组 ，支持快速随机访问
2.list 底层数据结构为双向链表，支持快速增删
3.deque 底层数据结构为一个中央控制器和多个缓冲区.支持首尾（中间不能）快速增删，也支持随机访问
4.stack 底层一般用23实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时
5.queue 底层一般用23实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时
- 45是适配器,而不叫容器，因为是对容器的再封装
7.priorityQueue 的底层数据结构一般为vector为底层容器，堆heap为处理规则来管理底层容器实现
8.set 底层数据结构为红黑树，有序，不重复
9.multiSet 底层数据结构为红黑树，有序，可重复
10.map 底层数据结构为红黑树，有序，不重复
11.multiMap 底层数据结构为红黑树，有序，可重复
12.hashSet 底层数据结构为hash表，无序，不重复
13.hashMultiSet 底层数据结构为hash表，无序，可重复
14.hashMap 底层数据结构为hash表，无序，不重复
15.hashMultiMap 底层数据结构为hash表，无序，可重复
递归式的先序遍历一个n节点，深度为d的二叉树，需要栈空间的大小为
o（d）
前缀后缀表达式转换。
递归转非递归。
链表和hash表
树和图
深度优先搜索要借助栈；
广度优先搜索要借助队列；
解析：几种常见的数据结构的操作性能对比如下图所示
image
由上图可见，平衡二叉树的查找，插入和删除性能都是O(logN)，其中查找和删除性能较好；哈希表的查找、插入和删除性能都是O(1)，都是最好的。
网友评论