[Data Structure] 큐(Queue)

큐

• 선형 자료 구조
• 선입선출(First In First Out) : 가장 먼저 저장된 데이터가 가장 먼저 나가는 것
• 데이터의 삽입이 뒤쪽에서, 삭제가 앞쪽에서 일어남

큐의 기본 연산

• 데이터 추가(Enqueue)
  • 큐에 데이터 추가
    

• 데이터 꺼내기(Dequeue)
  • 큐에서 데이터 꺼내기
    

큐의 시간 복잡도

• 원소의 추가/제거 : O(1)
• 맨 앞 원소 확인 : O(1)
  • 맨 앞 이외의 원소 확인이 원칙적으로는 불가능하다

큐의 활용

• BFS
• 우선순위 큐(OS 스케줄링, 다익스트라)

C++ STL vs Java

• C++에서 큐 선언

#include <queue>

queue<T> qu;

• Java에서 큐 선언

import java.util.LinkedList;
import java.util.Queue;

Queue queue = new LinkedList();

• 메소드 비교

	C++	Java
삽입	push(ITEM)	add(ITEM)
삭제	pop()	poll()
맨 앞 원소 접근	front()	peek()
맨 뒤 원소 접근	back()	-
크기	size()	size()
비어있는지 여부	empty()	isEmpty()
초기화	-	clear()
원소포함여부	-	contains(ITEM)