一、Stack
 堆栈（Stack）代表了一个后进先出的对象集合。当您需要对各项进行后进先出的访问时，则使用堆栈。当您在列表中添加一项，称为推入元素，当您从列表中移除一项时，称为弹出元素。
 
Stack 类的方法和属性
 Stack 类的一些常用的 属性：
 
属性
描述
Count
获取 Stack 中包含的元素个数。
Stack 类的一些常用的 方法：
 
方法
描述
public virtual void Clear();
从 Stack 中移除所有的元素。
public virtual bool Contains( object obj );
判断某个元素是否在 Stack 中。
public virtual object Peek();
返回在 Stack 的顶部的对象，但不移除它。
public virtual object Pop();
移除并返回在 Stack 的顶部的对象。
public virtual void Push( object obj );
向 Stack 的顶部添加一个对象。
public virtual object[] ToArray();
复制 Stack 到一个新的数组中。
实例
 
using System;
using System.Collections;

namespace CollectionsApplication
{
    class Program
    {
        static void Main(string[] args)
        {
            Stack st = new Stack();

            st.Push('A');
            st.Push('M');
            st.Push('G');
            st.Push('W');
           
            Console.WriteLine("Current stack: ");
            foreach (char c in st)
            {
                Console.Write(c + " ");
            }
            Console.WriteLine();
           
            st.Push('V');
            st.Push('H');
            Console.WriteLine("The next poppable value in stack: {0}",
            st.Peek());
            Console.WriteLine("Current stack: ");          
            foreach (char c in st)
            {
               Console.Write(c + " ");
            }
            Console.WriteLine();

            Console.WriteLine("Removing values :{0}", st.Pop());
            Console.WriteLine("Removing values :{0}", st.Pop());
            Console.WriteLine("Removing values :{0}", st.Pop());
           
            Console.WriteLine("Current stack: ");
            foreach (char c in st)
            {
               Console.Write(c + " ");
            }
        }
    }
}
 
结果
 
Current stack: 
W G M A
The next poppable value in stack: H
Current stack: 
H V W G M A
Removing values :H
Removing values :V
Removing values :W
Current stack: 
G M A
 
二、ConcurrentStack
 
由于Stack是线程不安全的集合，在进行多线程多任务操作集合时会出现数据丢失等问题。通常的解决方法是添加lock锁。lock 确保当一个线程位于代码的临界区时，另一个线程不进入临界区。如果其他线程试图进入锁定的代码，则它将一直等待（即被阻止），直到该对象被释放。但锁的引入，带来了一定的开销和性能的损耗，并降低了程序的扩展性，而且还会有死锁的可能。
 
在.NET Framework 4提供了新的线程安全和扩展的并发集合，它们能够解决潜在的死锁问题和竞争条件问题，因此在很多复杂的情形下它们能够使得并行代码更容易编写，这些集合尽可能减少使用锁的次数，从而使得在大部分情形下能够优化为最佳性能，不会产生不必要的同步开销。（需要注意：在串行代码中不要使用并发集合，会增加不必要的开销）
 
Stack对应的线程安全的并发集合就是 ConcurrentStack，命名空间：System.Collections.Concurrent。
 ConcurrentStack类的常用方法：
 
方法
描述
public void Push(Object obj)
向 ConcurrentStack的顶部添加一个对象。
public bool TryPop()
移除并返回在 ConcurrentStack的顶部的对象。
关于ConcurrentStack是如何实现线程安全的，可参考文章C# ConcurrentStack实现

 

  [cpp] 
  view plain
   copy
  

  
 

#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <windows.h>  
  
int ShowEsp(int* arg1,int* arg2);  
  
