larger[index]=stack[index];
stack=larger;
}
第4章链式结构——栈
1.对象引用变量可以用来创建链式结构。
链式结构是一种数据结构，它使用对象引用变量来创建对象之间链接。
链式结构是基于数组的集合实现的主要替代方案。
2.对象引用变量存放的是对象的地址，表示该对象在内存中的存储位置。
我们通常并不是显示地址，而是把引用变量描绘成一种“指向”对象的名字，这种引用变量又称为指针。
3.链表由一些对象构成，是一种链式结构，其中的一个对象可以指向另一个对象，从而在链表中创建一个对象的线性次序。
链表中存储的对象通常泛称为该链表的结点。
4.需要一个单独的引用变量来表示链表的首结点。
链表终止于其next引用为空的结点。
5.链表只是链式结构的一种。
如果建立的类含有多个指向对象的引用，就可以创建更复杂的链式结构。
链接的管理方式表明了这种链式结构的特定组织形式。
6.链表会按需动态增长，因此在本质上，它没有容量限制（在不考虑计算机本身的内存限制下）。
7.链表的大小可以按需伸缩以容纳要存储的元素数量，因此链表被认定为是一种动态结构。
在java语言中，所有动态创建的对象都来自于一个名为系统堆或自由存储的内存区。
8.对于链表来说，访问链表的元素的唯一方式是，从第一个元素开始，顺着该链表往下进行。
9.结点可以被插入到链表的任意位置。
在链表前端架结点时，需重新设置指向整个链表的引用：
a）新添加结点的next引用被设置为指向链表的当前首结点；
b）指向链表前端的引用重新设置为指向这个新结点。
如果颠倒顺序，即先重新设置front引用，那么就失去了那个唯一指向现有链表的引用，于是再也检索不到该链表了。
10.改变引用顺序是维护链表的关键。
11.链表的任一结点都可被删除。
要删除链表的首结点，需要重置指向链表前端的引用，使其指向链表当前的次。
如果其他地方需要这个被删除的结点，那么在重制front引用之前，必须创建一个指向被删除结点的单独引用。
12.链表的一个关键特征：
必须把链表结构的细节内容与链表所储存的元素区分开来
13.存储在集合中的对象不应该含有基本数据结构的任何实现细节。
14.节点类含有两个引用：
一个引用指向链表的下一结点，另一个引用指向将存储到链表中的那个元素。
这时，链表中所存储的实际元素是使用结点对象中单独引用来访问的。
15.双向链表中，需维护两个引用：
一个指向链表的首结点，一个指向链表的末结点。
链表中的每个结点都存有两个引用：
一个指向下一元素，一个指向上一元素。
16.哨兵结点或哑结点：
位于链表前端或末端的结点，起标记符作用，不表示链表中的某个元素。
如果要在双向链表中使用哑结点，那么就得在链表的两端都放置哑结点。
17.递归使用了程序栈的概念，程序栈又称运行时栈，用于跟踪被调用的方法。
每调用一个方法时，就会创建一个表示该调用的调用记录，并压入到程序栈中。
因此，栈中的元素表示的是在一个正在运行程序中，到达某个位置时所调用的方法系列。
18.程序运行出现异常时，可检查调用跟踪栈，来发现问题出自于哪个方法。
19.可以使用栈来模拟递归处理，以便跟踪恰当的数据。
20.用链表实现栈：
a）Push：
publicvoidpush（Telement）{
LinearNodetemp=newLinearNode（element）;
temp.setNext（top）;
top=temp;
count++;
}
b）Pop：
publicTpop（）throwsEmptyCollectionException{
if（isEmpty（））
thrownewEmptyCollectionException（"stack"）;
Tresult=top.getElement（）;
top=top.getNext（）;
count--;
returnresult;
}
第5章队列
1.队列是一种线性集合，其元素从一端加入，另一端删除。
因此，队列元素是按先进先出（FIFO）方式处理的。
从队列中删除元素的次序，与往队列中放置元素的次序是一样的。
元素都是从队列末端（rear）进入，从队列前端（front）退出。
2.用链表实现栈：
a）队列和栈的主要区别在于，队列中我们必须要操作链表的两端。
因此需要两个引用分别指向链表的首、末元素。
b）对于单向链表，可选择从末端入列，从前端出列。
c）双向链表可以解决需要遍历链表的问题，因此在双向链表实现中，无所谓在哪端入列和出列。
d）对于一个空队列，head和tail引用都为null，count为0。
队列中只有一个元素时，head和tail引用都会指向这个对象。
e）Enqueue：
将新元素放到链表末端
publicvoidenqueue（Telement）{
LinearNodenode=newLinearNode（element）;
if（isEmpty（））
head=node;
else
tail.setNext（node）;
tail=node;
count++;
}
f）Dequeue
publicTdequeue（）throwsEmptyCollectionException{
if（isEmpty（））
thrownewEmptyCollectionException（"queue"）;
Tresult=head.getElement（）;
head=head.getNext（）;
count--;
if（isEmpty（））
tail=null;
returnresult;
}
3.用数组实现队列：
a）由于队列操作会修改集合的两端，因此将一端固定于索引0出要求移动元素。
b）非环形数组实现的元素位移，将产生O（n）的复杂度。
c）把数组看作是环形的，可以除去在队列的数组实现中元素的移位需要。
d）环形数组：
如果数组的最后一个索引后面跟的是第一个索引，那么该数组就可用作环形数组。
e）用两个整数值表示队列的前端和末端。
front的值表示的是队列的首元素存储的位置，rear的值表示的是数组下一个可用单元（不是最后一个元素储存的位置），此时rear的值不在表示队列元素的数目了。
f）Enqueue：
publicvoidenqueue（Telement）{
if（size（）==queue.length）
expendCapacity（）;
queue[rear]=element;
rear=（rear+1）%queue.length;
count++;
}
注意：
环形增加
rear=（rear+1）%queue.length;
e）Dequeue:
publicTdequeue（）throwsEmptyCollectionException{
if（isEmpty（））
thrownewEmptyCollectionException（"queue"）;
Tresult=queue[front];
queue[rear]=null;
front=（front+1）%queue.length;
count--;
returnresult;
}
4.队列是一种可存储重复编码密钥的便利集合。
5.
队列的链表实现中，head和tail引用相等的情况：
a）队列为空：
head和tail都为null
b）队列中只有一个元素
6.队列的环形数组实现中，front和rear引用相等的情况：
a）队列为空
b）队列为满
7.dequeue操作复杂度为O（n）的非环形数组实现的时间复杂度最差
8.环形数组和非环形数组都会因未填充元素而浪费空间。
链表实现中的每个存储元素都会占用更多的空间。
第6章列表
1.链表和列表集合之间的差别：
a）链表是一种实现策略，使用引用来在对象之间创建链接，如前面用链表来实现了栈和队列集合。
b）列表集合是一种概念性表示法，其思想是使事物以线性列表的方式进行组织。
就像栈和队列一样，列表也可以使用链表或数组来实现。
2.列表集合没有内在的容量大小，它可以随着需要增大。
3.栈和队列都是线性结构，可以像列表那样进行思考，但元素只能在末端添加和删除。
列表集合更一般化，可以在列表的中间和末端添加和删除元素。
Inotherwords,栈和队列都属于列表，列表可任意操作。
4.列表可分为：
a）有序列表：
其元素按照元素的某种内在特性进行排序；
b）无序列表：
其元素间不具有内在顺序，元素按照它们在列表中的位置进行排序。
c）索引列表：
其元素可以用数字索引来引用。
5.有序列表是基于列表中元素的某种内在特征的。
列表基于某个关键值排序。
对于任何已添加到有序列表中的元素，只要给定了元素的关键值，同时已经定义了元素的所有关键值，那么它在列表中就会有一个固定的位置。
6.无序列表中各元素的位置并不基于元素的任何内在特性。
但列表中的元素是按照特殊顺序放置着，只不过这种顺序与元素本身无关。
列表的使用者会决定元素的顺序。
无序列表的新元素可以加到列表的前端、后端，或者插到某个特定元素之后。
7.索引列表与无序列表类似，各元素间也不存在能够决定它们在列表中的顺序的内在关系。
列表的使用者决定了元素的顺序。
除此之外，索引列表的每个元素都能够从一个数字索引值得到引用，该索引值从列表头开始从0连续增加直到列表末端。
索引列表的新元素可以加到列表的任一位置，包括列表的前端和后端。
每当列表发生改变，索引值就相应调整以保持顺序和连续性。
索引列表为它的元素维护一段连续的数字索引值。
8.索引列表和数组的根本区别在于：
索引列表的索引值总是连续的。
如果删除了一个元素，其他元素的位置会像“坍塌”了一样消除产生的空隙。
当插入一个元素时，其他元素的索引将进行位移以腾出位置。
9.列表有可能既是有序列表，又是索引列表，但这种设计没有什么意义。
10.Java集合API中的列表：
a）Java集合API提供的列表类只要是支持索引列表。
在一定程度上，这些类与无序列表是重叠的。
i.注意：
javaAPI并没有任何类能直接实现以上描述的有序列表。
b）List接口：
add（Eelement）
往列表的末端添加一个元素
add（intindex,Eelement）
在指定索引处插入一个元素
get（intindex）
返回指定索引处的元素
remove（intindex）
删除指定索引处的元素
remove（EObject）
删除制定对象的第一个出现
set（intindex，Eelement）
替代指定索引处的元素
size（）
返回列表中的元素数目
11.数组实现列表：
使用环形数组方法，但当从列表中间插入或者删除元素时，仍需移动元素。
a）Remove操作：
publicTremove（Telement）throwsElementNotFoundException{
Tresult;
intindex=find（element）;
if（index==NOT_FOUND）
thrownewElementNotFoundException（"ArrayList"）;
result=list[index];
rear--;
for（intscan=index;scanlist[scan]=list[scan+1];
list[rear]=null;
returnresult;
}
注意：
程序中的for循环，当循环结束后，scan等于rear。
因为当scan==rear-1时，最后运行一次list[scan]=list[scan+1],然后scan++，不满足scan复杂度为O（n）。
b）find方法：
privateintfind（Ttarget）{
intscan=0;
intresult=NOT_FOUND;
if（!
isEmpty（））
while（result==NOT_FOUND&&scanif（target.equals（list[scan]））
result=scan;
else
scan++;
}
returnresult;
}
注意：
find方法依靠equals方法来判断目标元素是否已找到。
c）contains操作
publicbooleancontains（Ttarget）{
return（find（target）!
=NOT_FOUND）;
}
如果没有找到目标元素，contains方法将返回false。
如果找到了，返回true。
由于该方法执行的是列表的线性查找，因此最坏的情况是所查找的元素不在列表中。
在这种情况下需要n个比较操作。
因此该方法平均需要n/2次比较操作，因而其复杂度为O（n）。
d）有序列表的add操作：
publicvoidadd（Telement）{
if（size（）==list.length）
expandCapacity（）;
Comparabletemp=（Comparable）element;
intscan=0;
while（scan0）
scan++;
for（intscan2=rear;scan2>scan;scan2--）
list[scan2]=list[scan2-1];
list[scan]=element;
rear++;
}
注意：
复杂度为O（n）。
只有Comparable对象才能存储在有序列表中。
e）Comparable接口定义了comp
升级会员 