[자료구조] 스택 with JavaScript

 

들어가며

SOPT의 세미나에서 스택과 큐에 대해 처음 배웠습니다. 당시 자바스크립트 동작 원리를 배우면서 콜 스택에 대해 배웠는데, 스택이 무엇인지 몰라서, 이해를 못하고 넘어갔던 기억이 납니다. 생각해보면 정확하게 스택이 무엇이고, 스택은 어떻게 처리할 수 있는지 제대로 공부해본 적이 없었던 것 같습니다. 데이터들을 어떤 구조로 어떻게 저장하느냐에 따라 프로그램의 효율과 성능이 차이가 날 수 있다고 합니다. 따라서 스택에 대해 제대로 공부해야 더 효율적이고 성능 좋은 프로그램을 개발할 수 있다고 믿습니다. 

 

어디선가, 늦음을 걱정하지 말고 제대로 하지 않았음을 걱정하라는 이야기를 들은 적이 있습니다. 이제부터라도 제대로 공부하고 싶어 이 글을 정리합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

스택은 어디에 쓰일까?

무엇인가 글을 잘못쓰거나 수정하고 싶을 때, 우리는 ctrl + z를 활용해서 되돌리기를 하곤 합니다. 그리고 되돌리기 한 것을 취소하고 싶으면 다시 돌릴 수 있습니다. 이런 작업들은 우리를 스택을 통해 구현할 수 있습니다. 또한 자바스크립트에서 모든 함수 호출은 스택 자료 구조로 이루어져 있습니다.그렇다면, 스택은 무엇이며, 스택을 어떻게 구현할 수 있는지 함께 알아보겠습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Stack (스택)

Stack은 데이터를 한 줄로 쌓아서 마치 탑을 쌓듯 추가하는 형태의 자료 구조입니다. Stack의 맨 위에 데이터를 추가하는 것을 'push'라고 하고, 반대로 맨 위에 데이터를 하나씩 제거하는 것을 'pop'이라고 합니다. 즉 하나의 탑에 블록을 계속 쌓아가는 형태이고, 가장 마지막에 올린 데이터가 가장 먼저 나오는 형태라고 해서, Last-In First-Out(LIFO) 형태를 갖고 있다고 합니다. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

스택의 BIg-O (시간 복잡도)

만약 스택이라는 자료 구조를 활용하여 자료를 삽입하고 삭제하고 검색한다면 시간 복잡도는 어떻게 되는지 알아보겠습니다. 

 

 

Insertion	O(1)
Deletion	O(1)
Search	O(n)

 

먼저 삽입을 한다고 생각해보겠습니다. 스택에 자료를 추가하는 것은 스택의 맨 위에 하나를 올리기(push)를 하면 됩니다. 즉, 스택이 무수히 커도, 자료를 삽입하기 위해 한 번의 노력만 하면 됩니다. 이를 생각해보면 시간 복잡도는 O(1)으로 표현할 수 있습니다. 

 

만약 삭제를 한다면, 스택이 끝없이 크더라도 맨 위의 자료를 삭제(pop)하면 되므로, 시간 복잡도는 O(1)로 표현할 수 있습니다. 

 

그렇다면 자료를 검색했을 때는 어떻게 될까요? 만약 스택에 10개의 블록이 쌓여있다고 생각해보겠습니다. 만약 가장 맨 위에 올려져 있는 자료를 검색한다면, 우리는 별도의 노력 없이 바로 데이터를 찾을 수 있습니다. 하지만 가장 밑에 있는 자료를 검색한다면, 모든 자료를 모두 검색해봐야 합니다. 이럴 경우 모든 자료를 찾아봐야 하므로, 시간 복잡도는 O(n)으로 표현할 수 있습니다. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

 

 

 

 

 

 

 

 

 

 

 

 

 

stack overflow

 

Stack Overflow?

프로그래밍을 한다면, 구글에 항상 나오는 사이트 stack overflow를 들어보셨을 것입니다. stack overflow는 사실 재귀 함수를 무한 호출했을 때 나오는 대표적인 에러입니다. 

 

function a(data) {
  b(data + 1);
}
function b(data) {
  c(data + 1);
}
function c(data) {
  console.log('스택이 내부적으로 사용되었습니다 ' + data);
}
a(1); // 3

 

