- 큐는 First In First Out입니다.
👉 먼저 들어온 데이터가 가장 먼저 나가는 구조죠. (반면 스택은 Last In First Out)
즉, 순서대로 무언가를 처리할 때 쓰이는 자료구조입니다.
🎯 큐를 활용하는 분야
- 작업 대기열: 네트워크 통신할 때 다수의 클라이언트가 서버에 작업을 요청하면 서버는 들어온 순서대로 작업을 처리해요.
- 이벤트 처리: 어떤 애플리케이션이나 시스템에서 사용자의 이벤트. (ex: 키보드 입력이나 마우스의 움직임)
📐 큐의 ADT (Abstract Data Type)
🔧 연산
| 연산 |
설명 |
시간 복잡도 |
isFull() |
큐가 꽉찼는지 확인 |
O(1) |
isEmpty() |
큐가 비어있는지 확인 |
O(1) |
enqueue(item) |
isFull() false면, 아이템 푸시 |
O(1) |
dequeue() |
isEmpty()가 false면, 제일 앞에 있는 값 팝하고 반환 |
O(1) |
📊 상태
| 상태 |
설명 |
front |
가장 최근에 꺼낸 위치 |
rear |
가장 최근에 삽입한 위치 |
data[maxsize] |
큐의 데이터를 관리하는 배열 (크기: maxsize) |
⚡ JS로 큐 만들기
- JS는 기본적으로 큐를 제공하지 않아요.
👉 shift()를 흉내낼 수 있지만 O(n)이라 실제 큐의 성능을 기대할 수 없어요.
그래서 배열이나 연결 리스트로 직접 구현하는 게 좋아요.
1️⃣ shift()로 흉내내기
shift()는 배열의 첫번째 요소를 제거 후, 나머지 요소들을 앞으로 당겨야 하기 때문에 비효율적이에요. => O(n)
2️⃣ 배열로 직접 구현하기
- 배열은 단순하지만
front가 앞으로 이동하면서 dequeue한 공간이 낭비되는 단점이 있어요.
class Queue {
constructor() {
this.front = 0;
this.rear = 0;
this.maxSize = 1001; // maxsize를 임의로 1001로 두었다.
this.data = Array(this.maxSize).fill(null);
}
enqueue(item) {
if (isFull()) {
}
this.data.push(item);
this.rear++;
}
dequeue() {
if (isEmpty()) {
return null;
}
return this.data[this.front++];
}
isFull() {
return this.rear === this.maxSize - 1;
}
isEmpty() {
return this.front === this.rear;
}
}
3️⃣ 연결 리스트로 직접 구현하기
- 연결 리스트는 동적 크기 조정이 가능하고, 사용하지 않는 메모리는 해제할 수 있어서 메모리 사용 측면에서 더 효율적이다.
class Node {
constructor(item) {
this.data = item;
this.next = null;
}
}
class Queue {
constructor() {
this.front = null;
this.rear = null;
this.size = 0; // 노드 수
}
enqueue(item) {
const newNode = new Node(item);
if (this.isEmpty()) {
this.front = newNode;
this.rear = newNode;
} else {
this.rear.next = newNode;
this.rear = newNode;
}
this.size++;
}
dequeue() {
if (this.isEmpty()) {
return null;
}
const removedNode = this.front;
this.front = this.front.next;
if (this.front === null) {
this.rear = null;
}
this.size--;
return removedNode.data;
}
isEmpty() {
return this.size === 0;
}
}
🧩 큐 관련 코테 문제
🎮 🃏 [프로그래머스/159994] 카드 뭉치
- 문제 요약:
- 문자열로 이루어진 배열
cards1, cards2와 원하는 단어 배열 goal이 매개변수로 주어진다.
- 각 카드 배열의 앞에서부터 순차적으로만 뽑을 수 있다.
goal과 문자열을 만들 수 있다면 "Yes"를, 만들 수 없다면 "No"를 반환한다.
- 문제의 핵심은 순차적으로 큐의 개념이 필요해요. for문으로
card1과 card2의 첫 번째 카드가 타겟 문자열과 같으면 해당 큐를 dequeue하면서 goal과 동일한 문자열이 될 수 있는지 확인합니다.
- 여기서는 이미 배열이 주어졌기 때문에 주어진 배열을 큐처럼 사용해요. 또한
shift()은 O(n)이므로 인덱스를 증가시키는 방식으로 dequeue를 대체했어요. ( -> O(1))
function solution(cards1, cards2, goal) {
let j = 0,
k = 0;
for (let i = 0; i < goal.length; i++) {
if (cards1[j] === goal[i]) {
j++;
} else if (cards2[k] === goal[i]) {
k++;
} else {
return "No";
}
}
return "Yes";
}
- 최단 거리를 구하는 BFS 문제에서도 큐가 이용돼요.
- 문제 요약:
1. n x m 크기의 게임 맵(`maps`)이 주어지고, `0`은 벽, `1`은 길이다.
2. 캐릭터는 시작엄 **(1,1)**에서 출발하여 도착 지점까지 지나가는 칸의 **최솟값**을 반환한다.
3. 도착 지점에 도달 불가능하면 -1를 반환한다.
- 왜 큐를 사용할까?:
- BFS는 항상 가까운 칸부터 차례대로 탐색해요. 따라서 먼저 들어온 좌표를 먼저 꺼낼 수 있는 자료구조, 즉 큐가 필요합니다. 따라서 도착 지점을 처음 만나는 순간이 곧 최단 거리가 돼요.
function solution(maps) {
const dirs = [
[1, 0],
[-1, 0],
[0, 1],
[0, -1],
];
const row = maps.length;
const col = maps[0].length;
const visited = Array(row)
.fill(0)
.map((e) => Array(col).fill(false));
function canGo(r, c) {
if (r < 0 || c < 0 || r >= row || c >= col) return false;
if (maps[r][c] === 0 || visited[r][c]) return false;
return true;
}
function bfs(r, c) {
const q = [[r, c, 1]];
visited[r][c] = true;
while (q.length) {
let [r, c, len] = q.shift();
if (r === row - 1 && c === col - 1) return len;
for (const [dr, dc] of dirs) {
let curR = r + dr;
let curC = c + dc;
if (canGo(curR, curC)) {
visited[curR][curC] = true;
q.push([curR, curC, len + 1]);
}
}
}
return -1;
}
return bfs(0, 0);
}
🔄 원형 큐 & ⭐ 우선순위 큐
- 원형 큐: 선형 큐의 메모리 낭비 문제를 해결했어요.
front와 rear가 순회하기 때문에 비어진 공간을 재사용할 수 있어요.
- 하지만 코딩 테스트에서는 js에서 제공하는 배열로도 충분히 커버가 가능하기 때문에 원형 큐를 사용할 필요는 없다고 한다.
- 우선 순위 큐: 순서가 아니라 우선순위가 높으면 먼저 처리되는 구조로, 선형 큐와 다르게
heap으로 구현해요.
📚 참고 자료
