읽고 나면 진짜 쉬워지는 자료 구조 - 4. 스택과 큐
데이터가 저장된 순서에 따라 데이터를 읽을 수 있는 자료 구조
🔖 4.1 스택
배열로 스택 구현
데이터를 추가할 때 스택을 확장할 수는 있지만, 배열의 크기를 확장해야 하는 경우 추가 비용이 발생할 수 있다.
자바스크립트 배열은 동적 크기를 가지므로
push()연산은 배열의 크기가 충분하면 빠르게 수행되지만, 배열 크기를 확장해야 할 때는 메모리 재할당 비용이 발생한다.스택에서 항목을
pop()할 때는push()보다 내부 동작이 간단하다.push()는 배열의 끝에 데이터를 삽입하고, 배열 크기를 고려하여 메모리를 확장해야 할 수도 있지만,pop()은 배열의 마지막 요소를 제거하는 단순한 작업이다.
const stack = [];
stack.push(10); // 추가 (push)
stack.push(20);
console.log(stack); // [10, 20]
stack.pop(); // 제거 (pop)
console.log(stack); // [10]연결 리스트로 스택 구현
연결 리스트를 사용하면 크기에 제한이 없고, 메모리 재할당을 걱정할 필요가 없다.
스택에 항목을
push()할 때는 연결 리스트의 앞쪽에 새로운 노드를 추가한다.새로운 노드를 생성하고, 새 노드의
next포인터와 스택의head포인터를 갱신해 새 노드를 리스트 맨 앞에 삽입한다.pop()할 때는head노드의 값을 반환하고,head포인터를 다음 노드로 이동시킨다.
function createNode(value) {
return { value, next: null };
}
function createStack() {
let head = null;
return {
push(value) {
const newNode = createNode(value);
newNode.next = head;
head = newNode;
},
pop() {
if (!head) return null;
const poppedValue = head.value;
head = head.next;
return poppedValue;
},
peek() {
return head ? head.value : null;
},
};
}
const stack = createStack();
stack.push(10);
stack.push(20);
console.log(stack.peek()); // 20
console.log(stack.pop()); // 20
console.log(stack.pop()); // 10
🔖 4.2 큐
배열로 큐 구현
큐는 배열의
push()와shift()를 사용해 구현할 수 있다.그러나
shift()는 배열의 모든 요소를 앞으로 이동시키므로 비용이 크다.이러한 단점을 해결하기 위해 순환 큐를 사용하면 배열의 끝에서 맨 앞으로 이동하는 추가 작업 없이 효율적으로 작동할 수 있다.
const queue = [];
queue.push(10); // 추가 (enqueue)
queue.push(20);
console.log(queue); // [10, 20]
queue.shift(); // 제거 (dequeue)
console.log(queue); // [20]연결 리스트로 큐 구현
연결 리스트를 사용하면 큐의 크기를 동적으로 관리할 수 있다.
리스트의 머리(head)를 가리키는 포인터와 꼬리(tail)를 가리키는 포인터를 유지한다.
enqueue()는 꼬리에 새로운 노드를 추가하고,dequeue()는 머리에서 노드를 제거한다.큐 크기와 상관없이 연산은 항상 일정한 시간(O(1)) 내에 수행된다.
function createQueue() {
let head = null;
let tail = null;
return {
enqueue(value) {
const newNode = createNode(value);
if (!tail) {
head = tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
},
dequeue() {
if (!head) return null;
const dequeuedValue = head.value;
head = head.next;
if (!head) tail = null;
return dequeuedValue;
},
peek() {
return head ? head.value : null;
},
};
}
const queue = createQueue();
queue.enqueue(10);
queue.enqueue(20);
console.log(queue.peek()); // 10
console.log(queue.dequeue()); // 10
console.log(queue.dequeue()); // 20
🔖 4.3 순서의 중요성
깊이 우선 탐색 (DFS)
더 깊이 탐색하면서 막다른 골목에 도달할 때까지 한 가지 경로를 진행하는 방식
막다른 골목에 도달하면 마지막으로 방문했던 분기로 돌아가 다음 루트를 확인한다.
스택을 사용해 앞으로 탐색할 목록을 유지하며, 가장 최근에 삽입한 가능성을 가장 먼저 탐색한다.
function dfs(graph, start) {
const visited = new Set();
const stack = [start];
while (stack.length > 0) {
const node = stack.pop();
if (!visited.has(node)) {
visited.add(node);
console.log(node);
for (const neighbor of graph[node]) {
stack.push(neighbor);
}
}
}
}
const graph = {
A: ['B', 'C'],
B: ['D', 'E'],
C: ['F'],
D: [],
E: [],
F: [],
};
dfs(graph, 'A'); // A, C, F, B, E, D너비 우선 탐색 (BFS)
깊이 우선 탐색과 유사한 방식으로 탐색하나, 큐를 사용해 미래의 가능성을 저장한다.
각 단계에서 탐색은 가장 오래 기다린 가능성을 탐색하며, 더 깊은 단계를 탐색하기 전에 같은 깊이의 여러 다른 방향으로 뻗어 나간다.
function bfs(graph, start) {
const visited = new Set();
const queue = [start];
while (queue.length > 0) {
const node = queue.shift();
if (!visited.has(node)) {
visited.add(node);
console.log(node);
for (const neighbor of graph[node]) {
queue.push(neighbor);
}
}
}
}
bfs(graph, 'A'); // A, B, C, D, E, F정리
DFS와 BFS는 모두 한 번에 하나의 가능성을 탐색한다는 점에서 동일한 속도로 작동한다.
DFS는 '스페셜리스트'처럼 특정 경로를 깊이 탐색하고, BFS는 '제너럴리스트'처럼 여러 경로를 얕게 탐색한다.
Last updated