스택과 큐
[2023.06.02 ~ 2023.06.08] 동안 공부한 스택이다.
해당 포스트는 누구나 자료구조와 알고리즘 개정 2판을 참고하여 작성되었다.
📌 스택(Stack)과 큐(Queue)
스택(Stack)과 큐(Queue)
스택과 큐는 임시데이터를 다룰 때 사용된다. 임시데이터란 처리 후에는 필요없는 정보이므로 다 쓴 후에 버려도 상관없는 정보를 의미한다.
실제로 대부분의 프로그래밍 언어에는 스택과 큐가 내장 데이터 타입이나 클래스로 포함되어 있지 않다. 스택과 큐를 규현하기 위해서는 실제로 데이터를 저장할 내장 데이터 구조 중 하나를 골라야 한다. 즉, 스택과 큐는 추상 데이터 타입이다. ‼
스택과 큐는 오늘 하루 퇴근하면 필요없어지는 오늘의 식당 총 주문 내역서 같은 임시 데이터를 다루는 데 적합하며, 특히 순서를 매우 중요시 여긴다.
스택 (Stack)
- 데이터는 스택 끝에만 삽입 가능
- 데이터는 스택 끝에서만 삭제 (pop)
- 스택의 마지막 원소만 읽기 가능
-> 스택은 예를 들면 수업시간에 지각한 사람들이 늦게 와서 몰래 먼저 나가는 상황과 비슷하다. -> Last in, First out (LIFO) 🙆♀️
스택은 어떠한 상황에서 유용할까?
스택은 상황을 다룰때에만 쓰이고 처리가 끝난 후에는 필요가 없는 데이터, 즉 임시데이터를 다룰때 유용하다. 예를 들면, 자바스크립트 린터(linter), 프로그래머가 작성한 자바스크립트가 문법적으로 유용한지 검사하는 린팅 알고리즘에서 유용하다.
린팅 알고리즘에서 괄호가 올바르게 표현되어 있는지만 체크하는 로직을 활용해 배열로 스택을 구현하여 코드를 짜보았다.
function solution(arr) {
let answer = "YES";
let stack = [];
for (let x of arr) {
if (["(", "{", "["].includes(x)) {
stack.push(x);
} else if ([")", "}", "]"].includes(x)) {
if (stack.pop() == undefined) {
return "NO";
}
}
}
if (stack.length > 0) return "NO";
return answer;
}
let arr = "(var x={y:[1,2,3]}))";
console.log(solution(arr));
// 답: 'NO'
배열과 다른 스택의 이점
린팅 알고리즘에서도 배열을 활용해서 스택을 구현한 것을 보면 스택은 제약을 가진 배열이라고 볼 수 있다. 그러면 배열과 다르게 스택이 주는 이점은 무엇일까?
- 스택은 끝에서만 삭제가 가능하므로 린팅 알고리즘과 같은 위에서 항목을 제거해야만 하는 경우에 적합하다.
- LIFO 일때, 유용하고 새로운 해결책을 제시한다.
큐 (Queue)
큐는 식당 대기줄처럼 먼저 선 사람이 먼저 식당에 들어갈 수 있는 First in First out 이라고 할 수 있다.
- 데이터의 끝에만 삽입 가능
- 데이터의 앞에서만 삭제
- 데이터의 앞에 있는 원소만 읽을 수 있음
큐는 어떤 상황에서 효율적일까?
큐는 들어온 순서대로 무언가 작업을 해야할때 유용하다. 예를 들면, 시간 순으로 들어온 프린트 출력물을 먼저 들어온 순서대로 뽑으려고 할때의 상황을 들 수 있다.
큐는 비동기 요청건을 순서대로 요청을 처리하도록 로직을 짜는데 유용하게 쓰인다.