/* 
引言 各种面试宝典上都会说 又说栈在进程空间的高地址部分,向下扩展;  
堆在进程空间的低地址部分,堆向上扩展 
来验证一下是否正如所说这些变量在内存中如何分布? 
*/  
int main()  
{  
  
    //0)  
    int i=0xABCDABCD;  
    //int* j = (int*)malloc(sizeof(int)); //malloc为什么被我注掉了?  
    //memcpy(j,&i,sizeof(int));  
    int* k = (int*)VirtualAlloc(NULL,sizeof(int),MEM_COMMIT,PAGE_READWRITE);  
    int* ptr = NULL;  
    ptr = (int*)&i;  
    //ptr = j;   
    /* 
    malloc 是crt运行库实现 系统为crt库在进程靠近2G的高地址处保留大块堆内存 用链表管理  
    调用malloc时，单独从此处抽取分配给调用者 
    */  
    ptr = k;  
  
    //1) 忽略malloc这另类 看看实际系统定义诺干栈变量后，查看他们在内存中的分布  
    int arg1=0x40302010;  
    int arg2=0x20;  
    int* ptr1=NULL;  
    int* ptr2=NULL;  
    char str[] = {"1234567"};  
    printf("arg1:%x\narg2:%x\n",&arg1,&arg2);  
    printf("ptr1:%x\nptr2:%x\n",&ptr1,&ptr2);  
    printf("str:%x\n",str);  
    //结论:变量的地址是连续并且向下扩展  
    //编译器通过sub esp,immd来开辟栈空间  
    //再来看下变量地址存放的内容 arg1  
    char* arg1Ptr = (char*)&arg1;  
    printf("arg1Ptr[0]:%02x\narg1Ptr[1]:%02x\narg1Ptr[2]:%02x\narg1Ptr[3]:%02x\n",*arg1Ptr,*(arg1Ptr+1),*(arg1Ptr+2),*(arg1Ptr+3));  
    //程序没问题吧，感觉在用arg1Ptr取arg1各个字节的内容，看下arg1在内存中的分布  
    //.........................................................................  
    //intel cpu小端机 (题外话 网络编程时 ip/port转换即为大小端字节转换) 数据在内存中按高高低低分布 高字节 在高位 低字节在低位  
  
    //2) 知道了变量在内存中的分布 再看下如何存取变量，alt-8  
    //  
    arg1 = 0x80706050;  
    arg2 = arg1;  
    arg2 = 0x20;  
  
    //程序编译后 用[ebp-N]相对偏移取变量 why?   
    //intel CPU用esp指向当前函数栈顶，变量又保存在栈中，理所当然的可以用esp取变量。  
    //但是变量在不断扩充esp在不断减小 ------  
    //假设 现在要取arg1变量值 可能会编译成 mov eax,[esp+0x40]，意思是arg1离栈顶esp相差0x40个字节  
    //如果程序又新定义一个栈变量，栈顶向下移动，即esp=esp-4 此时 esp离arg1的距离为0x44   
    //如果再次取arg1的值 会编译成 mov eax,[esp+0x44] 这样编译起来太麻烦了    
    //a) intel CPU用ebp做当前函数帧[不是强制约定 习惯]，也就是栈底，某些面试宝典会写  
    //函数栈底不改变，说的就是ebp再当前函数中不改变。栈变量编译后内存位置固定下来，现在ebp又是固定不变的准绳  
    //这样无论程序怎样扩展栈变量，ebp到各个变量之间的距离都不会改变  
      
    //3) 面试宝典还说 c++参数入栈顺序是 从右往左压栈 全部入完后 压入函数返回地址  
    //既然 大家对堆栈达成共识才看到这了 再来看下调用函数,继续反汇编 观察堆栈变化  
    ShowEsp(&arg1,&arg2);  
    //a)入栈操作 (esp寄存器的变化) 用的是push 每次push后esp减4 压入返回地址后 jmp到ShowEsp  
    //程序jmp到ShowEsp 这里也跟到esp  
      
    //5) 堆栈平衡的收尾  
    /* 
    来看下函数返回后当前栈顶还剩啥 
    指令执行顺序-|esp变化------|保存ebp后变量相对于新栈帧ebp的距离------- 
    push &arg2   |1次esp=esp-4 | ebp+0x0C 
    push &arg1   |2次esp=esp-4 | ebp+0x08 
    */  
    /*函数参数已经显得不重要了可以忽略不计，再说main函数中依然可以通过[ebp-N]的形式访问这些变量 
    但是目前堆栈还没有恢复到函数调用前的样子 还倒欠main函数8个字节,于是编译器采用了一种简单粗暴 
    却有行之有效的办法 
    add esp,0x08 
    于是堆栈平衡 
    还有一个问题，函数范围值在哪?eax中 
    eax 4字节 不管返回什么都没问题 
    */  
    exit(0);  
}  
  
