链表、堆栈、队列的区别

《链表、堆栈、队列的区别》由会员分享，可在线阅读，更多相关《链表、堆栈、队列的区别（4页珍藏版）》请在金锄头文库上搜索。

1、数据结构知识：链表，队列和栈的区别 链表，队列和栈都是数据结构的一种。Sartaj Sahni在他的数据结构、算法与应用一书 中称：“数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种 联系。这些联系可以通过定义相关的函数来给出。”他将数据对象(data object)定义为“一 个数据对象是实例或值的集合”。一. 链表1. 定义链表(Linked list)是一种常见的基础数据结构，是一种线性表，但是并不会按线性的 顺序存储数据，而是在由一个个节点组成，每个节点(node)中储存着数据变量(data)和 指针变量(node next)，又有一个头节点(head)连接下面

2、的节点，而最后一个节点指向空 (null)”可以在链表类中定义增加，删除，插入，遍历，修改等方法，故常用来储存数据。2. 优点(1) .使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以 充分利用计算机内存空间，实现灵活的内存动态管理”(2) .数据的存取往往要在不同的排列顺序中转换，而链表是一种自我指示数据类型， 因为它包含指向另一个相同类型的数据的指针(链接)”链表允许插入和移除表上任意位置 上的节点，但是不允许随机存取”3. 缺点链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比 较大”4. 类型主要有单向链表，双向链表以及循环链表”5. 实例(

3、1) .单向链表2) .双向链表6.与数组(Array)的对比链表的使用不需要知道数据的大小，而数组在创建时必须指明数组的大小。 链表没有对应的下标，只有指向下一个数据的指针，而数组中每一个都有一个相对 应的下标。链表在内存中储存的数据可以是不连续的，而数组储存的数据占内存中连续的一段 用标识符标识。二. 队列1. 定义队列是一种特殊的线性表，它只允许在表的前端(front)进行删除操作，而在表的 后端(rear)进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队 列中没有元素时，称为空队列。在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的 元素将最后

4、被删除的元素，因此队列又称为“先进先出”(FIFOfirst in first out)的线性表。2. 队列的方法add(E e)将指定的元素插入此队列(如果立即可行且不会违反容量限制)，在成功时返回true，如果当前没有可用的空间，则抛出IllegalStateException。返回boolean。element()获取不移除此队列的头，如果此队列为空，则抛出 NoSuchElementException，返回泛型E。offer(E e)将指定的元素插入此队列(如果立即可行且不会违反容量限制)，当使用有容量限制的队列时，此方法通常要优于add(E)，后者可能无法插入元素，而只 是抛出一个异

5、常。返回 boolean。peek()获取不移除此队列的头，如果此队列为空，则返回null。返回泛型E。poll()获取并移除此队列的头，如果此队列为空，则返回null。返回泛型E。remove()获取并移除此队列的头。返回泛型E。3. 队列的使用和假溢出队列可以用数组Q1m来存储，数组的上界是m，最大容量是m。在队列的运算 中需设两个指针：队头指针(head)，指向实际队头元素的前一个位置；队尾指针(tail), 指向实际队尾元素所在的位置，队列中拥有的元素个数为：N=tail-head。一般情况下，两个指 针的初值设为0,这时队列为空，没有元素。若数组定义Q110, head=2，tail

6、=8。如果要让排头的元素出队，则需将头指针加 1。即head=head+1这时头指针向上移动一个位置，指向Q(3)，表示Q(3)已出队。如果想 让一个新元素入队，则需尾指针向上移动一个位置。即tail=tail+1这时Q（9）入队。当队尾已 经处理在最上面时，即tail=10，如果还要执行入队操作，则要发生上溢，但实际上队列中 还有三个空位置，所以这种溢出称为假溢出。4. 循环队列的概念 为充分利用向量空间，克服假溢出现象的方法是：将向量空间想象为一个首尾相 接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。循环队列的入队算法：（1） . tail

7、=tail+1；（2）.若 tail=m+1，则 tail=1；（3）. 若 head=tail 尾指针与头指针重合了，判断空或满；（4）.否则,Qtail=X,结束（X为新入出元素）。循环队列的出队算法：（1）. 若 head=tail 尾指针与头指针重合了，判断空或满；（2）. 若不重合 head=head+1；（3）.若 head=m+1，则 head=1；（4）.移除 Qhead，结束。循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针， 造成队空和队满时头尾指针均相等。因此，无法通过条件front=rear来判别队列是空还是 满。解决这个问题的方法至少有两种： 另

8、设一布尔变量以区别队列的空和满； 另一种方式就是数据结构常用的：队满时：（tail+1）%n=head, n为队列长度（所用 数组大小），由于 tail， head 均为所用空间的指针，循环只是逻辑上的循环，所以需要求余 运算。如图情况，队已满，但是tail+1=5+1=6, n=6，求余6%6=0=head。012345仆台headtail5.阻塞队列（BlockingQueue）的概念三. 栈1. 定义栈（Stack），是硬件。主要作用表现为一种数据结构，是只能在某一端插入和删除 的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在 栈顶，需要读数据的时候从栈顶

9、开始弹出数据（最后一个数据被第一个读出来）。栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端 称为栈顶（top），另一端为栈底（bottom）；栈底固定，而栈顶浮动；栈中元素个数为零时称为 空栈。插入一般称为进栈（PUSH）,删除则称为退栈（POP）。栈也称为先进后出表。2. 栈的方法empty（） 测试堆栈是否为空。返回 boolean。peek（）查看堆栈顶部的对象，但不从堆栈中移除它。返回泛型E。pop（）移除堆栈顶部的对象，并作为此函数的值返回该对象。返回泛型E。push（E item）把项压入堆栈顶部。返回泛型 E。search（Object o） 返回对象在堆栈中的位置，以 1 为基数。返回 int。ays 0-Att颇一拒底33. 栈的实现1、进栈（PUSH）算法 若TOP三n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作）； 置TOP=TOP+1 （栈指针加1,指向进栈地址）； S（TOP）=X，结束（X为新进栈的元素）；2、退栈（POP）算法 若TOPWO,则给出下溢信息，作出错处理（退栈前先检查是否已为空栈,空则下溢；不空则作）； X=S（TOP），（退栈后的元素赋给X）： TOP=TOP-1，结束（栈指针减1，指向栈顶）。