先進(jìn)先出

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

    def append(self, val):
        return self.items.append(val)

    def pop(self):
        return self.items.popleft()

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


def test_qeue():
    q = Queue()
    q.append(0)
    q.append(1)
    q.append(2)
    q.append(3)
    print(q.pop())
    print(q.pop())
    print(q.pop())
    print(q.pop())

test_qeue()

后進(jìn)先出

from collections import deque

class Stack():
    def __init__(self):
        self.items = deque()

    def push(self, val):
        return self.items.append(val)

    def pop(self):
        return self.items.pop()

def test_stack():
    s = Stack()
    s.push(0)
    s.push(1)
    s.push(2)
    s.push(3)
    s.push(4)
    print(s.pop())
    print(s.pop())
    print(s.pop())
    print(s.pop())
    print(s.pop())

test_stack()

二叉樹(shù)

先序遍歷

中序遍歷

image.png

import heapq

class Topk():
    """獲取大量元素topk 元素，固定內(nèi)存
    思路：
    1、先放入元素前K個(gè)建立一個(gè)最小堆
    2、迭代剩余元素：
        如果當(dāng)前元素小于堆頂元素，跳過(guò)該元素(肯定不是前K大)
        否則替代堆頂元素為當(dāng)前元素，并重新調(diào)整堆
    """

    def __init__(self, iterable, k):
        self.minheap = []
        self.capacity = k
        self.iterable = iterable

    def push(self, val):
        if len(self.minheap) >= self.capacity:
            min_val = self.minheap[0]
            if val < min_val: #當(dāng)然你可以直接if val > min_val操作，這里只是顯示指出跳過(guò)這個(gè)元素
                pass
            else:
                heapq.heapreplace(self.minheap, val) # 返回并且pop堆頂最小值，推入新的val值并調(diào)整堆
        else:
            heapq.heappush(self.minheap, val) # 前面k個(gè)元素直接放入minheap

    def get_topk(self):
        for val in self.iterable:
            self.push(val)
        return self.minheap

def test():
    import random
    i = list(range(1000))
    random.shuffle(i)
    l = Topk(i, 10)
    print(l.get_topk()) # [990, 991, 996, 992, 995, 997, 998, 993, 994, 999]

test()