1. 栈的实现

特点：先进后出、后进先出

1.1 顺序栈

顺序栈是依赖数组实现的。

其代码实现如下：

class SequenceStack {
public:
    SequenceStack(int size = 10);
    ~SequenceStack();

public:
    // 入栈
    void push(int val);
    // 出栈
    void pop();
    // 返回栈顶元素
    int top() const;
    // 栈是否为空
    bool empty() const;
    // 返回栈大小
    int size() const;
    // 打印
    void print() const;

private:
    // 数组扩容
    void expand(int size);

private:
    int* pStack_;
    int  top_; // 栈顶索引
    int  cap_; // 当前栈容量
};

SequenceStack::SequenceStack(int size)
    : pStack_(new int[size])
    , top_(0)
    , cap_(size) {
}

SequenceStack::~SequenceStack() {
    delete[] pStack_;
    pStack_ = nullptr;
}

void SequenceStack::push(int val) {
    if (top_ == cap_)
        expand(cap_ * 2);
    pStack_[top_++] = val;
}

void SequenceStack::pop() {
    if (top_ == 0) return;
    top_--;
}

int SequenceStack::top() const {
    if (top_ == 0)
        throw "Stack is empty";
    return pStack_[top_ - 1];
}

bool SequenceStack::empty() const {
    return top_ == 0;
}
 
int SequenceStack::size() const {
    return top_;
}

void SequenceStack::print() const {
    for (int i = top_ - 1; i >= 0; i--) {
        cout << pStack_[i] << " ";
    }
    cout << endl;
}

void SequenceStack::expand(int size) {
    int* p = new int[size];
    memcpy(p, pStack_, top_ * sizeof(int));
    delete[] pStack_;
    pStack_ = p;
    cap_    = size;
}

1.2 链式栈

链式栈是依赖链表实现的。

其代码实现如下：

class LinkedStack {
public:
    LinkedStack();
    ~LinkedStack();

    // 出栈
    void push(int val);
    // 入栈
    void pop();
    // 返回栈顶
    int top() const;
    // 返回栈大小
    int size() const;
    // 栈是否为空
    bool empty() const;
    // 打印
    void print() const;

private:
    struct Node {
        Node(int data = 0)
            : data_(data)
            , next_(nullptr) {
        }
        int   data_;
        Node* next_;
    };

    Node* head_;
    int   size_;
};

LinkedStack::LinkedStack()
    : head_(new Node)
    , size_(0) {
}

LinkedStack::~LinkedStack() {
    Node* cur = head_->next_;
    while (cur) {
        head_->next_ = cur->next_;
        delete cur;
        cur = head_->next_;
    }
    delete head_;
}

void LinkedStack::push(int val) {
    Node* node   = new Node(val);
    node->next_  = head_->next_;
    head_->next_ = node;
    size_++;
}

void LinkedStack::pop() {
    if (size_ == 0) return;
    Node* node   = head_->next_;
    head_->next_ = node->next_;
    size_--;
    delete node;
}

int LinkedStack::top() const {
    if (size_ == 0)
        throw "Stack is empty";
    return head_->next_->data_;
}

int LinkedStack::size() const {
    return size_;
}

bool LinkedStack::empty() const {
    return size_ == 0;
}

void LinkedStack::print() const {
    Node* node = head_->next_;
    while (node) {
        cout << node->data_ << " ";
        node = node->next_;
    }
    cout << endl;
}

2. 常见的算法问题

2.1 括号匹配问题

如下图所示，对于括号的匹配问题，可以使用栈结构来模拟括号匹配。

其基本的过程如下：

• 如果遇到左括号就入栈
• 如果遇到右括号
  • 如果栈为空则返回 false
  • 如果栈顶元素与当前的右括号不匹配则返回 false
  • 如果栈顶元素与当前的右括号匹配则弹出栈顶元素

练习题目: 20. 有效的括号 - 力扣（LeetCode）

2.2 逆波兰表达式求解

逆波兰表达式是一种后缀表达式，所谓后缀就是指运算符写在后面。

• 通常所使用的算式称为中缀表达式，如 (1 + 2) * (3 + 4)
• 该算式的逆波兰表达式为：( (1 2 +) (3 4 +) * )

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即使写成 1 2 + 3 4 + * 也可以依据次序计算出正确的结果
• 适合栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中

例如对于后缀表达式：1 2 + 3 4 + * ，其计算过程如下表：

将一个中缀表达式转化为后缀表达式的过程如下：

• 从左到右依次扫描中缀表达式
• 遇到数字则直接放入后缀表达式
• 如果遇到操作符
  • 如果栈为空，则直接将操作符放入符号栈
  • 如果栈不为空，则比较当前符号和栈顶符号元素的优先级
    • 如果当前符号比栈顶符号的优先级高，则直接入栈
    • 如果当前符号比栈顶符号的优先级相等
      • 如果当前符号为从左到右结合，即 +、-、*、/ 等，那就将当前符号加入后缀表达式
      • 如果当前符号为从右到左结合，即 ^ 等，那就入栈
    • 如果当前符号比栈顶符号的优先级低，那就将当前符号放入后缀表达式
  • 如果遇到的是 (，则直接入栈
  • 如果遇到的是 )，则依次出栈，直到碰到 （

比如对于中缀表达式: ((a + b) c) / ((a - b) a^b) ，其转化过程如下表所示：

练习题目： 150. 逆波兰表达式求解 - 力扣（LeetCode）

3. STL实现

STL 的 stack 实现了栈数据结构，它是一种先进后出的数据结构。由于 stack 系以底部容器完成其所有工作，而具有这种 “修改某物接口，形成另一种风貌” 之性质者，称为adapter(配接器)，因此stack往往被归类为container adapter(容器适配器)。

stack 所有元素的进出都必须符合 “先进后出” 的条件，只有 stack 的顶端元素，才有机会被外界取用。stack 不提供遍历功能，也不提供迭代器。

除了使用 deque 作为底层容器外，stack 也可以使用双向链表 list 作为底层容器。