跳到主要内容

栈结构

概述​

总结​

栈是一种受限的数据结构，不同于可以在任意位置插入和删除数据的数组，栈是一种受限的线性表，后进先出。其限制是仅允许在表的一端进行插入和删除操作，这一端被称为栈顶，另一端称为栈底。LIFO（last in first out）表示就是后进入的元素，第一个弹出栈空间。向一个栈插入新元素又称为进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素。从一个栈删除元素又称作出栈或退栈，它把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

后进先出​

由于仅允许在表的一端进行插入和删除操作，这个操作就类似于叠盘子，只能在顶部，拿出或放上盘子。也就是我们仅能在栈顶进行操作。

实现栈结构​

栈常见的操作​

  1. push()：添加一个新元素到栈顶
  2. pop()：移除栈顶的元素，同时返回被移除的元素
  3. peek()：返回栈顶的元素，不对栈做任何修改
  4. isEmpty()：如果栈中没有任何元素就返回true，否则返回false
  5. size()：返回栈中的元素个数
  6. toString()：将栈结构的内容以字符形式返回

代码实例​

基于数组的栈:

// 封装栈类
function Stack() {
    this.items = []; // 栈的属性
    // 将元素压入栈
    Stack.prototype.push = function (element) {
        this.items.push(element);
    }
    // 从栈取出元素
    Stack.prototype.pop = function () {
        return this.items.pop();
    }
    // 查看栈顶元素
    Stack.prototype.peek = function () {
        return this.items[this.items.length - 1];
    }
    // 判断栈是否为空
    Stack.prototype.isEmpty = function () {
        return this.items.length == 0;
    }
    // 获取栈中元素的个数
    Stack.prototype.size = function () {
        return this.items.length;
    }
    // toString()
    Stack.prototype.toString = function () {
        // 按照元素+空格+元素将其转化为字符串
        let result = "";
        for (let i = 0; i < this.items.length; i++) {
            result += this.items[i] + " ";
        }
        return result;
    }
}

汇编角度看栈操作​

概述​

栈是一种最基本的数据结构，在函数调用时用来存储数据，其遵循先入后出原则，通常分为push（压栈）与pop（出栈）操作，在栈中有一个esp指针指向栈的顶部。但栈是由高地址位向低地址位存储，所以在进行push操作时每一个元素压入栈，esp都要-4，在进行pop操作时每弹出一个元素esp+4。

汇编​

比如如下的函数的汇编代码

int add1(int t1,int t2){
    int tmp=t1+t2;
    return tmp;
}
tmp= dword ptr -4
t1= dword ptr  10h
t2= dword ptr  18h

push    rbp  //将ebp入栈(64位叫rbp)
mov     rbp, rsp  //将ebp设置为当前的esp，相当于保存当前的栈底地址，这里把esp也叫做rsp
sub     rsp, 10h  //对栈分配空间
mov     [rbp+t1], ecx  //对t1进行赋值(传入函数的值)
mov     [rbp+t2], edx  //对t2进行赋值(传入函数的值)
mov     edx, [rbp+t1]  
mov     eax, [rbp+t2]					
add     eax, edx						//进行加法
mov     [rbp+tmp], eax       //保存返回值
mov     eax, [rbp+tmp]					//将eax作为返回值
add     rsp, 10h						//释放
pop     rbp								//rbp出栈
retn
_Z4add1ii endp		// add1(int,int) 结束