int ShowEsp(int* arg1,int* arg2)  
{  
    //进入到ShowEsp后 先是取形参，然后赋值给局部变量  
    //局部变量访问 已经不是这里的重点 此处重点看下如何取形参  
    int op1,op2,res;  
    //atl-8  
    op1 = *arg1;  
    op2 = *arg2;  
    /* 
    访问arg1 arg2 被翻译成mov eax,[ebp+8],[ebp+0x0c] 
    之前访问变量是用[ebp-N]的形式 现在怎么变成使用[ebp+N]的形式? 
    解释这个 还是得看反汇编的结果 
    反汇编的前几句如下 
    push ebp 
    mov ebp,esp 
    sub esp,4Ch 
    上面2-a)处写到过 intel CPU用ebp做当前函数帧，刚才指令流是在main函数中，因此ebp是基于main函数的 
    现在进入到ShowEsp函数中，要形成新的函数帧，因此先用push ebp把前一个函数的函数帧保存起来,然后 
    mov ebp,esp把当前的栈顶esp赋值给ebp形成新的函数帧 最后的sub esp,4Ch 为本函数创建栈空间 
     
    如果把之前main函数中的函数调用和参数入栈 以及此处生成新的函数帧一系列动作联合起来 并查看esp在此期间的 
    变化: 
    指令执行顺序-|esp变化------|保存ebp后变量相对于新栈帧ebp的距离------- 
    push &arg2   |1次esp=esp-4 | ebp+0x0C 
    push &arg1   |2次esp=esp-4 | ebp+0x08 
    call ShowEsp |3次esp=esp-4 | ebp+0x04 
    push ebp     |4次esp=esp-4 | ebp+0x00 
     
    这应该能解释函数取形参用mov eax,[ebp+0x08]等形式 
    */  
    res = op1+op2;  
  
    //4)堆栈平衡的下半段  
    /* 
    还是拿某宝典说事，说c++是_stdcall c是_cdcel call 
    区别是函数执行结束 一个由被调用的函数恢复堆栈 另一个是由调用者恢复堆栈 
    这代码是_cdcel call 由调用者恢复堆栈 
    来看下这函数怎么恢复堆栈 继续返回编 
    */  
    return res;  
    /* 
    程序结尾处看到 
    mov esp ebp 
    pop ebp 
    ret 8 
    还记得函数入口处的? 
    push ebp 
    mov ebp esp 
    都说是堆栈操作了，所有的操作要呼应对吧，执行了 
    mov esp ebp 
    pop ebp 
    这两句之后，函数堆栈恢复到发生调用ShowEsp的情景，虽然ShowEsp分配的栈变量还存在，但 
    已经处在esp指向的范围之外，换句话说，此时再新建栈变量，以前栈上的变量就会覆盖。当然 
    很少有人这么做。这也是有时候函数返回了，还能得到函数内部变量的原因。注意，所谓的宝典 
    会说，函数返回会自动清栈变量，反正c的代码，我没看到这种语句 
 
    最后的ret语句会使程序返回到函数调用的地方，这个地方由谁指定? 
    还记得3-a)处调用ShowEsp时，把下一条指令压入堆栈?就是那个时候指定函数返回地址,翻阅intel手册 
    说发生ret时，返回到当前栈顶指向的值 
 
    来看下当前栈顶还剩啥 
    指令执行顺序-|esp变化------|保存ebp后变量相对于新栈帧ebp的距离------- 
    push &arg2   |1次esp=esp-4 | ebp+0x0C 
    push &arg1   |2次esp=esp-4 | ebp+0x08 
    call ShowEsp |3次esp=esp-4 | ebp+0x04 
    栈顶还剩call ShowEsp时压入的返回地址，ret执行后 相当于pop eax, jmp eax 弹出一个栈值。 
    于是我们乘坐这个传送门返回到main函数中 
     
    [题外话]如果修改这个返回地址会得到意想不到的结果，这是后面要讲的缓冲区溢出 
    */  
}  
  
//文章结尾感谢同事yj同志 帮我做义务审校,并提出修改建议  

一般的由C/C++编译的程序占用的内存分为以下几个部分
 1、栈区（stack）。
 2、堆区（heap）。
 3、静态数据区（全局）。
 5、程序代码区。
 
那在多线程环境下的堆栈是如何分配的呢？
 
我们只需要记住以下两点：
 
