队列和栈

栈

主要特点，先进后出，可以使用动态数组来实现动态扩容机制，每次数组数量不足的时候扩容一倍即可；

设计一个能够获取栈中最大值的栈

class MaxStack:
    def __init__(self):
        """
        核心思路就是维护两个栈，一个记录当前的最大值，一个记录所有的元素，
        push的时候检查放进去的是否大于最大值，如果是，就往最大值栈中放一个
        pop的时候同理，如果pop出来的值是当前的最大值，就在最大值栈中pop一个值出来
        """
        self.data = []
        self.max = []

    def push(self, item: int):
        self.data.append(item)
        if not self.max or self.max[-1] < item:
            self.max.append(item)

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

    def pop(self):
        if self.data:
            res = self.data.pop()
            if res == self.max[-1]:
                self.max.pop()
            return res

    def get_max(self):
        if self.max:
            return self.max[-1]

    def empty(self):
        return len(self.data) == 0

队列

队列的特点是先进先出，可以用数组或者链表实现，下面采用数组实现循环队列：

class MyQueue:
    def __init__(self):
        # 这里模拟静态数组，另外不考虑扩容的问题
        self.data = [None] * 4
        self.capacity = 4
        self.size = 0
        self.head = 0
        self.tail = 0

    def empty(self):
        return self.head == self.tail

    def full(self):
        return (self.tail + 1) % self.capacity == self.head

    def enqueue(self, item):
        if self.full():
            # 扩充一倍容量，
            self.__expansion()
        self.data[self.tail] = item
        self.tail = (self.tail + 1) % self.capacity
        self.size += 1

    def __expansion(self):
        # 扩容，一次扩充一倍容量，攒不实现
        raise Exception()

    def dequeue(self):
        if not self.empty():
            res = self.data[self.head]
            self.head = (self.head + 1) % self.capacity
            self.size -= 1
            if self.size < (self.capacity * 0.5):
                self.__reduction()
            return res

    def __reduction(self):
        """
        缩容，缩小原本一倍的容量，暂不实现
        :return:
        """
        pass

注意一点，循环队列中判断队列满的条件是 (self.tail + 1) % self.capacity == self.head，因此能够放置的最大元素数量是数组的容量-1，另外，扩容机制可以参考动态数组的扩容，一次扩充一倍；

优先级队列

优先级队列可以采用堆来实现，每个元素中安置一个链表或者一个普通的队列来记录优先级相同的元素，确保优先级相同的情况下的顺序；

下面是一个最大堆的实现代码：

class MaxHeap:
    def __init__(self, ll: List[int]):
        self.data = ll
        self.size = len(self.data)
        self.__init_heap()

    def __init_heap(self):
        """
        初始化堆
        从第一个非叶节点开始，逐个进行堆化
        :return:
        """
        i = (len(self.data) >> 1) - 1
        while i >= 0:
            p = i
            while True:
                max_index = p
                r = (p << 1) + 1
                l = (p << 1) + 2
                if r < self.size and self.data[r] > self.data[p]:
                    max_index = r
                if l < self.size and self.data[l] > self.data[max_index]:
                    max_index = l
                if max_index == p:
                    break
                swap(self.data, max_index, p)
                p = max_index
            i -= 1

    def get_max(self):
        if self.data:
            return self.data[0]

    def insert(self, d: int):
        self.size += 1
        self.data.append(d)
        i = self.size - 1
        while i > 0:
            p = (i - 1) >> 1
            if self.data[p] < self.data[i]:
                swap(self.data, i, p)
            i = p

    def pop_max(self):
        if self.size > 0:
            res = self.data[0]
            self.data[0] = self.data[self.size - 1]
            self.size -= 1
            p = 0
            while True:
                r = (p << 1) + 1
                l = (p << 1) + 2
                max_index = p
                if r < self.size and self.data[p] < self.data[r]:
                    max_index = r
                if l < self.size and self.data[max_index] < self.data[l]:
                    max_index = l
                if max_index == p:
                    break
                swap(self.data, p, max_index)
                p = max_index
            return res

堆

堆的定义，一个满二叉树，每个节点的值均大于（小于）其左右子节点的值，这样构成的树，称为最大（小）堆/大（小）顶堆；

由于是满二叉树，因此堆可以使用数组来记录所有的顶点，即从根节点开始，将每层所有的节点按照顺序放入到数组中去，通过节点的索引\(i\)，可以计算出其左右子节点索引依次是：\(2i+1,2i+2\)，其父节点索引为\((i-1)/2\)。

• 堆的初始化

  给定一组元素，将其构建为最大堆；

  主要思路：

  1. 从第一个内部节点开始，逐步向前遍历，每个节点均进行如下构建：
     1. 检查其于子节点的关系，将三个节点构建为符合条件的结构，如果最大值原本就是父节点，停止构建，如果最大值是子节点，则再构建对应子节点的结构
  

• 数据插入

  • 在数组末尾插入元素，即插入一个叶节点；
  • 从插入的叶子节点开始，逐步向上确认比较，如果子节点大于父节点，则交换子父节点的元素；
  • 构建直接到跟节点结束；

• 获取最大（小）值

  • 将根节点元素返回并删除
  • 删除根节点步骤：
    1. 交换根节点和最后一个节点的元素
    2. 从根节点开始，向下重新构建堆，重复构建堆时的操作即可；