파이썬 API 둘러보기

simpleadt(custom)

Stack, Queue, Heap, HeapSet

Stack, Queue, Heap, HeapSet

API들은 눈이 좀 어지러워서, 최소한의 기능만 가진 자료구조들을 만들어 보았다.

사실은 스택에 push / pop 이 아니라 append / pop 을 하니까 좀 찝찝하다는... 같잖은 이유다.

힙은 ADT가 아니라는데, simpledatastructure는 이름이 너무 길어서 그냥 adt를 붙였다.

 

simpleadt.py:

"""
simpleadt.py
by jhjang

simple Stack, Queue, Heap, and HeapSet

though heap is not an ADT, a module name "simpledatastructure" is too long!
"""
from collections import deque
from heapq import *


class Stack:
    def __init__(self, *items):
        self._lst = [*items]
        self.size = len(self._lst)

    def push(self, *items):
        self._lst.extend(items)
        self.size += len(items)

    def pop(self):
        self.size -= 1
        return self._lst.pop()

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

    def isempty(self):
        return self.size <= 0


class Queue:
    def __init__(self, *items):
        self._deq = deque(items)
        self.size = len(items)

    def enqueue(self, *items):
        self._deq.extend(items)
        self.size += len(items)

    def dequeue(self):
        self.size -= 1
        return self._deq.popleft()

    def front(self):
        return self._deq[0]

    def rear(self):
        return self._deq[-1]

    def isempty(self):
        return self.size <= 0


# because Heap depends on heapq, which only supports min heap,
# provide a priority-inversing function if you want a max heap
# the function should be behave like this: invf(invf(item)) = item
class Heap:
    def __init__(self, *items, invf=lambda x: x):
        self._heap = list(map(invf, items))
        self.size = len(self._heap)
        self._invf = invf
        heapify(self._heap)

    def insert(self, *items):
        for item in items:
            heappush(self._heap, self._invf(item))
            self.size += 1

    def extract(self):
        self.size -= 1
        return self._invf(heappop(self._heap))

    def peek(self):
        return self._invf(self._heap[0])

    def isempty(self):
        return self.size <= 0


# heap containing unique items
# reference: https://stackoverflow.com/questions/5997189/how-can-i-make-a-unique-value-priority-queue-in-python
class HeapSet(Heap):
    def __init__(self, *items, invf=lambda x: x):
        super().__init__(*items, invf=invf)
        self._set = set(items)

    def insert(self, *items):
        for item in items:
            if item not in self._set:
                super().insert(item)
                self._set.add(item)

    def extract(self):
        item = super().extract()
        self._set.remove(item)
        return item

 

테스트 코드:

from simpleadt import *


# s = Stack()
s = Stack(1, 2, 3)
s.push(4)
s.push(5)
s.push(6, 7, 8)

print(f'{s.peek()}({s.size})')
while not s.isempty():
    print(f'{s.pop()}({s.size})', end=' ')
print()

# q = Queue()
q = Queue(1, 2, 3)
q.enqueue(4)
q.enqueue(5)
q.enqueue(6, 7, 8)

print(f'{q.front()} {q.rear()} ({q.size})')
while not q.isempty():
    print(f'{q.dequeue()}({q.size})', end=' ')
print()

#h = Heap()
#h = Heap(1, 2, 3)
h = Heap(1, 2, 3, invf=lambda x: -x)
h.insert(3)
h.insert(5)
h.insert(10, 1)

print(f'{h.peek()}({h.size})')
while not h.isempty():
    print(f'{h.extract()}({h.size})', end=' ')
print()


#hs = HeapSet()
#hs = HeapSet(1,2,3)
hs = HeapSet(1,2,3, invf=lambda x: -x)
hs.insert(3)
hs.insert(5)
hs.insert(10, 1, 5)

print(f'{hs.peek()}({hs.size})')
while not hs.isempty():
    print(f'{hs.extract()}({hs.size})', end=' ')
print()

 

댓글

댓글 본문
작성자
비밀번호
버전 관리
장과장02
현재 버전
선택 버전
graphittie 자세히 보기