堆(heap) 栈(stack) (操作系统--数据结构)
操作系统堆栈区别?
堆栈空间分配
栈(操作系统):由操作系统自动分配释放 ,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。
堆(操作系统): 一般由程序员分配释放, 若程序员不释放,程序结束时可能由OS回收,分配方式倒是类似于链表。
堆栈缓存方式
栈使用的是一级缓存, 他们通常都是被调用时处于存储空间中,调用完毕立即释放。
堆则是存放在二级缓存中,生命周期由虚拟机的垃圾回收算法来决定(并不是一旦成为孤儿对象就能被回收)。所以调用这些对象的速度要相对来得低一些。
数据结构堆、栈、队列区别?
①堆是在程序运行时(no 编译),申请某个大小的内存空间。即动态分配内存,对其访问和对一般内存的访问没有区别。
②栈就是一个桶,后放进去的先拿出来,它下面本来有的东西要等它出来之后才能出来。(后进先出)
③队列只能在队头做删除操作,在队尾做插入操作.而栈只能在栈顶做插入和删除操作。(先进先出)
堆:堆可以被看成是一棵树,如:堆排序。 (1)总是一棵完全二叉树。 (2) 堆中某个节点的值总是不大于或不小于其父节点的值;(根节点最大叫大根堆,最小叫小根堆)
栈:一种运算受限(仅允许在一端进行插入和删除运算)的线性表。这一端为栈顶,相对为栈底。
队列:先进先出。
建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间,并设置两个指针进行管理。一个是队头指针front,它指向队头元素;另一个是队尾指针rear,它指向下一个入队元素的存储位置。
队列采用的FIFO(first in first out),新元素(等待进入队列的元素)总是被插入到链表的尾部,而读取的时候总是从链表的头部开始读取。每次读取一个元素,释放一个元素。所谓的动态创建,动态释放。因而也不存在溢出等问题。由于链表由结构体间接而成,遍历也方便。(先进先出)
内存分配中的堆和栈
在 C 语言中,内存分配方式不外乎有如下三种形式:
1、从静态存储区域分配:它是由编译器自动分配和释放的,即内存在程序编译的时候就已经分配好,这块内存在程序的整个运行期间都存在,直到整个程序运行结束时才被释放,如全局变量与 static 变量。
2、在栈上分配:它同样也是由编译器自动分配和释放的,即在执行函数时,函数内局部变量的存储单元都可以在栈上创建,函数执行结束时这些存储单元将被自动释放。需要注意的是,栈内存分配运算内置于处理器的指令集中,它的运行效率一般很高,但是分配的内存容量有限。
3、从堆上分配:也被称为动态内存分配,它是由程序员手动完成申请和释放的。即程序在运行的时候由程序员使用内存分配函数(如 malloc 函数)来申请任意多少的内存,使用完之后再由程序员自己负责使用内存释放函数(如 free 函数)来释放内存。也就是说,动态内存的整个生存期是由程序员自己决定的,使用非常灵活。需要注意的是,如果在堆上分配了内存空间,就必须及时释放它,否则将会导致运行的程序出现内存泄漏等错误。
ps:顺序栈AStack的类定义
template < class T >
class AStack {
private:
int size ; // 数组的规模
T * stackArray ; // 存放堆栈元素的数组
int top ; // 栈顶所在数组元素的下标
public:
AStack ( int MaxStackSize ) // 构造函数
{ size = MaxStackSize ; stackArray = new T [MaxStackSize] ; top = -1 ; }
~AStack ( ) { delete [ ] stackArray ; } // 析构函数
bool Push ( const T& item ) ; // 向栈顶压入一个元素
bool Pop ( T & item ) ; // 从栈顶弹出一个元素
bool Peek ( T & item ) const ; // 存取栈顶元素
int IsEmpty ( void ) const { return top = = -1 ; }
// 检测栈是否为空
int IsFull ( void ) const { return top size-1 ; }
// 检测栈是否为满
void clear ( void ) { top-1 ; } // 清空栈
} ;