数据结构 - 栈

栈是一种 LIFO(Last In First Out) 的数据结构，栈插入和删除都在 栈顶 操作

Python 中内置的数据结构 List 就可以实现栈的后进先出，只需要对其进行简单的封装

class Stack:

    def __init__(self):
        self._stack = []

    def push(self, item):
        self._stack.append(item)

    def pop(self):
        if not self.is_empty:
            return self._stack.pop()
        raise Exception('stack is empty')

    def peek(self):
        if not self.is_empty:
            return self._stack[-1]
        raise Exception('stack is empty')

    def clear(self):
        self._stack.clear()
        
    @property
    def size(self):
        return len(self._stack)

    @property
    def is_empty(self):
        return len(self._stack) == 0

栈的应用

二进制转换

通过 “除二取余法” 将十进制转换为二进制，栈 这种数据结构再适合不过了。

def d2bin(number):
  s = Stack()
  while number > 0:
    s.push(number % 2)
    number = number // 2

  bin_string = str()
  while not s.is_empty:
    bin_string += str(s.pop())

  return bin_string

这样写只是为了距离，Python 内置数据结构和语法比较强大，完全没有必要这样写