数据结构 — 队列和堆栈
2020-03-06 本文已影响0人
leap_
队列 Queue
队列是一种FIFO的线性数据结构，front指针指向对头（第一个元素），rear指针指向队尾（最后一个元素的下一个空白的位置）
假溢出：
环形队列：
队列元素的判断：
- 队列为空：front == rear
- 队列为满： (rear+1)%N == front
- 队列元素个数：(rear-front + N)%N
优先级队列 ：
队列里的元素都有一个优先级，优先级高的先出队列
- MessageQueue
- PriorityQueue
栈 Stack
一种FILO的线性数据结构，只能在一段进行操作
应用：
- 计算机计算，后缀表达式
- activity活动栈
- JVM内存模型的栈区（方法调用），帧栈（计算）
堆 Heap
堆通常可以看做一个完全二叉树
应用：
- JVM堆，存放对象内存
栈解决了程序运行问题，堆解决了数据存储问题
- Stack与heap都运行在内存上，在内存空间上字节码指令不必担心不同机器上的区别，所以JVM实现了与平台无关的特性。
- JVM栈的每个栈帧（slot）大小都是4bytes，而一个slot恰好可以保持一个对象引用，所以引用永远是4bytes
