栈

栈（Stack）是一种只允许在一端进行插入或删除操作的线性表。这种结构具有后进先出（Last In First Out, LIFO）的特性，意味着最后插入的元素将是第一个被删除的。在栈中，插入和删除操作通常发生在同一端，称为栈顶，而另一端则被称为栈底。

栈的基本操作包括：

• 初始化（InitStack）：创建一个空栈。
• 判空（Empty）：检查栈是否为空。
• 进栈（Push）：在栈顶添加一个元素。
• 出栈（Pop）：移除栈顶的元素。
• 读栈顶元素（GetTop）：获取栈顶元素的值，但不移除它。
• 销毁栈（DestroyStack）：移除栈中的所有元素，并释放内存。

栈可以通过数组（顺序栈）或链表（链栈）来实现。顺序栈使用连续的内存空间存储元素，而链栈则通过链表的节点来存储，每个节点包含数据和指向下一个节点的指针。

C++ STL 之 Stack

头文件<stack>

常用操作

1. push(x) 将x入栈
2. top() 返回栈顶元素
3. pop() 删除栈顶元素
4. size() 返回栈中元素个数
5. empty() 检查是否空栈

栈的应用

括号匹配问题

#include <stack>
#include <unordered_map>
#include <string>

bool brace_match(std::string s) {
    std::unordered_map<char, char> match = {{'}', '{'}, {']', '['}, {')', '('}};
    std::stack<char> st;
    
    for (char ch : s) {
        if (ch == '{' || ch == '[' || ch == '(') {
            st.push(ch);
        } else {
            if (st.empty()) {
                return false;
            } else if (st.top() == match[ch]) {
                st.pop();
            } else {
                return false;
            }
        }
    }
    
    return st.empty();
}

def brace_match(s):
    match = {'}':'{', ']':"[", ')':'('}
    stack = Stack()
    for ch in s:
        if ch in {'(','[','{'}:
            stack.push(ch)
        else:   #ch in {'}',']',')'}
            if stack.is_empty():
                return False
            elif stack.get_top() == match[ch]:
                stack.pop()
            else: # stack.get_top() != match[ch]
                return False
    if stack.is_empty():
        return True
    else:
        return False