[Section 3] 큐(Queue) 구현 알고리즘 _ 원형 배열(Circular Array)

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

원형 배열로 큐는 고정된 사이즈라는 단점을 가지고 있다. 하지만, 그 구현이 매우 단순하고 이해하기 쉽다는 장점을 가지고 있다. 가장 쉬운 큐를 구현함으로써 원형 배열 알고리즘을 이해해보자.

1. 원형 배열 큐의 복잡도 분석

큐의 핵심은 인큐(EnQueue)와 디큐(DeQueue)이다. 그리고 이 자료구조의 공간 복잡도가 O(n)이지만, 자료가 적을 때 적절히 사용해주면 아주 효과적이다. 왜냐하면, 자료구조의 사이즈 확인 그리고 인큐와 디큐 과정이 모두 O(1)의 시간 복잡도를 가지고 있기 때문이다. 원형 배열 큐의 구성은 다음과 같다.

원형 배열 큐의 개요도

2. 원형 배열 큐의 구현

원형 배열 큐의 경우, 사이즈가 고정적이므로 다음의 예시 코드와 같이 자료구조의 사이즈를 선언해야 한다.

 

예시 코드:

class QueueA:
    def __init__(self,limit=1):
        self.Q=[]
        self.limit=limit
        self.front=None
        self.rear=None
        self.length=0
    def isEmpty(self):
        return self.length <=0
    def enQ(self,data):
        if self.length>=self.limit:
            print("Queue Overflow!")
            return
        else:
            self.Q.append(data)
        if self.front is None:
            self.front = self.rear = 0
        else:
            self.rear = self.length
        self.length +=1
        print("Queue Sequence:", self.Q)
    def deQ(self):
        if self.length <=0:
            print("Queue Underflowe!")
            return
        else:
            self.Q.pop(0)
            self.length -=1
            if self.length ==0:
                self.front=self.rear=None
            else:
                self.rear=self.length-1
                print("Queue Sequence:", self.Q)

다음의 프로그램 동작 프로세스를 이해하자.

 

구현한 큐의 동작 프로세스