큐 Queue

: 데이터들이 일렬로 줄을 선 형태의 자료구조

• 특징
  • 선입선출 (First-In-First-Out)
  • 삭제가 이루어지는 front 부분과 삽입이 이루어지는 rear부분으로 구성

---

선형 큐 Linear Queue

Python에서의 큐

💡 deque로 구현

deque (double-ended queue) : 앞뒤에서 삽입, 삭제가 가능한 큐
→ stack, queue 등으로 사용 가능

from collections import deque

# 생성
q = deque()

# 삽입
q.append(1)

# 삭제
q.popleft()

💡 list로 구현

# 생성
q = []

# 삽입
q.append(1)

# 삭제
q.pop(0)

🔎 deque와 list 비교

• 큐 삭제

  • list.pop(0) 시간복잡도 O(n)
    → 삭제 요소 외 남은 요소들 복사
  • deque.popleft() 시간복잡도 O(1)
    → 링크드리스트 형태로, 연결 노드 인덱스만 갱신

• 스택 삭제

  • list.pop()와 deque.pop() 둘 다 시간복잡도 O(1)

• 특정 인덱스 접근

  • list[i] 시간복잡도 O(1)
  • deque[i] 시간복잡도 O(n)

스택으로 쓰일 경우, list
큐로 쓰일 경우, deque를 사용하는 것이 더 효율적

 

Java에서의 큐

💡 Queue 클래스

import java.util.Queue;

// 생성
Queue<Integer> q = new LinkedList<>();

// 삽입
q.offer(1);
q.add(10);

// 삭제 및 반환
q.poll();

// 전체 삭제
q.clear();

// 공백 확인
q.isEmpty();

// 크기
q.size();

💡 배열로 큐 구현

크기가 고정된 배열로 선형 큐 구현 시 문제점

삽입과 삭제를 반복하면, 배열 앞쪽에는 활용할 수 있는 공간이 있지만 포화상태로 인식
→ 인덱스를 순환시키는 원형 큐로 해결 가능

public class QueueArr {
	int size;
    int[] q;
	int front = -1;
    int rear = -1;
    
    
	// 생성 
	public void QueueArr(int size) {
    	this.size = size;
        q = new int[size];
    }
	
    // 공백
    public boolean isEmpty() {
    	return front == rear;
    }
    
    // 포화
    public boolean isFull() {
    	return rear == size - 1;
    }
    
	// 삽입 
    public void enQueue(int element) {
    	if(isFull()) {
        	System.out.println("Queue is full.");
        } else {
          rear += 1;
          q[rear] = element;
        }
    }
    
    // 삭제 및 반환
	public int deQueue() {
    	if(isEmpty()) {
        	System.out.println("Queue is empty.");
        	return -1;
        } else {
        	front += 1;
        	return q[front];
        }
    }
    
    // 검색
    public int Qpeek() {
    	if(isEmpty()) {
        	System.out.println("Queue is empty.");
        } else {
        	return q[front + 1];
        }
    }
}

 

 

---

원형 큐 Circular Queue

: 큐의 첫 요소와 마지막 요소가 연결된 형태

💡 배열로 원형 큐 구현

선형 큐와의 차이점

• 초기상태 & 공백상태 : front = rear = 0
• 포화상태 : rear의 다음 칸 = front (front 칸은 항상 공백)
• front와 rear 계산 시 배열 크기로의 나머지 연산이 추가됨

public class CircularQueue {
	int size;
    int[] q;
	int front = 0;
    int rear = 0;
    
    
	// 생성 
	public void CircularQueue(int size) {
    	this.size = size + 1;
        q = new int[size];
    }
	
    // 공백
    public boolean isEmpty() {
    	return front == rear;
    }
    
    // 포화
    public boolean isFull() {
    	return front == (rear + 1) % size;
    }
    
	// 삽입 
    public void enQueue(int element) {
    	if(isFull()) {
        	System.out.println("Queue is full.");
        } else {
          rear = (rear + 1) % size;
          q[rear] = element;
        }
    }
    
    // 삭제 및 반환
	public int deQueue() {
    	if(isEmpty()) {
        	System.out.println("Queue is empty.");
        	return -1;
        } else {
        	front = (front + 1) % size;
        	return q[front];
        }
    }
    
    // 검색
    public int Qpeek() {
    	if(isEmpty()) {
        	System.out.println("Queue is empty.");
        } else {
        	return q[(front + 1) % size];
        }
    }
}

 

---

우선순위 큐 Priority Queue

: 우선순위에 따라 정렬되는 자료구조

• 특징
  • 들어간 순서와 상관없이, 우선순위가 높은 데이터가 먼저 나옴
  • 작업 스케줄링, 네트워크 관리 등에 적용

Java에서의 우선순위 큐

• 배열로 구현 → 삽입 삭제 연산마다 매번 요소의 재배치 → 메모리 낭비

💡 PriorityQueue 클래스

• 값을 비교해야하므로 null을 허용하지 않음
• 이진트리 힙 구조 → 삽입, 삭제 연산 시간복잡도O(nlogn)

import java.util.PriorityQueue;
import java.util.Collections;

//낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> pqLowest = new PriorityQueue<>();

//높은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> pqHighest = new PriorityQueue<>(Collections.reverseOrder());

// 삽입
pqLowest.add(1);
pqLowest.offer(10);

// 삭제
pqLowest.poll();
pqLowest.remove();

// 우선순위가 가장 높은 값 조회
pqLowest.peek();

Python에서의 우선순위 큐

💡 queue 라이브러리의 PriorityQueue

import queue

# 생성
pq = queue.PriorityQueue()

# 삽입 (값, 우선순위)
pq.put((1, 0))
pq.put((10, 1))

# 삭제 및 반환
pq.get()