数据结构与算法 - 栈

栈是一种后进先出的数据结构，栈的常见操作包括入栈（Push）、出栈（Pop），栈就好像一摞盘子，每次放盘子总是放到最上面，同样每次也是从最上面取。

栈的实现

可以使用数组或者链表来实现栈结构，本文采用基于数组的链表实现，下面主要实现栈的入栈、出栈、查询栈顶元素等操作。

入栈：

public void Push(T item)
{
    if (size == items.Length){
        T[] newArray = new T[items.Length == 0 ? defaultSize : items.Length * 2];
        Array.Copy(items, newArray, items.Length);
        items = newArray;
    }
    items[size++] = item;
}

出栈：

public T Pop()
{
    if (size == 0)
        throw (new InvalidOperationException("stack under flow"));

    var top = items[--size];
    items[size] = default(T);
    return top;
}

完整代码在这里。

应用场景

栈这种数据结构在日常开发中还是比较常用的，主要的应用场景包括：

函数调用
表达式求值
括号匹配

函数调用

在进行单步调试时，可能经常会看到调用栈这个东西，正如它的名字所指，它是一种栈结构，我们通过一段代码来简单看下它是如何工作的。

int main(){
    int a = 1;
    int b = 2;
    int sum = 0;
    sum = add(2,4);
    return 0;
}

int add(int v1,int v2){
    int sum = 0;
    sum = v1 + v2;
    return sum;
}