只见它们后来居上

这就是栈

栈（stack） 也是一种非常基础的数据结构，非常简单

栈有两种实现方式，一种是普通的数组，一种是普通的链表

用链表写

鉴于之前已经搓过一次链表了，就偷懒不重复造轮子了

class LinkedStack : protected LinkedList {
private:

public:
  using LinkedList::LinkedList; // 偷懒

};

这里偷了个懒，直接把链表改了个名（其实也没有，因为原本的成员都变成protected了

然后加入一些很简单的方法

bool isEmpty() {  // 是空的吗？
  return size() == 0;
}
void push(int val){  // 入栈
  append(val);
}

int pop() {  // 出栈
  int value = access(size() - 1) -> val;
  remove(size() - 1);
  return value;
}

int top() {  // 顶上是什么？
  if (isEmpty()){
    throw out_of_range("栈是空的");
  }
  return access(size() - 1) -> val;
}

int size() {  // 有多少元素
  return length();
}

emmm……这好像没什么可讲的，因为实在太简单了

这里用的是尾插法，也就是在后面入栈出栈

当然相对的还有头插法

用数组写

C艹最棒的就是有vector这种东西，再也不用担心数组不够大啦（虽然感觉还是不如列表

实现真的很简单

class ArrayStack {  // 我连注释都懒得加
private:
    vector<int> stack;
    public:
    int size() {
        return stack.size();
    }
  bool isEmpty() {
        return stack.size() == 0;
    }
  int top() {
        if (isEmpty()) {
            throw out_of_range("栈是空的");
        }
    return stack.back();
    }
  void push(int val) {
        stack.push_back(val);
    }
  int pop() {
        int num = top();
        stack.pop_back();
        return num;
    }
  vector<int> toVector() {
        return stack;
    }
};

所以栈真的很简单呐