栈（stack）是一种先进后出的线性数据结构。

栈的常用操作

// 初始化栈

stack<int> stack;

// 入栈
stack.push(1);

// 访问栈顶元素
int top = stack.top();

// 出栈
stack.pop();

// 获取栈的大小
int size = stack.size();

// 判空
bool empty = stack.empty();

栈的实现

栈可以视为一种受限的数组或链表，因为只能在栈顶进行插入或者删除。

基于链表的实现

利用“头插法”，入栈操作只需要将元素插入链表头部，出栈操作只需要从链表中删除头节点。

class LinkedListStack {
  private:
    ListNode* stackTop;
  	int stkSize;
  public:
    LinkedListStack() {
      stackTop = nullptr;
      stkSize = 0;
    }
  
    ~LinkedListStack() {
      freeMemoryLinkedList(stackTop);
    }
  
    int size() {
      return stkSize;
    }
    
    bool isEmpty() {
      return size() == 0;
    }
  
    void push(int num) {
      ListNode* node = new ListNode(num);
      node->next = stackTop;
      stackTop = node;
      ++stkSize;
    }
    
    int pop() {
      int num = top();
      ListNode* tmp = stackTop;
      stackTop = stackTop->next;
      delete tmp;
      --stkSize;
      return num;
    }
  	 int top() {
       if (isEmpty()) {
         throw out_of_range("stack is empty");
       }
       
       return stackTop->val;
     }
  
  vector<int> toVector() {
    ListNode* node = stackTop;
    vector<int> res(size());
    
    for (int i = res.size() - 1; i >= 0; --i) {
      res[i] = node->val;
      node = node->next;
    }
    
    return res;
  }
}

基于数组的实现

由于栈的元素可能源源不断增加，因此使用动态数组实现比较合理。

class ArrayStack {
 private:
   vector<int> stack;
 public:
  int size() {
    return stack.size();
  }
  
  bool isEmpty() {
    stack.size() == 0;
  }
  
  void push(int num) {
    stack.push_back(num);
  }
  
  int pop() {
    int num = top();
    stack.pop_back();
    return num;
  }
  
  int top() {
    if (isEmpty())
      throw out_of_range("stack is empty");
    return stack.back();
  }
  
  vector<int> toVector() {
    return stack;
  }
}

两种实现对比

• 基于数组实现的栈在触发扩容机制时，时间效率会降低，额外申请但尚未使用的空间也会造成浪费；但由于扩容是低频操作，因此平均效率更高。
• 基于链表实现的栈，单个节点占用的空间相对大。

栈的典型应用

• 浏览器的后退与前进、撤销与恢复。
• 程序运行内存管理，函数调用时会添加栈帧记录函数上下文信息。