[알고리즘] 큐 (Queue)

이전 글 : )

[알고리즘] 스택 (Stack)

 

---

 

 큐 Queue 

큐 queue란 자료 공간에 먼저 들어온 자료가 먼저 처리하는 자료구조를 말합니다.

먼저 들어온 자료를 먼저 처리한다, 즉 선입선출이라고 하며 FIFO, First-In-First-Out라고도 합니다.

일상생활에서 보면 맛집에서 번호표를 뽑고 번호표 순서대로 먼저 온 손님이 먼저 자리에 앉은 순과 같습니다.

 

큐는 스택과 마찬가지로 삽입과 삭제의 위치와 방법이 제한되어 있는 자료구조이지만

스택과 다르게 한쪽 끝에서는 삽입 작업만 이루어지고 반대쪽 끝에서는 삭제 작업이 이루어집니다.

한쪽 끝을 Front로 정하여 삭제 연산만 수행하도록 하고

다른 쪽 끝을 Back 또는 Rear로 정하여 삽입 연산만 수행하도록 제한합니다.

입력 동작은  Enqueue, 출력 동작은 Dequeue라고 합니다.

 

 

 종류 

큐의 종류에는 선형 큐 linear queue , 원형 큐 circular queue 그리고 우선순위 큐 priority queue가 있습니다.

 

선형 큐 linear queue는 위에서 설명한 기본적인 큐의 형태로써 막대 모양으로 된 큐입니다.

배열 혹은 리스트로 구현되어 크기가 제한되어있으며 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있습니다.

이러한 단점으로 많은 수의 Enqueue작업 및 Dequeue작업이 있는 경우 어느 시점에서 큐가 비어있어도 자료를 삽입하지 못하는 경우가 발생합니다.

선형 큐

이러한 선형 큐의 단점을 보완한 구조가 원형 큐 circular queue입니다.

원형 큐 혹은 환형 큐라고 하며, 이는 선형의 배열 형태의 큐를 원형으로 구조화하여 처음과 끝을 연결한 형태입니다.

다음에

원형 큐, www.geeksforgeeks.org/circular-queue-set-1-introduction-array-implementation/

우선운위 큐 priority queue는 데이터마다 우선순위를 넣어서 우선순위가 높은 순으로 데이터를 추출합니다.

즉 들어가는 순서에 관계없이 큐에서 dequeue 될 때, 우선순위에 맞게 나갑니다.

완전 이진 트리의 구조를 이용하여 트리의 균형을 맞추어 형태를 유지하는 것이 특징입니다.

모든 부모와 자식 간의 비교가 이루어지는 힙(Heap)을 이용하여 구현합니다.

[알고리즘] 힙 (Heap)

 

우선순위 큐, 트리구조

 

 구현 

python의 리스트를 이용해 선형 큐를 구현해보았습니다.

큐의 동작 원리를 알기 위해 클래스로 작성해보겠습니다.

python에서는 기본 제공 모듈로 큐가 존재하기에 import Queue를 하면 아래의 구현 과정 없이 사용할 수 있습니다.

class Queue:

    def __init__(self) :
 
        self.myQueue = []

큐 myQueue를 생성합니다.

    def push(self, n) :

        self.myQueue.append(n)

push()를 통해 큐에 요소를 삽입합니다.

    def pop(self) :

        if self.empty() ==1:
            return
        del self.myQueue[0]

 

pop()을 통해 큐에서 가장 앞에 있는 정수를 제거합니다. 만약 큐에 값이 없을 경우에는 아무 일도 하지 않습니다. 

    def size(self) :

        return len(self.myQueue)

큐의 size를 return 합니다.

   def empty(self) :

        if self.size() == 0:
            return 1
        else :
            return 0

큐가 비어있다면 1, 아니면 0을 return 합니다.

    def front(self) :

        if self.empty() == 1:
            return -1
        
        return self.myQueue[0]

큐의 가장 앞에 있는 정수를 return 합니다. 만약 queue에 들어있는 값이 없을 경우에는 -1을 return 합니다.

    def back(self) :

        if self.empty() == 1:
            return -1
        
        return self.myQueue[-1]

큐의 가장 뒤에 있는 정수를 return 합니다. 만약 큐에 들어있는 값이 없을 경우에는 -1을 return 합니다.

 

---

 

 

[알고리즘] 힙 (Heap)