1. 每个线程一个栈，每个进程一个堆。
 2. 请看典型的内存分布图。不同的段可能被加载器映射到相距很遥远的位置。
 
1.      变量在内存地址的分布为：堆-栈-代码区-全局静态-常量数据
 
2.      同一区域的各变量按声明的顺序在内存的中依次由低到高分配空间（只有未赋值的全局变量是个例外）。
 
3.      全局变量和静态变量如果不赋值，默认为0。 栈中的变量如果不赋值，则是一个随机的数据。
 
4.      编译器会认为全局变量和静态变量是等同的，已初始化的全局变量和静态变量分配在一起，未初始化的全局变量和静态变量分配在另一起。
 而且主函数中栈的地址都要高于子函数中参数及栈地址，证明了栈的伸展方向是由高地址向低地址扩展的。主函数和子函数中静态数据的地址也是相邻的，说明程序会将已初始化的全局变量和表态变量分配在一起，未初始化的全局变量和表态变量分配在另一起。
 
参考：https://blog.csdn.net/morewindows/article/details/6851681

第17节：什么是堆栈





在前面的课程中应该知道每一个程序都有一个4G的内存空间，如果不知道的话可以看前面的章节，那么是不是当前的这个程序的4G内存空间可以独立使用呢？答案：不是的。虽然说有4G内存，但是你真正要用到某一块内存空间的时候，你一定要向操作系统申请，换句话说你要告诉操作系统。我们管这个过程叫做内存申请，那不同的语言申请的形式也是不同的，但是本质上是相同的。那么至于怎么写后面会讲到，你只要记住进程有一个4G内存，但应用程序想使用某一块内存，一定要申请，那么这个申请过程就是所提到的内存申请。





那堆栈有是怎么一回事呢？堆栈就好比一块内存，只不过是程序员申请的，它只有在你的程序启动执行的时候，操作系统会给你分配好的，所以堆栈和其他内存不同的地方。别的内存是程序员自己申请的，但堆栈是程序启动时分配的。堆栈是给程序执行的时候使用的，你的程序在执行过程中肯定要执行临时数据等等，这些信息存储在哪里呢？答案：是在堆栈中。（注意：这里提到的堆栈不要和数据结构的堆栈搞混淆）





任何程序在执行过程中使用到的数据都会在堆栈中体现出来，所以我们可以这样理解，堆栈可以做程序的心脏，无论你是做病毒和反病毒，或者是漏洞扫描，堆栈是我们必须理解的。对于正向的普通程序员，他们对堆栈并没有怎么关注，因为操作系统给他们分配好的，他们只管取使用就可以了，他们不管细节是什么样的。如果你是做安全或者底层开发的人你就会了解到堆栈。





举例：

1)打开olldebug工具

2)托入一个程序

3)看寄存器中的S位(FS位) 

4)32bit对应着是B2B000(FFF) 注意：这里你们可能跟我不一样因为程序不一样

5)B2B000这个值在指令窗口中输入dd B2B000

6)可以看到B2B000下的B2B004=009F000 的值加上4就是和B2B008=09E6000

7)这两个值就是操作系统为我们分配的内存空间（注意：在堆栈窗口中最后的值是009EFFFC 的值加上4就是009F000）

8)所以以上的例子就是我反复提到的堆栈









这块内存还有一个特征，都是从小到大的排列，这个排列顺序是从后往前的，如果当程序中的内存不够用的时候就会出错（也就是内存溢出），比如：写递归的时候写太大了就会出现内存溢出的情况。









1、ESP指令(称为：栈指针寄存器)

什么叫栈指针寄存器，就是我们讲的当你程序可以用，那么程序用到那里了，需要记录的这个地址称为栈指针寄存器，记录地址存在ESP内。





举例：

1)存储1和2的值

2)mov dword ptr ds:[0x18FFFC8],1

3)mov dword ptr ds:[0x18FFFC4],2

4)SUB ESP,8

5)看堆栈的值变化

6)看ESP寄存器的变化









2、PUSH指令

功能

1)向堆栈中存入数据

2)修改栈顶指针ESP寄存器的值

也就是前面说的ESP指令的例子，只是这里是简写形式





3、POP指令

POP指令是将数据拿出来存到一个地方，esp再加4

举例：

mov eax，10

mov ecx，dword ptr ds:[esp]

add esp,4





简写是：

pop eax