Python 的栈到底是个啥？

栈是一种有序的数据结构，如图所示，想要取出下面的元素，就要先从顶端开始，一个一个的拿出，最终获得底端的元素 4。

反过来说，想要把元素按照上面的方式摆放，就要从底端开始放入 4，然后依次放入元素，最后放入 8.4。

因此，这种排列方式称为 LIFO（后入先出，last-in-first-out）。

一个典型的栈结构，需要包含以下功能：

• Stack()创建一个空栈。它不需要参数，且会返回一个空栈。
• push(item)将一个元素添加到栈的顶端。它需要一个参数 item，且无返回值。
• pop()将栈顶端的元素移除。它不需要参数，但会返回顶端的元素，并且修改栈的内容。
• peek()返回栈顶端的元素，但是并不移除该元素。它不需要参数，也不会修改栈的内容。
• isEmpty()检查栈是否为空。它不需要参数，且会返回一个布尔值。
• size()返回栈中元素的数目。它不需要参数，且会返回一个整数。

栈的应用：

• 函数调用
• 进制转换
• 中序 -> 后序（括号匹配）

Python 实现的栈

class Stack:

    _data_list = []

    def push(self, data):
        self._data_list.append(data)

    def pop(self):
        return self._data_list.pop()

    def peek(self):
        return self._data_list[-1]

    def is_empty(self):
        return len(self._data_list) > 0

    def size(self):
        return len(self._data_list)

由于栈是由列表实现的，列表的 pop()和 pop(0)时间复杂度不一致，因此栈还有下面的实现方式：

class Stack:

    _data_list = []

    def push(self, data):
        self._data_list.insert(0, data)

    def pop(self):
        return self._data_list.pop(0)

    def peek(self):
        return self._data_list[0]

    def is_empty(self):
        return len(self._data_list) > 0

    def size(self):
        return len(self._data_list)

两者只有性能上的区别，具体来说就是前者偏向取出，后者偏向插入。

十进制转换成二进制

def convert_o_to_b(int_):
    stack = Stack()
    str_ = ''
    while True:
        a, int_ = int_ % 2, int(int_ / 2)
        stack.push(a)
        if int_ == 0:
            break
    while stack.size:
        item = stack.pop()
        str_ += str(item)
    return str_

# 123256545434567
# 11100000001100111100110100110110101101111000111

前序、中序和后序表达式

有表达式 A * B + C，分别用前序、中序和后序表达：
前序：运算符在两个操作数之前，AB+C
中序：运算符在两个操作数之间，AB+C
后序：运算符在两个操作数之后，AB*C+

中序表达式转换为后序表达式：

def convert_multi(str_):
    stack = Stack()
    priority_map = {
        '*': 3,
        '/': 3,
        '+': 2,
        '-': 2,
        '(': 1,}
    res = ''
    for s in str_.split():
        if s in string.digits:
            res += s
        elif s == '(':
            stack.push(s)
        elif s == ')':
            op = stack.pop()
            while op != '(':
                res += op
                op = stack.pop()
        else:
            while not stack.is_empty and priority_map[stack.peek] >= priority_map[s]:
                res += stack.pop()
            stack.push(s)
    while not stack.is_empty:
        res += stack.pop()
    return res

# '(1 * 2 + 3) * 4 + 5 - 6 + 1 * 2'
# 后序表达式：12*3+4*5+6-12*+