栈和队列

栈实现

栈是一种操作受限的线性表只允许从一端插入和删除数据。栈有两种存储方式，即线性存储和链接存储（链表）。栈的一个最重要的特征就是栈的插入和删除只能在栈顶进行，所以每次删除的元素都是最后进栈的元素，故栈也被称为后进先出（LIFO）表。栈有两种处理方式，即进栈（push）和出栈（pop），因为在进栈只需要移动一个变量存储空间，所以它的时间复杂度为O(1)，但是对于出栈分两种情况，栈未满时，时间复杂度也为O(1)，但是当栈满时，需要重新分配内存，并移动栈内所有数据，所以此时的时间复杂度为O(n)。

import abc
class Stack(metaclass=abc.ABCMeta):
    @abc.abstractmethod
    def pop(self):
        pass
    @abc.abstractmethod
    def push(self, item):
        pass
    @abc.abstractmethod
    def clear(self):
        pass
    @abc.abstractmethod
    def empty(self):
        pass
    @abc.abstractmethod
    def size(self):
        pass
    @abc.abstractmethod
    def top(self):
        pass
    @abc.abstractmethod
    def show(self):
        pass
class MyStack(Stack):
    def __init__(self):
        """ 初始化数据结构为 python 列表"""
        self.__data = []
    def push(self, item):
        """ 入栈 """
        self.__data.append(item)
    def empty(self):
        """ 判断是否为空栈 """
        return self.size() == 0
    def size(self):
        """ 输出栈的大小 """
        return len(self.__data)
    def pop(self):
        """ 出栈 """
        assert self.size() > 0, "stack is empty"
        return self.__data.pop()
    def top(self):
        """ 查看栈顶值 """
        assert self.size() > 0, "stack size is 0"
        return self.__data[self.size() - 1]
    def clear(self):
        """ 清空栈 """
        del self.__data[:]
    def show(self):
        str_start = "["
        for i in range(self.size()):
            if i == self.size() - 1:
                str_start += str(i)
            else:
                str_start += str(i) + ","
        str_start += "] top "
        print(str_start)
def is_valid(s: str) -> bool:
    """ 括号匹配 """
    stack = MyStack()
    for i in s:
        if i in ["(", "[", "{"]:
            stack.push(i)
        else:
            if stack.empty():
                return False
            top_s = stack.pop()
            if i == ")" and top_s != "(":
                return False
            elif i == "]" and top_s != "[":
                return False
            elif i == "}" and top_s != "{":
                return False
    return stack.empty()

队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

import abc
class ListQueue(metaclass=abc.ABCMeta):
    @abc.abstractmethod
    def dequeue(self):
        pass
    @abc.abstractmethod
    def enqueue(self, item):
        pass
    @abc.abstractmethod
    def empty(self):
        pass
    @abc.abstractmethod
    def size(self):
        pass
    @abc.abstractmethod
    def front(self):
        pass
    @abc.abstractmethod
    def show(self):
        pass
class MyQueue(ListQueue):
    def __init__(self):
        """ 初始化数据结构为 python 列表"""
        self.__data = []
    def enqueue(self, item):
        """ 入队 """
        self.__data.append(item)
    def empty(self):
        """ 判断是否为空队 """
        return self.size() == 0
    def size(self):
        """ 输出队列的大小 """
        return len(self.__data)
    def dequeue(self):
        """ 出队 """
        assert self.size() > 0, "stack is empty"
        return self.__data.pop(0)
    def front(self):
        """ 查看队首元素 """
        assert self.size() > 0, "stack size is 0"
        return self.__data[0]
    def show(self):
        str_start = "front ["
        for i in range(self.size()):
            if i == self.size() - 1:
                str_start += str(i)
            else:
                str_start += str(i) + ","
        str_start += "] "
        print(str_start)

循环队列

从基本的队列数据结构中可以看到，在删除数据时候，需要对删除后的剩余数据进行位置转换，时间复杂度为O（n），为了解决这个问题，可以把队列当作一个首尾相连的环，这样在进行删除的元素时候就不用每次都移动剩余的元素，只需维护几个变量即可。这样做的优点就是可以适当的时候进行扩容和缩容，可以把时间复杂度均摊下来。

class LoopQueue:
    def __init__(self, capacity=10):
        self.arr = [None] * (capacity+1)  # 由于特意浪费了一个空间，所以arr的实际大小应该是用户传入的容量+1
        self.front = 0  # 队首下标
        self.tail = 0   # 下一个数据如队的下标
        self.size = 0   # 队列数据总量
        self.capacity = capacity  # 队列容许的最大数据量
    def __len__(self):
        return len(self.arr)
    def size(self):
        # 获取队列中元素个数
        return self.size
    def get_capacity(self):
        # 获取队列容量
        return len(self.arr) - 1
    def is_full(self):
        # 判断队列是否为满 (取余) 当一个数据入队后如果和队首位置重复表示此时队列已满
        return (self.tail + 1) % len(self.arr) == self.front
    def is_empty(self):
        # 判断队列是否为空 可以判断队列中的元素个数 或是否队首和队尾下标重复(初始话的情况)
        # return front == tail
        return self.size == 0
    def get_front(self):
        # 获取队首
        return self.arr[self.front]
    def enqueue(self, e):
        # 入队
        if self.is_full():
            self.resize(self.get_capacity() * 2)  # 如果队列满，以当前队列容积的2倍进行扩容
        self.arr[self.tail] = e
        self.tail = (self.tail + 1) % len(self.arr)
        self.size += 1
    def dequeue(self):
        # 先判断队列是否为空
        assert not self.is_empty(), "Cannot dequeue from en empty queue"
        result = self.arr[self.front]
        self.arr[self.front] = None
        # 更新其下标
        self.front = (self.front + 1) % len(self.arr)
        self.size -= 1
        # 如果元素个数少于容积的1/4并且元素个数
        if self.size < self.get_capacity() // 4 and self.get_capacity() > 1:
            self.resize(self.get_capacity() // 2)
        return result
    # 扩容或者缩容
    def resize(self, new_capacity: int):
        new_arr = [None] * (new_capacity + 1)
        for i in range(self.size):
            new_arr[i] = self.arr[(i + self.front) % len(self.arr)]
        self.arr = new_arr
        self.front = 0
        self.tail = self.size
    def show(self):
        print(self.arr)