자료구조 - Circular Queue 학습

Circular Queue 란?

  • 원형 큐는 선형 큐의 문제점을 보완하기 위한 자료구조이다.
  • rear를 가르키는 포인터가 배열의 마지막 인덱스를 가르키고 있을 때, 앞쪽에서 Dequeue로 발생한 배열의 빈 공간을 활용 할 수 없다.
  • 원형큐에서는 배열의 첫 인덱스부터 다시 데이터 삽입이 가능하다.

Circular Queue 구조

  • 크기가 정해져있는 배열을 사용한다.
  • 비어있을 경우에는 head == tail 인 상태이다.
  • 가득 차 있을 경우에는 head == tail + 1 인 상태이다.
  • 최초 head와 tail을 0번 인덱스로 설정한다.
  • enqueue : 인덱스 tail+1에 data를 enqueue한다.
  • dequeue : 인덱스가 front+1 인 값을 dequeue한다.
  • 첫번째 인덱스는 항상 비워놓는다.
  • 10의 크기를 가진 큐를 사용하기 위해서는 11만큼의 배열 사이즈를 할당해야 한다.

Circular Queue 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class CQueue:
    MAXSIZE = 10
    # 배열 사이즈보다 1 증대시켜 container 사이즈를 초기화한다.
    # head와 tail 모두 0 인덱스로 설정한다.
    def __init__(self):
        self.__container = [None for _ in range(CQueue.MAXSIZE+1)]
        self.__head = 0
        self.__tail = 0

    # circular queue가 값이 비어있는지 확인
    def is_empty(self):
        if self.__head == self.__tail:
            return True
        return False

    # circular queue가 값으로 가득 채워있는지 확인
    def is_full(self):
        next = self.__step_forward(self.__tail)
        if next == self.__head:
            return True
        return False

    # tail = tail + 1 설정한 뒤, tail 인덱스에 data를 enqueue한다.
    def enqueue(self, data):
        if self.is_full():
            raise Exception("The queue is full")
        self.__tail = self.__step_forward(self.__tail)
        self.__container[self.__tail] = data

    # head = head + 1 설정한 뒤, head 인덱스의 값을 dequeue한다.
    def dequeue(self):
        if self.is_empty():
            raise Exception("The queue is empty")
        self.__head = self.__container[self.__head + 1]
        self.__head = self.__step_forward(self.__head)
        return self__head

    # head + 1 인덱스의 값을 반환한다.
    def peek(self):
        if self.is_empty():
            raise Exception("The queue is empty")
        return self.__container[self.__head + 1]

    # 편의 함수 (1씩 값을 증대시켜주는 함수)
    def __step_forward(self, x):
        x += 1
        # 인덱스 값이 배열 사이즈 + 1 보다 클 경우 0으로 설정
        if x >= CQueue.MAXSIZE+1:
            x = 0
        return x

    def __str__(self):
        return str(self.__container)

    
if __name__ =="__main__":
cq = CQueue()

for i in range(9+1):
    cq.enqueue(i + 1)
    print(f"enqueue: {i+1}")

for i in range(5+1):
    print("dequeue: ", cq.dequeue())


print("tail: ", cq._CQueue__tail)
print("head: ", cq._CQueue__head)
print("peek: ", cq.peek())
print("container: ", cq)
print("is full? ", cq.is_full())
print("is empty? ", cq.is_empty())
Posted  
tags:
  • { Python }
  • { DataStructure }
  • { Queue }