[알고리즘, 자료구조] 자바스크립트로 스택(Stack)구현하기 (+개념이해)

 

어떤 데이터의 구체적인 구현 방식은 생략한 채, 데이터의 추상적 형태와 그 데이터를 다루는 방법만을 정해놓은 것을 가지고 ADT(Abstract Data Type) 혹은 추상 자료형이라고 한다. 그 중 널리 사용되는 스택(Stack) 과 큐(Queue) 에 대해 알아보고자한다.

 

스택(Stack) 과 큐(Queue)는 프로그래밍이라는 개념이 탄생할 때부터 가장 고전적인 자료구조 중 하나이다. 

하지만 이 두 자료구조는 자바스크립트(JavaScript)에 내장되어 있기 않지만, 베열(Array)과 내장함수들을 이용하여 스택(Stack) 과 큐(Queue)를 흉내낼 수는 있다.

 

대부분의 알고리즘 문제를 풀어야할 경우 배열을 이용하더라도 통과하는 편이지만, 시간 복잡도를 매우 세세하게 관리한다던가, 데이터의 양이 매우 큰 경우에는 이 같은 방식으로는 통과할 수 없는 경우가 종종 있다고 한다. 

 

게다가 이 두 자료구조는 프로그래밍에서 있어 중요한 자료구조이고, 파이썬으로 구현하는 것을 보고나니 자바스크립트(JavaScript)로 어떻게 구현할지 궁금했다.

 

따라서 두 포스팅에 걸쳐 스택(Stack) 과 큐(Queue)를 이해하고 자바스크립트(JavaScript)로 구현하는 방법에 알아보고자 한다. 

 

---

스택 (Stack)

• LIFO(Last in, Last out) 원칙으로 만들어진 자료구조 > 나중에 들어온 데이터가 먼저 나간다.   
• - 함수 실행 콘텍스트들이 쌓이는 Call stack과 브라우저의 방문 기록이 쌓이는 History stack이 대표적이다.
• 서로 관계가 있는 여러 작업을 연달아 수행하면서 이전의 작업 내용을 저장해 둘 필요가 있을 때 널리 사용된다.
• 스택(Stack)이 비어있을 때 stack.pop을 시도하는 것을 stack underflow라고 하고 스택(Stack)의 크기가 비어있을 때 stack.push를 시도하면 stack overflow가 발생한다. 

 

이해를 돕기 위해 그려본 스택의 flow

 

속성

• top : 스택 맨 위의 아이템

메소드

• push : 스택의 맨 위에 아이템을 삽입한다
• pop : 스택 맨 위의 아이템을 제거하고 및 그 아이템을 반환한다
• contains : 해당 아이템이 스택에 존재하는지 확인한다
• size : 현재 스택에 있는 아이템의 총 개수를 반환한다

스택 (Stack) 사용 사례

• 재귀 알고리즘
• 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
• 재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다.
• 스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다.
• 또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
• 웹 브라우저 방문기록 (뒤로가기)
• 실행 취소 (undo)
• 역순 문자열 만들기
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
  Ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기
• 후위 표기법 계산

 

 

---

 

JavaScript 배열로 스택 (Stack)구현

간단하고 명료하다. 확실히 알고리즘을 풀고 개념을 적으니까 더 이해가 잘 되는 것 같다.

 

export default class Stack {
  constructor() {
    // item들을 받을 배열 생성
    this.items = [];
  }

  push(item) {
    this.items.push(item);
  }

  pop() {
    return this.items.pop();
  }

  peek() {
    if (this.items.length === 0) {
      return null;
    }
    // items 배열의 마지막 item만 가져와준다. pop()과 다르게 배열에서 아이템이 빠지는 것이 아닌 유지된 채로 마지막 값만 받아와줌
    return this.items[this.items.length - 1];
  }

  getSize() {
    return this.items.length;
  }

  isEmpty() {
    return this.getSize() === 0;
  }
}

 

 

---

 

배열 이용하지 않고 스택 (Stack)구현

배열을 이용하지 않았기에 연결리스트(Linked List)방식으로 구현하였다. 연결리스트를 처음 알고리즘문제로 접했는데 너무 어려웠다. 하지만 스택(Stack)의 개념을 이해하고 이를 구현하고자 연결리스트(Linked List)를 사용하게 되니 이해가 더 잘됐다. 

 

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

class Stack {
  constructor() {
    this.top = null;
  }

  isEmpty() {
    return this.top === null;
  }

  push(data) {
    // 새로운 데이터를 받은 노드생성,
    const newNode = new Node(data);
    // 현재 최상위 노트(현재의 this.top노드) 기 새로 노드의 next가됨
    newNode.next = this.top;
    // 그리고 최상위 노드는 새로 들어온 newNode가 된다.
    this.top = newNode;
  }

  pop() {
    if (this.isEmpty()) return;
    // 최상단 노드가 pop()되면서 최상단 밑에있던 노드가 최상단 노드(this.top)가 된다.
    this.top = this.top.next;
  }

  peek() {
    if (this.isEmpty()) return -404;
    return this.top.data;
  }

  display() {
    if (this.isEmpty()) return;
    let curr = this.top;
    process.stdout.write("(TOP) ");
    while (curr.next) {
      process.stdout.write(`${curr.data} ---> `);
      curr = curr.next;
    }
    process.stdout.write(`${curr.data}\n`);
  }
}

 

print 결과

 

 

---

 

스택(Stack)의 Big-O (Time Complexity)

 

Insertion : Stack에 데이터를 추가하는 것은 Stack의 맨 위에 하나를 올리기(push)를 하면된다. 스택에 들어있는 값들이 무수히 많아도 하나의 데이터의 삽입은 한 번이기 때문에 시간 복잡도는 O(1)이 된다. 

 

delete : LIFO에 따라 삭제를 할 때도 최상위 데이터가 삭제되는 것이므로 스택의 크기에 상관없이 시간복잡도는 O(1)이된다. 

 

Access : 스택(Stack) 특성상 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료구조이므로 데이터 접근 또한 데이터가 삽입된 top을 통해서만 접근이 가능하다. 삭제 또한 top을 통해서만 가능하다. 따라서 n번 째 접근은 top데이터부터 순회하기 때문에 O(n)의 시간복잡도를 가진다. 

 

Search : 데이터를 찾을 때 만약 스택의 가장 최상단에 있는 데이터를 찾는다면 시간복잡도는 O(1)일 것이다. 하지만 가장 밑에있는 데이터를 찾는다면 데이터의 개수만큼 작업이 발생되므로 시간복잡도는 O(n)이 되겠다. 

 

 

Big-O (시간복잡도)	삽입	삭제	접근	n번째 접근	검색
스택 (Stack)	O(1)	O(1)	O(1)	O(n)	O(n)

 

 

 

---

빼놓을 수 없는 큐(Queue) 자료구조 이해 & 구현하기!

https://algoroot.tistory.com/55

[알고리즘, 자료구조] 자바스크립트로 큐(Queue)구현하기

 

 

 

Reference :

 

https://medium.com/globant/implementing-stack-and-queue-in-js-600c81a92120

https://helloworldjavascript.net/pages/282-data-structures.html

https://www.youtube.com/watch?v=-g0lYeoIQEA 

https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html