数据结构一：栈

什么是栈?

一种有次序的数据项集合，在栈中，数据项的加入和移除都仅发生在同一端，称为栈顶；另一端叫栈底。
后进先出：距离栈底越近的数据项，留在栈中的时间就越长；而最新加入栈的数据项会被最先移除。

栈的定义

class stack:
    def __init__(self):
        self.items = []
    def push(self, item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def peek(self):
        return self.items[-1]
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)

一、测试

s = stack()
print(s.isEmpty()) # True
s.push(4)
s.push('dog')
print(s.peek())    # dog
s.push(True)
print(s.size())    # 3
print(s.isEmpty()) # False
s.push(8.4)
print(s.pop())     # 8.4
print(s.pop())     # True
print(s.size())    # 2

栈的应用一：括号匹配

class Solution:
  def isValid(self, s: str) -> bool:
      stack = []
      for c in s:
          if c in '([{':
              stack.append(c)
          else:
              if not stack:
                  return False
              else:
                  last = stack.pop()
                  if c == ')' and last == '(':
                      continue
                  elif c == ']' and last == '[':
                      continue
                  if c == '}' and last == '{':
                      continue
                  else:
                      return False
      return stack == []

栈的应用二：进制转换

一、10进制转7进制

class Solution:
    def convertToBase7(self, num: int) -> str:
        base = 7  # 例：十进制转七进制
        if num == 0:
            return '0'
        if num < 0:
            num = -num
            fuhao = True
        else:
            fuhao = False
        stack = []
        while num > 0:
            stack.append(num % base)
            num = num // base
        ans = ''
        while stack:
            ans += str(stack.pop())
        if fuhao == True:
            ans = '-' + ans
        return ans

二、10进制转-2进制

class Solution:
    def baseNeg2(self, N: int) -> str:
        if N == 0:
            return '0'
        stack = []
        ans = ''
        while N != 0:
            if N % 2 == 0:
                stack.append(N % -2)
                N //= -2
            else:
                # N是奇数 则情况稍有不同
                stack.append('1')
                N = int((N-1)/(-2))
        while stack:
            ans += str(stack.pop())
        return ans

栈的应用三：中缀表达式转前缀表达式

（1）遇到数字：直接输出
（2）遇到左括号：直接入栈
（3）遇到右括号：输出栈顶元素，直到栈顶元素为左括号为止，然后把左括号pop掉
（4）遇到运算符：输出优先级 >= 自己的栈顶元素，直到栈为空或遇到左括号，然后自己入栈

import sys
Pri = dict()
Pri['+'], Pri['-'], Pri['*'], Pri['/'], Pri['('] = 1, 1, 2, 2, 0

while True:
    s = sys.stdin.readline().strip()
    if not s:
        break
    stack = []
    ans = ''
    for c in s:
        if c not in '+-/*()':
            ans += c
        else:
            if c == '(':
                stack.append(c)
            elif c == ')':
                while stack[-1] != '(':
                    ans += stack.pop()
                stack.pop()
            elif (not stack or Pri[stack[-1]] < Pri[c]):
                stack.append(c)
            else:
                while stack and Pri[stack[-1]] >= Pri[c]:
                    ans += stack.pop()
                stack.append(c)
    while stack:
        ans += stack.pop()
    print(ans)

栈的应用四：后缀表达式计算

stack2 = []
for c in ans:
    if c not in '+-/*':
        stack2.append(int(c))
    else:
        b = stack2.pop()
        a = stack2.pop()
        if c == '+':
            k = a+b
        elif c == '-':
            k = a-b
        elif c == '*':
            k = a*b
        else:
            k = int(a/b)
        stack2.append(k)
print(stack2[0])