선형구조 큐(Queue) 기본 원리와 종류 (단순 큐, 순환 큐, 우선순위 큐)

선형구조 큐(Queue) 기본 원리와 종류 (단순 큐, 순환 큐, 우선순위 큐)

 

 

데이터 구조는 컴퓨터 과학에서 데이터를 효율적으로 관리하고 처리하는 기초를 형성합니다. 특히, 선형 구조에 속하는 큐는 데이터 처리와 관리에 있어서 필수적인 개념입니다. 본 글에서는 큐의 기본적인 개념에서부터 다양한 종류를 깊이 있게 탐구해보고자 합니다.

 

 

큐(Queue)에 대해

 

큐의 기본 구조와 종류

큐(Queue)는 선입선출(FIFO: First In, First Out)의 원칙에 따라 데이터를 관리하는 선형 데이터 구조입니다. 데이터가 들어온 순서대로 처리됩니다. 이 기본적인 큐 외에도, 큐는 여러 형태로 변형되어 특정 상황에서 보다 효율적으로 사용됩니다. 대표적인 큐의 종류로는 다음과 같은 것들이 있습니다.

 

• 단순 큐(Simple Queue): 가장 기본적인 큐로, 선입선출 원칙을 따릅니다.
• 순환 큐(Circular Queue): 큐의 끝과 시작이 연결된 형태로, 공간 활용도를 높일 수 있습니다.
• 우선순위 큐(Priority Queue): 각 요소가 우선순위를 가지고, 우선순위가 높은 요소부터 처리됩니다.
• 이중 종료 큐(Deque, Double-Ended Queue): 양쪽 끝에서 데이터의 입력과 출력이 모두 가능합니다.

 

 

큐의 작동 원리

https://ko.wikipedia.org/wiki/%ED%81%90_%28%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0%29

 

 

class Queue {
  constructor() {
    this.items = [];
  }
  
  enqueue(element) {
    this.items.push(element);
  }
  
  dequeue() {
    if(this.isEmpty())
      return "Underflow";
    return this.items.shift();
  }
  
  front() {
    if(this.isEmpty())
      return "No elements in Queue";
    return this.items[0];
  }
  
  isEmpty() {
    return this.items.length == 0;
  }
}

 

• enqueue: 큐의 끝에 항목을 추가합니다.
• dequeue: 큐의 앞에서 항목을 제거하고 반환합니다.
• front: 큐의 첫 번째 항목을 보여줍니다.
• isEmpty: 큐가 비어 있는지 확인합니다.

 

 

큐(Queue)의 대표적인 활용 사례

 

컴퓨터 과학의 원리가 현실 세계에 적용되는 사례 중 하나로, 큐의 개념을 활용한 멀티태스킹과 프로세스 스케줄링을 들 수 있습니다. 이는 운영 체제(OS)의 핵심 기능 중 하나로, 사용자가 여러 프로그램을 동시에 실행하고 있을 때 컴퓨터가 이를 효과적으로 처리할 수 있게 해줍니다.

 

 

멀티태스킹과 큐의 관계

멀티태스킹은 여러 프로세스 또는 작업을 동시에 실행하는 컴퓨터의 능력을 말합니다. 컴퓨터가 동시에 여러 작업을 처리하는 것처럼 보이지만, 실제로는 한 번에 하나의 작업만 처리할 수 있습니다. 이때 운영 체제는 작업 스케줄러를 사용하여 각 프로세스에 CPU 시간을 할당합니다. 이 과정에서 큐의 데이터 구조가 핵심적인 역할을 수행합니다.

 

 

프로세스 스케줄링과 큐의 활용

프로세스 스케줄링은 시스템에 존재하는 모든 프로세스에 대해 실행 순서를 결정하는 작업입니다. 운영 체제는 이를 위해 여러 종류의 큐를 활용합니다. 예를 들어, 준비 큐(ready queue)는 실행을 위해 CPU를 할당받기를 기다리는 프로세스들을 관리합니다. 입출력 작업을 대기하는 프로세스들은 별도의 입출력 대기 큐에 저장됩니다. 이러한 큐들을 통해 운영 체제는 프로세스들을 효율적으로 관리하고, 사용자에게 여러 작업을 동시에 처리하는 것처럼 보이게 만듭니다.

 

 

현실 세계의 응용

 

이 원리는 현실 세계의 다양한 시스템에도 적용됩니다. 예를 들어, 은행에서 고객의 대기 순서를 관리하거나, 고속도로 톨게이트에서 차량의 통행 순서를 조정하는 것 등이 큐의 원리를 활용한 사례입니다. 이처럼 큐는 단순한 데이터 구조를 넘어서, 우리 생활 속에서 효율성과 공정성을 보장하는 데 필수적인 역할을 합니다.

 

 

순환 큐(Cirular Queue) 이해와 활용

 

컴퓨터 과학에서의 큐(Queue)는 매우 중요한 자료 구조 중 하나입니다. 특히, 순환 큐(Circular Queue)는 그 특성상 일반 큐의 단점을 극복하고 효율성을 높인 형태로, 다양한 프로그래밍 상황에서 유용하게 활용될 수 있습니다. 

 

순환 큐(Circular Queue)란?

