在数据结构中间，堆(heap)和栈(stack)是两种的不同的数据结构，
堆和栈在保存数据的方式上不同，利用堆和栈，可以解决不同的实际问题.
一 栈
1 栈的特性
栈是线性结构，有先进后出的运算特性--Fisrt In last Out,简称FILO
栈只允许在表的一端进行插入和删除操作。这一端被称为栈顶(Top).
栈的另外一端不允许进行操作，这一端称为栈底(Bottom).
在栈顶插入数据，使数据成为新的栈顶元素，该操作称为进栈或者入栈，也可以称为压栈.
删除栈顶元素，之前的相邻元素成为新的栈顶元素，该操作称为出栈或者退栈。
数组栈
2 栈的实现
栈是线性结构，所以栈的底层实现可以是数组，也可以是链表。
数组实现的栈，元素地址是连续的，叫做顺序栈
链表实现的栈，元素地址是不连续的，叫做链式栈
二 堆
1 堆的特性
堆是树型结构，一般采用二叉树。
第一种堆：
当且仅当所有节点的值总是不大于其父节点的值的完全二叉树称为堆，所以这种堆，根节点是最大节点，这种堆称为大顶堆
第二种堆：
当且仅当所有节点的值总是不小于其父节点的值的完全二叉树称为堆，这种堆，根节点是最小节点，这种堆称为小顶堆
小顶堆:
2 堆的实现
堆的存储一般用数组
数组下标为i，那么它的父节点下表为(i-1)/2，它的左节点的下标为(i*2)+1,它的右节点的下表为(i*2)+2。
在堆中插入数据时，需要找准该元素在堆中间的位置。
0条评论
点击登录参与评论