한동안 스택과 큐를 직접 사용할 일이 있었다. 낯선 경험 이였는데, 이상하다는 생각이 들었다. 스택과 큐는 자료구조의 가장 기본이다. 하지만 실제 사용해보니 낯선 경험 이라니.
FIFO(First In First Out) 혹은 LIFO(Last In First Out)은 나를 구원해주지 않았다. 큐는 왠지 쓰기 어려웠으며, 스택은 어째서인지 내 마음대로 동작하지 않았다.
이 글은 자료구조를 언제 사용해야 할까? 혹은 어떻게 사용해야 할까? 에 대한 고민에 대한 답이다.
Stack과 단조(Monotone)
스택에는 모노톤 스택(Monotone stack)이라고 불리우는 종류의 스택이 있다. 정의는 다음과 같다.
A monotonic stack is a stack whose elements are monotonically increasing or descreasing.
모노톤 스택은 단조롭게 증가하거나 감소하는 스택이다.
https://liuzhenglaichn.gitbook.io/algorithm/monotonic-stack
단조롭게 증감한다(monotonically increasing or descreasing)는 다음과 같이 설명되고 있다.
어떤 수열이나 함수가 있을 때, 해당 수열이나 함수가 정의된 구간에서 감소하지 않는 경우를 단조증가, 증가하지 않는 경우를 단조감소 함수라고 한다.
위 그림에서 오른쪽 그래프의 경우 중간에 감소하는 구간이 존재하므로 해당 그래프는 단조증가 함수가 아니나, 왼쪽의 그래프의 경우 감소하는 구간이 존재하지 않으므로 단조증가 함수라고 할 수 있다. 결국 감소하는 구간이 없는 경우란 값이 일정하거나 증가하는 구간밖에 없는 경우가 된다. 이 단조증가에서 모든 구간에서 항상 수치가 증가하는 경우를 ‘강한 단조증가’라고 하기도 한다.
즉 쉽게 설명하면 스택 내에 있는 모든 값은 오름차순 혹은 내림차순으로 정렬되어 저장되어 있다는 의미이다.
직접 파란 색상을 값으로 담는 스택으로 살펴보면 다음과 같다.
좌측의 이미지는 완전한 모노톤 스택이다. 색깔이 진한 순서대로 정렬되어 적재되어 있기 때문이다.
반면에 우측의 이미지는 모노톤 스택이라고 불릴 수 없다. 왜냐하면 빨간 테두리에 칠해진 부분이 아래의 값보다 연한 색깔을 가지기 때문이다.
위의 이미지 역시 모노톤 스택이 될 수 없다. 다른 색깔을 사용했기 때문이다. 모노톤 스택이 되기 위해서는 같은 타입의 색깔만을 사용해야 한다.
이처럼 오름차순 혹은 내림차순의 정렬된 순서대로 값 저장하는 방식의 특징은 스택이 가지고 있는 특별한 경향성이다. 실제로 스택을 사용하는 많은 기능들이 채택하고 있다.
뿐만 아니라 알고리즘에서 스택을 사용할 때도 이러한 성질을 활용해서 풀어야 하는 경우가 발생한다.
아래는 몇몇 예시이다.
1. 후위 표기식
먼저 연산해야 하는 연산자를 순서대로 스택에 쌓아 해결하는 문제이다. 각각의 연산자들은 처리 해야할 Level이 존재한다. 다음 연산자가 만약 기존의 컨테이너에 존재하는 연산자들과 연속적이지 않다면 소비하는 방식으로 처리된다.
2. 탑
마찬가지로 스택에는 현재 값보다 큰 값들이 내림차순으로 적재되어 있다.
Stack과 Time Sequence ( sequential collection )
스택은 시간에 순차적인 혹은 연달아 발생하는 곳에서 자주 사용된다. 개인적으로는 이 역시 모노톤과 유사하다고 생각하는 편이다.
실제로도 스택의 내용을 살펴보면 시간을 역행하는 경우는 컨테이너 내에 존재하지 않는다.
1. Call Stack 혹은 Execute Context Stack
function one() {}
function two() { one() }
function three() { two() }
function four() { three() }
function five() { four() }
five();
JavaScript
우리는 five() 함수가 호출 되면 five() -> four() -> three() -> two() -> one() 순서대로 호출되는 것을 알고 있다. 반대로 함수의 실행 및 종료는 one() -> two() -> three() -> four() -> five() 순서대로 종료될 것이다.
이 때, Call Stack은 가장 최근에 실행된 순서대로 스택에 적재된다. 도중에 순서가 바뀌는 경우도 없고, 다른 함수가 실행되고 종료되는 와중에도 이 규칙은 절때 깨지지 않는다.
이는 자바스크립트 실행 컨텍스트(Execute Context)에서도 마찬가지다.
2. Browser History
브라우저 히스토리 역시 가장 최신에 방문한 순서대로 top 으로 적재된다.
MDN에 존재하는 정의는 아래와 같다.
DOM의 Window 객체는 history 객체를 통해 브라우저의 세션 기록에 접근할 수 있는 방법을 제공합니다. history는 사용자를 자신의 방문 기록 앞과 뒤로 보내고 기록 스택의 콘텐츠도 조작할 수 있는, 유용한 메서드와 속성을 가집니다. ( History API )
LeetCode에 Browser History에 대한 디자인 예시 문제 역시 stack으로 해결 가능하다.
#include <stack>
class BrowserHistory {
private:
stack<string> back_stack;
stack<string> forward_stack;
public:
BrowserHistory(string homepage) {
this->visit(homepage);
}
void visit(string url) {
this->back_stack.push(url);
this->forward_stack=stack<string>();
}
string back(int steps) {
for(int i=0; i<steps && this->back_stack.size() > 1; i++) { // 이 while for 상황 물어보기!
string current = this->back_stack.top();
this->back_stack.pop();
this->forward_stack.push(current);
}
return this->back_stack.top();
}
string forward(int steps) {
for(int i=0; i<steps && !forward_stack.empty(); i++) {
string current = this->forward_stack.top();
this->forward_stack.pop();
this->back_stack.push(current);
}
return this->back_stack.top();
}
};
C++
Queue와 비동기의 제어
요즘 특히 백엔드 및 인프라 진영에서 성능 향상을 위해서 Message Queue를 많이 도입하고 있는 것으로 알고 있다. Message Driven 기반의 아키텍쳐를 도입하는 이유야 많겠지만 이번에 포커스를 두고 싶은 것은 각각의 기능에서 모두 비동기적으로 동작한다는 포인트이다.
비동기는 통제가 힘들다. 예를 들어보자.
const asyncTask = (result) => {
return new Promise((resolve) => {
setTimeout(() => {
resolve(result);
}, Math.random() * 1000);
});
};
asyncTask("1").then((v) => {
console.log(v);
});
asyncTask("2").then((v) => {
console.log(v);
});
asyncTask("3").then((v) => {
console.log(v);
});
asyncTask("4").then((v) => {
console.log(v);
});
asyncTask("5").then((v) => {
console.log(v);
});
C++
이와 같이 비동기 요청이 들어왔다고 가정했을 때, 1, 2, 3, 4, 5 가 각각 순차적으로 실행되게 하려면 어떻게 해야 할까.
단순히 결과만 보면 동기처리(await)를 하면 되는 것처럼 보이지만 만약 여러 기능이 동시에 작동 중이라면 해당 처리가 다른 기능의 처리까지 오버헤드를 발생시키게 된다.
(async () => {
console.log(await asyncTask("api task1"));
console.log(await asyncTask("api task2"));
console.log(await asyncTask("api task3"));
console.log(await asyncTask("api task4"));
console.log(await asyncTask("api task5"));
// API를 순서대로 실행하기 위해서는, 브라우저의 작업들을 대기시켜야 한다.
asyncTask("browser task1").then((v) => console.log(v));
asyncTask("browser task2").then((v) => console.log(v));
asyncTask("browser task3").then((v) => console.log(v));
asyncTask("browser task4").then((v) => console.log(v));
asyncTask("browser task5").then((v) => console.log(v));
})();
JavaScript
이런 경우에 Queue 를 이용하게 되면 비동기 상황에서 하나의 태스크에 대해 동기 처리가 가능하게 된다.
각각의 기능들은 바로 실행되는 것이 아니라 큐에 요청할 파라미터, 즉 메시지를 push 한다.
이후에 queue는 하나씩 consume하며 처리하게 되면 태스크 내부에서는 순서대로 실행을 보장하나 각각의 태스크는 독립적으로 비동기로 동작할 수 있게 된다.
const genTask = (prefix) => {
const asyncTask = (result) => {
return new Promise((resolve) => {
setTimeout(() => {
resolve(result);
}, Math.random() * 1000);
});
};
const queue = [];
queue.push(`${prefix} task 1`);
queue.push(`${prefix} task 2`);
queue.push(`${prefix} task 3`);
queue.push(`${prefix} task 4`);
queue.push(`${prefix} task 5`);
const consume = () => {
if (queue.length == 0) return;
const top = queue.shift();
asyncTask(top).then((v) => {
console.log(v);
consume();
});
};
consume();
};
genTask("api");
genTask("browser");
JavaScript
MSA등에서 사용되는 Message Queue도 비슷한 맥락으로도 이해할 수 있다.
각각의 task들은 독립적으로 비동기 요청을 하길 원하지만 task들을 소비하는 곳은 여러 곳일 수도 있고, 또 순서나 타이밍이 중요한 경우가 발생할 수도 있다. 이처럼 비동기임에도 불구하고 통제를 하기 위해서는 container를 활용해서 문제를 해결 할 수 있는 경향이 있는 것 같다.
MultiLevel Feedback Queue
큐는 몇몇 경우에 우선적으로 처리가 필요한 경우가 발생한다.
대표적으로 Javascript Engine의 이벤트 루프가 그러하다. MicroTask Queue, Request Animation Queue, Macrotask Queue와 같이 여러 Queue가 별도로 존재하고 처리해야할 우선순위가 Queue마다 다르다.
이러한 처리를 하는 Queue를 별개로 MultiLevel Feedback Queue 라고 부른다. 특히 OS Scheduling에서 많이 나오는 키워드이다.
그 외에도 게임 렌더링 엔진 등에서도 마찬가지로 적용된다. 특히 재미있었던 점은 이 모든 것이 당연스럽게도 비동기 태스크와 스케쥴링과 연관이 있는 점이었다.
마치며
이전에는 자료구조를 학습해야 하는 이유에 대해서 확신이 서지 않았을 때가 있었다. 물론 실무에 사용하는 많은 기능들이 이를 활용중이긴 하지만 몰라도 사용하는데는 지장이 없었기 때문이다.
하지만 막상 깊게 살펴보고 나니 여태까지 부정확하게 사용하고 있음을 깨달을 수 있었다.
특히 최근 웹 개발이 폭팔적으로 성장하면서 퍼포먼스에 대한 관심이 늘어남에 따라 Queue 와 같은 것들은 다양하게 활용해보고 계속해서 학습하는 것이 좋겠다는 생각을 했다.
< 이번 기회에 큐와 스택에 대해서 모른다는 것을 알았다. >