什么是堆？什么是栈啊？

Question

如题所述

Answer 1

堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。

向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

扩展资料：

一、堆的算法思想

不必将值一个个地插入堆中，通过交换形成堆。假设根的左、右子树都已是堆，并且根的元素名为R。这种情况下，有两种可能：

（1） R的值小于或等于其两个子女，此时堆已完成。

（2） R的值大于其某一个或全部两个子女的值，此时R应与两个子女中值较小的一个交换，结果得到一个堆，除非R仍然大于其新子女的一个或全部的两个。这种情况下，我们只需简单地继续这种将R“拉下来”的过程，直至到达某一个层使它小于它的子女，或者它成了叶结点。

二、栈的基本算法

1、进栈（PUSH）算法

①若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）。

②置TOP=TOP+1（栈指针加1，指向进栈地址）。

③S(TOP)=X，结束（X为新进栈的元素）。

2、退栈（POP）算法

①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)。

②X=S(TOP)，（退栈后的元素赋给X）。

③TOP=TOP-1，结束（栈指针减1，指向栈顶）。

参考资料来源：百度百科-堆

参考资料来源：百度百科-栈

Answer 2

什么是堆和栈？
一个由c/C++编译的程序占用的内存分为以下几个部分
1、栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
2、堆区（heap） — 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表，呵呵。
3、全局区（静态区）（static）—，全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 - 程序结束后有系统释放
4、文字常量区 —常量字符串就是放在这里的。 程序结束后由系统释放
5、程序代码区—存放函数体的二进制代码。

函数压栈是怎么回事？
函数压栈的本质是参数传递
这又跟汇编语言连系起来了.汇编语言的过程即proc可以理解成函数
比如一个最简单的计算两数之和函数
如果用汇编来写估计是这样的

sub proc
pop ax ;从stack取a 并放在AX寄存器中
pop bx ;从stack取b 并放在BX寄存器中
add ax,bx ; 计算a+b
ret //返回
sub endp

显然要调用这个函数,你应当先把b值push进stack,然后再push a
因为stack是先进后出的
所以调用汇编像这样
比如计算4+5
push 5;
push 4;
call sub; //返回值在AX中
在这个例子中先压5或先压4得到的结果没有变化
但大多数程序,如果参数的顺序错误将是灾难性的

因为不管什么高级语言最终都要编译成汇编语言,然后是机器语言
同样下面这个C程序,计算a+b值,必然会编译成上面的汇编代码
int sub(int a ,int b) {return a+b;}
所以C在调用这个函数sub时,必须要压栈(即传入参数)但这些工作,在C语言里,并不需要你来完成.你只要写出
sub(7,9);
编译器在编译成汇编时就会自动完成相关的压栈工作.

根据函数调用方式和参数压入顺序目前存在三种约定:

stdcall
cdecl
fastcall
这都相关压栈顺序和栈的清理工作约定
他们的细节都不相同,但有一点是肯定的,参数比须从右向左压入栈中
stdcall中 函数必须自已清理栈
cdecall 由调用者清除堆栈 C的默认函数调用方式 所以这样C支持可变参数
fastcall 是把函数参数列表的前三个参数放入寄存器eax,edx,ecx,其他参数压栈

源代码:
int function(int a, int b)
{
return a + b;
}

void main()
{
function(10, 20);
}

1.__cdecl

_function
push ebp
mov ebp, esp
mov eax, [ebp+8] ;参数1
add eax, [ebp+C] ;加上参数2
pop ebp
retn
_main
push ebp
mov ebp, esp
push 14h ;参数 2入栈
push 0Ah ;参数 1入栈
call _function ;调用函数
add esp, 8 ;修正栈
xor eax, eax
pop ebp
retn

2.__fastcall

@function@8
push ebp
mov ebp, esp ;保存栈指针
sub esp, 8 ;多了两个局部变量
mov [ebp-8], edx ;保存参数 2
mov [ebp-4], ecx ;保存参数 1
mov eax, [ebp-4] ;参数 1
add eax, [ebp-8] ;加上参数 2
mov esp, ebp ;修正栈
pop ebp
retn
_main
push ebp
mov ebp, esp
mov edx, 14h ;参数 2给EDX
mov ecx, 0Ah ;参数 1给ECX
call @function@8 ;调用函数
xor eax, eax
pop ebp
retn

3.__stdcall

_function@8
push ebp
mov ebp, esp
mov eax, [ebp] ;参数 1
add eax, [ebp+C] ;加上参数 2
pop ebp
retn 8 ;修复栈
_main
push ebp
mov ebp, esp
push 14h ;参数 2入栈
push 0Ah ;参数 1入栈
call _function@8 ;函数调用
xor eax, eax
pop ebp
retn

Answer 3

堆栈解析大全

抽象篇：

内存的地址从0开始到最大
堆就是内存地址从最大向0的方向递减
栈就是内存地址从0向最大的方向递增

通俗篇：

栈是指只能从一边存入和取出数据
队是指一边存入另一边取出

实战篇：

堆（heap）是系统中可供程序自由动态分配的内存空间，c中用malloc来从堆中取得一块内存，用free释放。
栈（stack）是一种数据结构，先进先出。可以在程序中自己建立，还有函数栈，是系统调用函数时临时分配的内存空间，用来保留一些必要的数据，函数运行后释放。

理论篇：

堆栈都是一种数据项按序排列的数据结构，只能在一端(称为栈顶(top))对数据项进行插入和删除。要点：堆：顺序随意，先进后出可以，先出后行也行。栈：后进先出(Last-In/First-Out)

缩水篇：

new操作的内存在堆空间；而int a;类似的变量的内存在栈空间。

推荐篇：

http://www.diybl.com/course/3_program/c++/cppsl/20081117/151367.html

Answer 4

堆（heap）是系统中可供程序自由动态分配的内存空间，c中用malloc来从堆中取得一块内存，用free释放。

栈（stack）是一种数据结构，先进先出。可以在程序中自己建立，还有函数栈，是系统调用函数时临时分配的内存空间，用来保留一些必要的数据，函数运行后释放。

Answer 5

堆栈都是一种数据项按序排列的数据结构，只能在一端(称为栈顶(top))对数据项进行插入和删除。要点：堆：顺序随意，先进后出可以，先出后行也行。栈：后进先出(Last-In/First-Out)