[자료구조] Circle Deque (원형 덱) 구현

Circle Deque (원형 덱)

class MyCircularDeque:

    def __init__(self, k: int):
        self.q = [None] * (k+1)
        self.max = k+1
        self.front = 0
        self.rear = 0

    def insert_front(self, value: int):
        if self.is_full():
            print('Deque is Full')
        else:
            self.q[self.front] = value
            self.front = (self.front - 1 + self.max) % self.max

    def insert_last(self, value: int):
        if self.is_full():
            print('Deque is Full')
        else:
            self.rear = (self.rear + 1) % self.max
            self.q[self.rear] = value

    def delete_front(self) -> int:
        if self.is_empty():
            print('Deque is empty')
            return
        else:
            tmp = self.q[(self.front + 1) % self.max]
            self.q[(self.front + 1) % self.max] = None
            self.front = (self.front + 1) % self.max
            return tmp

    def delete_last(self) -> int:
        if self.is_empty():
            print('Deque is empty')
            return
        else:
            tmp = self.q[self.rear]
            self.q[self.rear] = None
            self.rear = (self.rear - 1 + self.max) % self.max
            return tmp

    def is_empty(self) -> bool:
        return self.front == self.rear

    def is_full(self) -> bool:
        return self.front == (self.rear + 1) % self.max

    def print(self):
        front = self.front
        rear = self.rear
        while(front != rear):
            print(self.q[(front + 1) % self.max], end=' -> ')
            front = (front + 1) % self.max
        print()


dq = MyCircularDeque(5)

print('<insert>')
for i in range(4, 6):
    dq.insert_last(i)
    dq.print()

for i in range(3, 0, -1):
    dq.insert_front(i)
    dq.print()

print()
print("결과 : ", end="")
dq.print()
print()

print('<delete>')
for i in range(0, 3):
    dq.delete_last()
    dq.print()

for i in range(0, 2):
    dq.delete_front()
    dq.print()

print("결과 : ", end="")
dq.print()


"""
<insert>
4 ->
4 -> 5 ->
3 -> 4 -> 5 ->
2 -> 3 -> 4 -> 5 ->
1 -> 2 -> 3 -> 4 -> 5 ->

결과 : 1 -> 2 -> 3 -> 4 -> 5 ->

<delete>
1 -> 2 -> 3 -> 4 ->
1 -> 2 -> 3 ->
1 -> 2 ->
2 ->

결과 :
"""

 

Circle queue는 여기서 insert_front()와 delete_last()만 삭제하면 된다.