위의 코드를 살펴봅시다. 위의 코드에서는 a 안에서 b가, b 안에서 c가 호출됩니다. 스택 메모리 안에서는 [a, b, c] 이렇게 호출된 순서대로 쌓이고(push), c, b, a 순서(pop)대로 실행됩니다. 그래서 c가 실행된 후, b가 실행되고 마지막으로 a가 실행됩니다. 각 함수는 일정 메모리를 차지하기 때문에 스택 메모리 안에 너무 많이 쌓이면 메모리 에러가 발생합니다.

 

function d(data) {
  if (data == 50) {
    console.log('재귀 함수의 스택입니다', data);
  } else {
    d(data + 1);
  }
}
d(1);

 

또한 재귀 함수의 경우는 역시 호출되는 순서대로 쌓이는데 [d, d, d, d,... ] 이렇게 50번 쌓이고, 거꾸로 실행됩니다. 만약 위처럼 50으로 제한을 두지 않았다면 스택 메모리가 다 찰 때까지 계속 쌓이다가 결국 stack overflow로 프로그램이 멈추고 맙니다. 그렇다면 이런 스택은 자바스크립트로 어떻게 구현할 수 있을까요? 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

 

 

 

 

 

 

 

 

 

 

 

 

 

 

JS로 Stack을 구현하기

먼저 Stack에 대한 ADT를 먼저 알아봅시다.

 

* ADT(Abstract Data Type)이란?

ADT란 추상 자료형이라고도 하며, 데이터를 구체적으로 구현하는 방식은 생략하고 데이터의 추상적인 형태와 데이터를 이루는 방법만을 정해놓은 것입니다.

 

ADT	종류	설명
Array	배열	stack을 담을 배열이자 stack 그 자체
push	함수	stack에 새 요소 추가
pop	함수	stack의 맨 위에 있는 요소 삭제
peek	함수	stack의 맨 위에 있는 요소 확인
lefts	함수	stack에 있는 모든 요소 문자열로 반환
clear	함수	stack에 있는 모든 요소 삭제
empty	함수	stack의 남은 요소가 있는지 없는지 확인

 

그렇다면, 위의 ADT를 활용하여 자바스크립트로 Stack을 구현해보겠습니다. 

 

class Node {
  constructor(value){
    this.value = value;
    this.next = null;
  }
}

class Stack {
  constructor(){
    this.top = null;
    this.bottom = null;
    this.length = 0;
  }
  peek() {
    // stack에 쌓인 가장 마지막 녀석을 확인하는 메소드
    return this.top;
  }
  push(value){
    const newNode = new Node(value);
    
    if (this.length === 0) {
      this.top = newNode;
      this.bottom = newNode;
    } else {
      const holdingPointer = this.top;
      this.top = newNode;
      this.top.next = holdingPointer;
    }
    this.length++;
    return this;
  }
  pop(){
    if (!this.top) return null;
    if (this.top === this.bottom) {
      this.bottom = null;
    }
    this.top = this.top.next;
    this.length--;
    return this;
  }
  //isEmpty
}

const myStack = new Stack();
console.log(myStack);
myStack.peek();
myStack.push('google');
myStack.push('facebook');
myStack.push('udemy');
myStack.pop();
myStack.pop();
myStack.pop();

 

위의 코드를 살펴본다면, push를 통해 배열에 데이터를 추가하고, pop 메서드를 통해 데이터를 삭제할 수 있습니다. peek 메서드를 통해 stack의 맨 위에 있는 요소를 확인할 수 있고, lefts 메서드를 통해 stack의 모든 요소 문자열을 반환합니다. empty 메서드를 활용해 배열이 모두 비었는지 비어있지 않은지 확인할 수 있으며, clear 메서드를 활용하면 배열의 모든 요소를 삭제할 수 있습니다. 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

 

 

 

 

 

 

 

 

 

 

 

 

 

 

마치며

이번엔 Stack을 공부했다면, 다음 글은 Queue에 대한 부분을 정리하려 합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

참고

(Algorithm) 자료구조(스택, stack)

[자료 구조] Data Structure - (1) Stack / Queue / Linked List

JavaScript 자료구조 - Stack (스택)

스택 - 위키백과, 우리 모두의 백과사전

[자바스크립트] 스택(stack) 구현하기

자바스크립트의 자료구조 4 : 스택(Stack), 큐(Queue)