지난 글에서 스택과 큐에 대해 다뤘지만, 피드백을 받으며 스택에 대해 제가 혼자만의 오해를 가지고 있었다는 걸 알게 되었습니다. 그래서 오늘은 그 오해를 풀고, 스택 자료구조에 대해 다시 한번 정리해보고자 합니다.
사실, 스택의 개념에 대해서는 저보다 훨씬 뛰어난 개발자분들이 이미 쉽게 풀어 쓴 글들이 많기 때문에, 이 글에서는 개념을 간략히 짚고 넘어가려 합니다. 대신 JavaScript로 스택을 직접 구현해보고, 프론트엔드 개발자로서 이 자료구조에 대한 저의 생각을 공유하고자 합니다.
스택을 이해하고 나니 다양한 상황에서 실질적인 활용이 가능하다는 걸 깨달았고, 오늘 글을 통해 이러한 점을 함께 나누고 싶습니다.
스택이란?
스택은 마지막에 넣은 요소가 가장 처음으로 제거 된다는 간단한 자료 구조입니다.
관련된 용어로는 다음과 같습니다.
- 요소를 넣는 것 : push
- 요고를 제거하는 것 : pop
- 스택 공간 초과 : stack overflow
- 스택 공간 부족 : stack underflow
스택 오버플로우가 발생한다는 것은 스택이 고정된 크기 제한을 가지고 있다는 의미입니다. 다만, 스택의 종류에 따라 스택 오버플로우가 발생하지 않을 수도 있습니다. 여기서 말하는 스택 오버플로우는 메모리 초과(Out of Memory) 오류를 제외하고, 스택 자체의 크기 제한에 의해 발생하는 오류를 의미합니다.
Array === Stack 인가?
스택의 종류를 설명하기에 앞서, 제가 처음 스택을 공부하며 했던 오해에 대해 먼저 이야기해보려 합니다. 처음엔 JavaScript의 Array가 push와 pop 메서드를 제공하니, Array 자체가 스택 자료구조라고 생각했습니다. 하지만, Array는 스택인가?라는 질문에 대한 답은 사실 "아니요"입니다.
- 스택은 Array뿐 아니라 Linked List로도 구현할 수 있습니다. 즉, Array를 이용해 스택을 만들 수는 있지만, Array만이 스택을 구성하는 유일한 방법은 아닙니다.
- 스택은 오직 상단(top)에서만 접근할 수 있는 제한이 있습니다. 하지만 Array는 push와 pop 외에도 맨 앞에 요소를 추가할 수 있는 unshift등 다양한 메서드를 제공합니다. 이 때문에 Array는 스택의 엄격한 특성을 만족하지 못합니다.
결론적으로, Array는 스택을 구현할 수 있는 도구일 뿐, 그 자체로 스택 자료구조라고 할 수는 없습니다.
스택의 종류
stack overflow 오류가 발생하냐 안하냐는 다음 두 종류의 스택에 따라서 달라지는데요.
배열 기반 스택
배열 기반 스택의 경우 말그대로 Array를 기반으로 만들어진 것인데요. 스택의 크기가 제한적이라는 특징이 있습니다.
관련해서 작성 해본 코드는 다음과 같습니다. 간단히, pop과 push기능만 들어간 코드를 작성해보았습니다.
class Stack {
constructor(maxSize) {
this.stack = [];
this.maxSize = maxSize;
}
get get_stack() {
return this.stack;
}
push(item) {
if (this.maxSize === this.stack.length) {
throw Error("stack overflow");
}
this.stack.push(item);
}
pop() {
if (this.stack.length === 0) {
throw Error("stack underflow");
}
this.stack.pop();
}
}Linked List 기반 스택
Linked List는 연결된 리스트라는 의미로 하나의 데이터와 그다음 데이터의 위치를 저장해 서로 연결시킨 구조를 말합니다. 프론트엔드 개발자에겐 다소 생소한 개념일 수 있을 것 같습니다. 왜냐하면, JavaScript에서는 Linked List가 없기 때문입니다.
다시 본론으로 돌아와서, Linked List를 이용해 만든 스택을 다이나믹 스택이라고도 부르는데요. 앞서 이야기 했다시피, 이 스택의 장점은 크기를 정해놓지 않아서 Stack overflow가 발생하지 않는 다는 장점이 있습니다.
JavaScript를 이용해서 이 LinkedList stack를 구현을 어떻게 할수 있을지에 대해 고민하다. 저한테는 조금 어려워.. 결국, gpt의 도움을 받아 다음과 같이 완성할 수 있었습니다!
class Node {
constructor(value) {
this.value = value;
this.next = null; // 다음 node에 대한 정보를 저장합니다.
}
}
class LinkedListStack {
constructor() {
this.head = null;
this.size = 0;
}
push(item) {
const newNode = new Node(item);
newNode.next = this.head;
this.head = newNode;
this.size++;
}
pop() {
if (!this.size) {
throw new Error("stack underflow");
}
this.head = this.head.next;
this.size--;
}
}코드에 대해서 간단히 설명해 보자면,
- Node 클래스: value와 next를 속성으로 가지며, 다음 노드를 가리킵니다.
- push 메서드: 새 노드를 스택의 head에 추가합니다. 새로운 노드의 next를 현재 head로 설정한 후, head를 새 노드로 업데이트합니다.
- pop 메서드: 현재 head의 값을 반환하고, head를 다음 노드로 이동시킵니다. 만약 head가 없으면(스택이 비어 있으면) Stack Underflow 에러를 발생시킵니다.
스택의 시간/공간 복잡도
스택의 시간과 공간 복잡도는 사용하는 연산에 따라 달라집니다.
시간 복잡도:
push와 pop 연산: 스택은 항상 상단(top)에서만 요소를 추가하거나 제거하기 때문에 특정 위치를 찾거나 이동할 필요가 없습니다. 따라서 push와 pop 연산은 O(1)의 시간 복잡도를 가집니다.
특정 요소 접근: 스택에서는 특정 요소에 접근하려면 상단부터 해당 요소까지 차례로 탐색해야 합니다. 따라서 특정 요소를 읽거나 검색하는 연산의 시간 복잡도는 O(n)이 될 수 있습니다.
공간 복잡도:
전체 공간 복잡도: 스택의 공간 복잡도는 현재 스택에 저장된 요소의 수에 비례하며 O(n)입니다. 이는 스택에 n개의 요소가 있을 때, 이들 모두를 저장하기 위한 공간이 필요하기 때문입니다.
각 연산의 공간 복잡도: push와 pop 연산은 요소 하나를 추가하거나 제거할 때 필요한 고정된 공간만 차지하기 때문에 각 연산의 공간 복잡도는 O(1)입니다.
나도 모르게 사용하고 있던 스택 자료구조
"프론트엔드 개발자가 스택을 다룰 일이 있을까요?" 예전엔 그렇지 않다고 생각했습니다. 그러나 이번 공부를 통해 생각이 바뀌게되는 계기가 되었습니다.
사실, 저는 이미 저도 모르게 스택 자료구조를 사용하고 있었는데요. 모달 컴포넌트를 구현할 때, 모달을 겹겹이 쌓아 올리고, 가장 최근에 열린 모달부터 닫는 방식은 바로 스택의 후입선출(LIFO) 원리를 활용한 것이었습니다.
프론트엔드 개발에서 스택은 이런 식으로 자연스럽게 쓰이며, 다양한 UI/UX 기능에서도 중요한 역할을 합니다. 그러나 스택은 항상 상단(top) 요소에만 접근할 수 있다는 제한이 있어 원하는 위치의 요소를 쉽게 찾거나 조작하기 어렵다는 단점이 있습니다.
예를 들어, 모달에 "하위에 있는 모달을 클릭했을 때 그 모달이 최상단으로 올라오게 해주세요"와 같은 요구 사항이 추가된다면, 스택 자료구조는 더 이상 적합하지 않게 됩니다. 이럴 땐 요소에 자유롭게 접근할 수 있는 큐나 배열을 활용한 관리 방식이 더 적합할 것입니다.
그럼에도 불구하고 스택은 특정 기능에서 아주 유용하게 쓰일 수 있습니다. 예를 들어, 방문 기록을 저장하거나 알림 창을 관리하는 기능에서도 스택 구조는 큰 도움이 됩니다.
프론트엔드 개발에서 클린 코드란 단순히 코드가 깔끔해 보이는 걸 넘어서, 효율적이고 유지보수하기 쉽게 만드는 것을 의미합니다. 이런 자료구조를 잘 이해하고 있으면 제품의 기능을 더 개선해 나갈 수 있고, 사용자에게도 더 나은 경험을 제공할 수 있을 것 같습니다.
