今天先来两个简单的数据结构——栈和队列吧。

栈 (Stack)

栈是一种线性结构，与数组相比，栈对应的操作是数组的子集。

它只能从一端添加元素，也只能从一端取出元素(这一端称之为栈顶)。

Stack这种数据结构用途很广泛，在计算机的使用中，大量的运用了栈，比如编译器中的词法分析器、Java虚拟机、软件中的撤销操作（Undo）、浏览器中的回退操作，编译器中的函数调用实现等等。

栈的实现

函数说明

栈可以用数组和链表来实现，这里我用链表写了一遍。

链表实现

#include <list>
using namespace std;
//我之前写过链表了，所以这里直接用C++里面的list吧

class Stack
{
private:
    list<int> value;

public:
    /*入栈，出栈*/
    void push(int data) { value.push_back(data); }
    int pop()
    {
        int tmp = top();
        value.pop_back();
        return tmp;
    }

    /*栈信息*/
    int top() { return value.back(); }
    int size() { return value.size(); }
    bool empty() { return value.empty(); }
};