链表、队列和堆栈都是数据结构的一种。 根据Sartaj Sahni的《数据结构、算法与应用》书中的描述,“数据结构是数据对象与构成对象的实例和实例的数据元素之间存在的各种联系。 这些联系可以通过定义相关的函数给出。 ”他将数据对象(数据对象)定义为“一个数据对象是实例或值的集合”。
一.链表
1.定义
3358www.Sina.com/(linkedlist )是一般的基础数据结构,虽然是线性表,但是不是以线性的顺序存储数据,而是在各节点)上存储数据变量(data )和指针变量(node next )
链表
)1) .使用链表结构,可以克服数组链表需要提前知道数据大小的缺点,链表结构可以充分利用计算机的内存空间,实现灵活的内存动态管理。
)2) .对数据的访问往往按不同的顺序进行转换,但链接列表为自指示数据类型。 这是因为它包含指向同一类型的其他数据的指针(链接)。 链表允许插入和删除表中任意位置的节点,但不允许随机访问。
2. 优点
链表失去了随机读取数组的优点,链表增加了节点的指针字段,从而增加了空间开销。
3. 缺点
主要有单向链表、双向链表及循环链表。
4. 类型
(1) .单向链表
(2) .双向链表
5. 实例
使用链表不需要知道数据的大小,但数组必须在创建时指定数组的大小。
链表没有相应的下标,只有指向下一个数据的指针,数组中每个数组都有相应的下标。
链表存储在内存中的数据可以是不连续的,但数组存储的数据占用内存中的连续段,并由标识符标识。
2 .队列
6. 与数组(Array)的对比
队列是一种特殊的线性表,只有表的前端前端才允许执行删除操作,而表的后端rear允许执行插入操作。 进行插入操作的端称为排队终端,进行删除操作的端称为排队终端。 如果队列中没有元素,则称为空队列。
在名为队列的数据结构中,最初插入的元素首先被删除。 相反,队列也称为FIFO—first in first out线性表,因为最后插入的元素最后会被删除。
1. 定义
33558www.Sina.com/(EE )将指定的元素插入此队列,如果可以立即完成并且不违反容量限制,则在成功时返回true
如果之前没有可用空间,则抛出IllegalStateException。 回到布尔。
2. 队列的方法()获取不删除此队列的标头,如果此队列为空,则抛出NoSuchElementException并返回通用e。
33558www.Sina.com/(e )如果将指定的元素插入此队列,并且可以立即执行而不违反容量限制,则为、
通常,该方法优于add(e )。 add )无法插入元素,可能会抛出异常。 回到布尔。
add()获取不删除此队列的标头,如果此队列为空,则返回null。 返回通用e。
element)获取并删除此队列的开头。 如果此队列为空,则返回null。 返回通用e。
offer()获取并删除此队列的开头。 返回通用e。
peek
队列可以用数组Q[1…m]保存,数组的上限为m,最大容量为m。 队列运算需要设置两个指针。 队列头指针(head ),指向实际队列头元素的前面位置; 队列指针(tail )指向实际的队列末端元素所位于的位置,并位于队列中
拥有的元素个数为:N=tail-head。一般情况下,两个指针的初值设为0,这时队列为空,没有元素。若数组定义Q[1…10],head=2,tail=8。如果要让排头的元素出队,则需将头指针加1。即head=head+1这时头指针向上移动一个位置,指向Q(3),表示Q(3)已出队。如果想让一个新元素入队,则需尾指针向上移动一个位置。即tail=tail+1这时Q(9)入队。当队尾已经处理在最上面时,即tail=10,如果还要执行入队操作,则要发生"上溢",但实际上队列中还有三个空位置,所以这种溢出称为"假溢出"。
4. 循环队列的概念
为充分利用向量空间,克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。
循环队列的入队算法:
(1). tail=tail+1;
(2). 若tail=m+1,则tail=1;
(3). 若head=tail尾指针与头指针重合了,判断空或满;
(4). 否则,Q[tail]=X,结束(X为新入出元素)。
循环队列的出队算法:
(1). 若head=tail尾指针与头指针重合了,判断空或满;
(2). 若不重合head=head+1;
(3). 若head=m+1,则head=1;
(4). 移除Q[head],结束。
循环队列中,由于入队时尾指针向前追赶头指针;出队时头指针向前追赶尾指针,造成队空和队满时头尾指针均相等。因此,无法通过条件front==rear来判别队列是"空"还是"满"。
解决这个问题的方法至少有两种:
① 另设一布尔变量以区别队列的空和满;
② 另一种方式就是数据结构常用的:队满时:(tail+1)%n=head,n为队列长度(所用数组大小),由于tail,head均为所用空间的指针,循环只是逻辑上的循环,所以需要求余运算。如图情况,队已满,但是tail+1=5+1=6,n=6,求余6%6=0=head。
5. 阻塞队列(BlockingQueue)的概念
三. 栈
1. 定义
栈(Stack),是硬件。主要作用表现为一种数据结构,是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。
栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为退栈(POP)。栈也称为先进后出表。
2. 栈的方法
empty() 测试堆栈是否为空。返回boolean。
peek() 查看堆栈顶部的对象,但不从堆栈中移除它。返回泛型E。
pop() 移除堆栈顶部的对象,并作为此函数的值返回该对象。返回泛型E。
push(E item) 把项压入堆栈顶部。返回泛型E。
search(Object o) 返回对象在堆栈中的位置,以 1 为基数。返回int。
3. 栈的实现
1、进栈(PUSH)算法
①若TOP≥n时,则给出溢出信息,作出错处理(进栈前首先检查栈是否
已满,满则溢出;不满则作②);
②置TOP=TOP+1(栈指针加1,指向进栈地址);
③S(TOP)=X,结束(X为新进栈的元素);
2、退栈(POP)算法
①若TOP≤0,则给出下溢信息,作出错处理(退栈前先检查是否已为空栈,
空则下溢;不空则作②);
②X=S(TOP),(退栈后的元素赋给X):
③TOP=TOP-1,结束(栈指针减1,指向栈顶)。