[Python] Queue1 (선형큐, 원형큐)

• 큐(Queue)의 특성
  • 삽입과 삭제의 위치가 제한적인 자료구조
  • 선입선출구조(FIFO : First In First Out)
• 큐의 주요 연산
  • enQueue(item) : 큐의 뒤쪽(rear 다음)에 원소를 삽입하는 연산
  • deQueue() : 큐의 앞쪽(front)에서 원소를 삭제하고 반환하는 연산
  • createQueue() : 공백 상태의 큐를 생성하는 연산
  • isEmpty() : 큐가 공백상태인지 확인하는 연산
  • isFull() : 큐가 포화상태인지 확인하는 연산
  • Qpeek() : 큐의 앞쪽(front)에서 원소를 삭제 없이 반환하는 연산

❗ append(),pop() 이용 시 느려짐

---

 

• 선형큐
  • 1차원 배열을 이용한 큐
  • 큐의 크기 = 배열의 크기
  • front : 저장된 첫 번째 원소의 인덱스
  • rear : 저장된 마지막 원소의 인덱스
  • 초기 상태 : front = rear = -1
  • 공백 상태 : front == rear
  • 포화 상태 : rear == n-1 (n : 배열의 크기)
• enQueue(item)
  • 마지막 원소 뒤에 새로운 원소를 삽입
  • rear값을 하나 증가시켜 그 인덱스에 해당하는 자리에 item 저장
• deQueue()
  • 가장 앞에 있는 원소를 삭제
  • front값을 하나 증가시켜 남아있게 될 첫 번째 원소 이동
  • 새로운 첫번째 원소를 리턴 함으로써 삭제와 동일한 기능함
• Qpeek()
  • 가장 앞에 있는 원소를 검색하여 반환하는 연산
  • 현재 front의 한자리 뒤에 있는 원소, 즉 큐의 첫 번째에 있는 원소를 반환

class MyQueue:
    def __init__(self):
        self.front = self.rear = -1
        self.queue = [0] * 5
    def enqueue(self,data):
        # 제일 뒤에 삽입
        if self.is_full():
            print('큐가 다 찼습니다.')
        else:
            self.rear += 1
            self.queue[self.rear] = data

    def dequeue(self):
        # 현재 가장 앞에 있는 요소를 반환하고 (삭제)
        if self.is_empty():
            print('큐가 비었습니다.')
        else:
            self.front += 1
            return self.queue[self.front]

    def is_full(self):
        if self.rear == len(self.queue)-1:
            return True
        else:
            return False

    def is_empty(self):
        if self.front == self.rear:
            return True
        else:
            return False

queue = MyQueue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
queue.enqueue(5) # 가득 참

queue.enqueue(6) # 못 들어감

print(queue.dequeue())

 

코드실행결과

• 선형 큐 이용 시의 문제점
  • 배열의 앞부분에 활용할 수 있는 공간이 있음에도 불구하고, rear = n-1 인 상태 즉, 포화상태 더 이상 삽입을 수행하지 않게 됨
• 해결법 1
  • 매 연산이 이루어질 때마다 저장된 원소들을 배열의 앞부분으로 모두 이동
  • 원소 이동에 많은 시간 소요 -> 큐의 효율성 급하락
• 해결법 2
  • 1차원 배열을 사용하되, 논리적으로는 배열의 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정하고 사용

---

• 원형 큐
  • 초기 공백 상태 : front = rear = 0
  • Index의 순환
    • front와 rear의 위치가 마지막 인덱스를 가리킨 후, 그다음에는 논리적 순환을 이루어 처음 인덱스로 이동
    • 이를 위해 나머지 연산자 mod 사용
  • front : 공백 상태와 포화 상태 구분을 쉽게 하기 위해 front가 있는 자리는 항상 비워 둠
  • 공백상태 : front = rear
  • 포화상태 : 삽입할 rear의 다음 위치 == 현재 front

class CircleQueue:
    def __init__(self):
        self.front = self.rear = 0
        self.queue = [0] * 5
    def enqueue(self,data):
        # 제일 뒤에 삽입
        if self.is_full():
            print('큐가 다 찼습니다.')
        else:
            self.rear  = (self.rear + 1) % len(self.queue)
            self.queue[self.rear] = data

    def dequeue(self):
        # 현재 가장 앞에 있는 요소를 반환하고 (삭제)
        if self.is_empty():
            print('큐가 비었습니다.')
        else:
            self.front = (self.front + 1) % len(self.queue)
            return self.queue[self.front]

    def is_full(self):
        if (self.rear + 1) % len(self.queue) == self.front:
            return True
        else:
            return False

    def is_empty(self):
        if self.front == self.rear:
            return True
        else:
            return False

코드실행결과