基本数据结构 之 堆栈、队列、堆

堆栈(stack,也叫栈)和队列是两种特殊的线性表。

堆栈的主要特点是只能在栈顶操作,也就是遵循先进后出的运算规则。

队列的主要特点是只能在一端插入、另一端删除,也就是遵循先进先出的运算规则。

%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-11-17-%e4%b8%8b%e5%8d%889-31-51

 

堆栈

栈的基本特点:

  1. 先入后出,后入先出。
  2. 除头尾节点之外,每个元素有一个前驱,一个后继。

 

堆叠数据结构使用两种基本操作:推入(push)和弹出(pop):

  • 推入:将数据放入堆叠的顶端(阵列形式或串列形式),堆叠顶端top指标加一。
  • 弹出:将顶端数据资料输出(回传),堆叠顶端资料减一。

 

堆栈可以用链表和数组两种方式实现,一般为一个堆栈预先分配一个大小固定且较合适的空间并非难事,所以较流行的做法是Stack结构下含一个数组。如果空间实在紧张,也可用链表实现,且去掉表头。

 

队列

与栈不同,它是一种FIFO(first in first out先进先出)结构
队列的实现
(1)数组
(2)链表
队列要记录的数据
(1)队首位置head:第一个元素位置
(2)队尾位置tail:下一个元素要插入的位置(最后一个元素的下一个位置)
(3)队列最大大小size
队列的操作
(1)ENQUEUE(x):入队
(2)DEQUEUE():出队
(3)EMPTY():队列为空,head=tail
(4)FULL():队列为满,head=(tail+1)%size

通常是一个可以被看做一棵树的数组对象。在队列中,调度程序反复提取队列中第一个作业并运行,因为实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,但具有重要性的作业,同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

堆的实现通过构造二叉堆(binary heap),实为二叉树的一种;由于其应用的普遍性,当不加限定时,均指该数据结构的这种实现。

这种数据结构具有以下性质

  • 任意节点小于(或大于)它的所有后裔,最小元(或最大元)在堆的根上(堆序性)。
  • 堆总是一棵完全树。即除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。

将根节点最大的堆叫做最大堆大根堆,根节点最小的堆叫做最小堆小根堆。常见的堆有二叉堆、斐波那契堆等。

应用

  • 堆(通常是二叉堆)常用于排序。这种算法称作堆排序。
  • 优先队列

heap

 

References:

《数据结构与算法分析–java语言描述》

http://www.jianshu.com/p/afbfc784238a

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注