순환 큐는 시작점과 끝점이 연결된 원형 구조를 가진 큐입니다. 일반 큐와 달리, 순환 큐는 공간의 재활용이 가능하여, 큐의 용량을 효율적으로 사용할 수 있습니다.

 

 

작동 원리

https://daeguowl.tistory.com/112

 

순환 큐에서는 삽입과 삭제가 이루어질 때, 포인터가 큐의 끝에 도달하면 다시 시작점으로 돌아오는 구조를 가집니다. 이를 통해 메모리 공간을 절약하며, 데이터의 삽입과 삭제가 반복되어도 큐의 크기를 변경할 필요가 없습니다.

 

 

순환 큐의 구현

Python을 사용한 간단한 순환 큐 구현 예시입니다.

 

class CircularQueue:
    def __init__(self, size):
        self.size = size
        self.queue = [None] * size
        self.front = self.rear = -1

    def enqueue(self, item):
        if ((self.rear + 1) % self.size == self.front):
            print("The circular queue is full")
        elif (self.front == -1):
            self.front = 0
            self.rear = 0
            self.queue[self.rear] = item
        else:
            self.rear = (self.rear + 1) % self.size
            self.queue[self.rear] = item

    def dequeue(self):
        if (self.front == -1):
            print("The circular queue is empty")
        elif (self.front == self.rear):
            temp = self.queue[self.front]
            self.front = -1
            self.rear = -1
            return temp
        else:
            temp = self.queue[self.front]
            self.front = (self.front + 1) % self.size
            return temp

 

이 코드는 순환 큐의 기본적인 삽입(enqueue)과 삭제(dequeue) 기능을 구현한 것입니다. 이를 통해 순환 큐의 동작 원리를 보다 실제적으로 이해할 수 있습니다.

 

 

순환 큐의 활용

 

순환 큐는 버퍼(Buffer) 관리, 네트워킹에서의 패킷(Packet) 관리, 프로세스 스케줄링 등 다양한 분야에서 활용됩니다. 특히, 제한된 메모리 공간 내에서 데이터를 효율적으로 관리해야 하는 경우에 매우 유용합니다.

 

 

우선순위 큐(Priority Queue)의 이해와 활용

 

데이터 구조와 알고리즘은 프로그래밍의 핵심 요소 중 하나입니다. 특히, 우선순위 큐는 다양한 상황에서 유용하게 사용될 수 있는 중요한 자료 구조입니다. 

 

우선순위 큐란?

우선순위 큐(Priority Queue)는 각 요소가 우선순위와 연관되어 있으며, 우선순위가 높은 요소가 먼저 제공되는 자료 구조입니다. 이는 일반 큐와는 다르게, 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out) 원칙을 따르지 않습니다. 대신, 요소들은 우선순위에 따라 처리됩니다.

 

 

우선순위 결정 방식

https://suyeon96.tistory.com/m/31

 

우선순위를 결정하는 방식은 구현에 따라 다를 수 있습니다. 일반적으로는 숫자가 클수록 우선순위가 높다고 가정하지만, 경우에 따라 가장 낮은 값을 가진 요소를 가장 높은 우선순위로 설정할 수도 있습니다. 이는 우선순위 큐를 사용하는 애플리케이션의 요구 사항에 따라 달라집니다.

 

 

우선순위 큐의 구현

import heapq

# 우선순위 큐 구현
class PriorityQueue:
    def __init__(self):
        self.elements = []

    def push(self, item, priority):
        heapq.heappush(self.elements, (priority, item))

    def pop(self):
        return heapq.heappop(self.elements)[1]

# 사용 예시
pq = PriorityQueue()
pq.push("작업 A", 3)
pq.push("작업 B", 1)
pq.push("작업 C", 2)

print(pq.pop())  # 가장 우선순위가 높은 "작업 B" 출력

 

이 코드는 파이썬에서 제공하는 heapq 모듈을 사용하여 우선순위 큐를 간단히 구현한 예시입니다. 여기서는 숫자가 낮을수록 우선순위가 높다고 가정하였습니다.

 

 

우선순위 큐의 활용 예시

1. 운영 체제의 작업 스케줄링

운영 체제에서는 다양한 작업(프로세스)에 대해 우선순위를 할당하여, 우선순위가 높은 작업을 먼저 처리합니다. 이를 통해 시스템 자원을 효율적으로 관리하고 사용자에게 더 나은 서비스를 제공할 수 있습니다.

 

2. 네트워크 트래픽 관리

네트워크에서 데이터 패킷을 전송할 때, 중요도에 따라 패킷에 우선순위를 부여하고, 우선순위가 높은 패킷부터 전송합니다. 이를 통해 중요한 데이터의 전송 지연을 최소화할 수 있습니다.

 

---

 

끝으로

멀티태스킹과 프로세스 스케줄링은 큐의 개념을 실제로 적용하는 뛰어난 예시입니다. 이를 통해 우리는 데이터 구조가 단순한 이론에 머물지 않고, 실제 생활과 밀접하게 연결되어 있음을 알 수 있습니다. 컴퓨터 과학의 기본 개념이 어떻게 현실 세계의 복잡한 문제를 해결하는 데 기여하는지 이해하는 것은 매우 흥미롭고 유익한 경험이 될 것입니다.

 

▼ 자료구조에 관한 다른 글 ▼

 

많은 기업들이 자료구조와 알고리즘을 중시하는 이유