[Data Structure] 큐

양영준·2026년 4월 1일

data structure

자료구조

목록 보기

8/8

📌 큐

스택과는 반대되는 개념을 가진 자료구조로, 선입선출(FIFO, First In, First Out) 원칙에 따라 데이터를 저장하고 접근하는 선형 자료구조이다.

💡 용어

enQueue : 큐에 데이터를 삽입하는 행위
deQueue : 큐에 데이터를 삭제하는 행위
front : 현재 큐에 가장 처음 삽입한 데이터를 가리키는 포인터
rear : 현재 큐에 가장 마지막에 삽입한 데이터를 가리키는 포인터

💡 시간복잡도

읽기(read) : O(n)
탐색(search) : O(n)
삽입(insert) : O(1)
삭제(delete) : O(1)

💡 종류

1. 선형 큐

가장 기본적인 형태의 큐로, 데이터가 일직선의 형태로 연결되어 있는 큐이다.
선형 큐를 배열로 구현하였을 때, enQueue와 deQueue 동작이 여러번 발생하는 경우, 큐가 비어 있음에도 데이터를 삽입하지 못하는 경우가 발생한다.
이러한 문제가 발생하는 원인을 알기 위해서는 deQueue 동작을 자세히 알 필요가 있다.

deQueue 과정을 수행하면, front가 가리키고 있는 값이 큐에서 빠져나가고 front는 그 다음 데이터를 가리키게 된다.

이 때, 원래 front가 가리키던 자리는 더 이상 쓸 수 없는 상태가 되고, 큐가 수용할 수 있는 데이터의 개수가 줄어들게 된다.

이러한 과정이 반복되다보면 결국 front가 미리 할당한 큐의 메모리 넘어를 가리키게 될 것이고, 이 경우가 큐가 비어있더라도 큐에 데이터를 삽입하지 못하는 경우가 된다.

2. 원형 큐

원형 큐는 선형 큐의 문제점을 보완하기 위해 만들어졌으며 큐를 원형으로 이어붙여 순환하는 구조를 가지는 큐이다.
front가 큐의 끝 부분을 가리키고 있을 때 deQueue 동작이 수행하게 되면 front는 순환하여 다시 첫 부분을 가리키게 된다.
이를 통해 front가 미리 할당된 메모리의 범위 밖을 벗어나지 않으며, deQueue가 반복될수록 큐가 수용할 수 있는 데이터 갯수가 줄어드는 문제점 또한 해결할 수 있게 되었다.

💡 장 / 단점

장점

구현이 간단하고 데이터를 관리하기 쉽다.
데이터가 들어온 순서대로 처리되므로 데이터 처리의 공정성을 보장한다.

단점

중간에 있는 요소에 직접적으로 접근할 수 없다.

💡 스택 VS 큐

구분	스택(Stack)	큐(Queue)
방식	LIFO(Last In, First Out)	FIFO(First In, First Out)
삽입 / 삭제 위치	한쪽 끝(top)에서만 가능	양쪽 끝 (삽입은 rear, 삭제는 front)
주요 작업	push / pop	enQueue / deQueue
주요 활용	함수 호출, 뒤로가기(undo), DFS(깊이 우선 탐색) 등	프로세스 관리, BFS(너비 우선 탐색), 캐시 등