栈和队列

1. 栈：后进先出

2. 栈的实现　　

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, ele):        # 进栈
        self.stack.append(ele)

    def pop(self):                # 出栈
        self.stack.pop()

    def get_top(self):            # 取栈顶
        if len(self.stack) > 0:
            return self.stack[-1]

    def is_empty(self):        # 判断栈为空
        return len(self.stack) == 0    

3. 栈的应用：括号匹配问题

def brace_match(str):
    stack = Stack()　　　　# 调用栈对象
    match = {'}':'{',']':'[',')':'('}   # 字典中的键值对为正确括号匹配
    for i in str:
        if i in {'(','[','{'}:  # 如果是左括号，则入栈
            stack.push(i)
        else:   # 右括号的三种情况
            if stack.is_empty():    # 栈为空直接判断False
                return False
            elif stack.get_top() == match[i]:   # 栈不为空时栈顶匹配字典，匹配上为一对则出栈
                stack.pop()
            else:   # 匹配不上判断False
                return False
    if stack.is_empty():    # 直到匹配所有字符后栈为空，则说明括号匹配成功
        return True
    else:
        return False

4. 队列：先进先出

5. 环形队列：首尾相连的队列

6. 队列的实现

# 环形队列
class Queue:
    def __init__(self, size):
        self.queue = [None for _ in range(size)]
        self.size = size
        self.rear = 0   # 队尾指针
        self.front = 0  # 队首指针
    # 队尾队列
    def push(self, ele):
        if not self.is_filled():
            self.rear = (self.rear + 1) % self.size
            self.queue[self.rear] = ele
        else:
            raise IndexError("Queue is filled")
    # 队首指针
    def pop(self):
        if not self.is_empty():
            self.front = (self.front + 1) % self.size
            return self.queue[self.front]
        else:
            raise IndexError("Queue is empty")
    # 队空判断
    def is_empty(self):
        return self.rear == self.front
    # 堆满判断
    def is_filled(self):
        return (self.rear + 1) % self.size == self.front