栈

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

    # 入栈
    def push(self,x):
        self.stack.append(x)

    # 出栈
    def pop(self):
        if not self.stack:
            raise IndexError("栈为空，无法出栈")
        return  self.stack.pop()
    
    # 获取栈顶元素，不删除
    def top(self):
        if self.empty():
            raise IndexError("栈为空")
        return self.stack[-1]
    
     # 判断是否为空
    def empty(self):
        return len(self.stack) == 0
    
    # 获取栈长度
    def __len__(self):
        return len(self.stack)
    
    # 打印
    def __str__(self):
        return f"Stack{self.stack}"

if __name__ == '__main__':
    my_stack = MyStack()
    my_stack.push(1)
    my_stack.push(2)
    my_stack.push(3)

    print(my_stack.pop())
    print(my_stack.pop())
    print(my_stack.pop())

队列

list.pop(0) 会把列表所有元素整体前移，时间复杂度 O (n)，数据量大时很慢

class MyQueue:
    def __init__(self):
        self.data = []

    # 入队
    def enqueue(self, x):
        self.data.append(x)

    # 出队并返回队首
    def dequeue(self):
        if self.empty():
            raise IndexError("队列为空，无法出队")
        return self.data.pop(0)

    # 查看队首，不删除
    def front(self):
        if self.empty():
            raise IndexError("队列为空")
        return self.data[0]

    # 判断是否为空
    def empty(self):
        return len(self.data) == 0

    # 支持 len(队列)
    def __len__(self):
        return len(self.data)

    # 打印队列内容
    def __str__(self):
        return f"Queue{self.data}"


if __name__ == '__main__':
    my_queue = MyQueue()
    my_queue.enqueue(1)
    my_queue.enqueue(2)
    my_queue.enqueue(3)

    print(my_queue.dequeue())
    print(my_queue.dequeue())
    print(my_queue.dequeue())
    print(my_queue.empty())

双栈模拟队列

摊还 O (1)，偶尔一次性 O (n) 搬运
适用场景：小规模数据、追求内存紧凑

class MyQueue:
    def __init__(self):
        self.in_stack = []   # 入队栈
        self.out_stack = []  # 出队栈

    def enqueue(self, x):
        self.in_stack.append(x)

    # 把in_stack全部转移到out_stack
    def _transfer(self):
        while self.in_stack:
            self.out_stack.append(self.in_stack.pop())

    def dequeue(self):
        if self.empty():
            raise IndexError("队列为空，无法出队")
        if not self.out_stack:
            self._transfer()
        return self.out_stack.pop()

    def front(self):
        if self.empty():
            raise IndexError("队列为空")
        if not self.out_stack:
            self._transfer()
        return self.out_stack[-1]

    def empty(self):
        return len(self.in_stack) == 0 and len(self.out_stack) == 0

    def __len__(self):
        return len(self.in_stack) + len(self.out_stack)

    def __str__(self):
        temp = []
        temp.extend(reversed(self.out_stack))
        temp.extend(self.in_stack)
        return f"Queue{temp}"


if __name__ == '__main__':
    q = MyQueue()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    print(q.dequeue())
    print(q.dequeue())
    q.enqueue(4)
    print(q.front())
    print(q.dequeue())
    print(q.dequeue())
    print(q.empty())

链表模拟队列（实际开发）

稳定 O (1)，无批量搬运
适用场景：高性能实时队列、大数据量动态场景

# 定义链表节点
class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

# 链表实现队列
class QueueByLinkedList:
    def __init__(self):
        self.head = None  # 队首
        self.tail = None  # 队尾
        self.size = 0     # 记录元素数量

    # 入队
    def enqueue(self, val):
        new_node = ListNode(val)
        # 队列为空，头尾都指向新节点
        if self.empty():
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1

    # 出队
    def dequeue(self):
        if self.empty():
            raise IndexError("队列为空，无法出队")
        res_node = self.head
        self.head = self.head.next
        self.size -= 1
        # 若弹出后队列为空，tail置空
        if self.empty():
            self.tail = None
        return res_node.val

    # 查看队首元素
    def front(self):
        if self.empty():
            raise IndexError("队列为空")
        return self.head.val

    # 判空
    def empty(self):
        return self.size == 0
    
    # 获取长度
    def __len__(self):
        return self.size
    
    # 打印
    def __str__(self):
        vals = []
        cur = self.head
        while cur:
            vals.append(str(cur.val))
            cur = cur.next
        return "Queue[" + ", ".join(vals) + "]"


# 测试代码
if __name__ == "__main__":
    q = QueueByLinkedList()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)

    print(q.front())   # 1
    print(q.dequeue()) # 1
    print(q.dequeue()) # 2

    q.enqueue(4)
    print(q.front())   # 3
    print(q.dequeue()) # 3
    print(q.dequeue()) # 4

    print(q.empty())    # True