[자료구조] Stack 스택에 대해 알아보자 (자바스크립트)

---

스택은 무엇일까?

---

스택은 `Last In First Out` 이라는 개념을 가진 선형 자료구조다.

 

말 그대로 '나중에 들어간 요소가 먼저 나온다' 혹은 '먼저 들어간 요소가 나중에 나온다' 라는 개념이다.

상자에서 나중에 넣은 물건을 먼저 꺼내듯이 말이다.

 

요소를 넣는 것을 push 라 부르고,

요소를 빼는 것은 pop 이라고 부른다.

그리고 Stack의 맨 위에 있는 요소를 TOP 이라고 부른다.

 

스택은 프링글스 통과 비슷하다.

마치 프링글스 통과 비슷한 구조로,

맨 위에 있는 과자만 꺼낼 수 있고, 아래에 깔린 과자는 꺼낼 수 없다.

 

 

 

스택의 동작 원리

---

스택의 동작 원리는 굉장히 단순하다.

우리가 할 수 있는 행동은 요소를 넣는 push와 빼는 pop만이 존재한다.

가장 맨 위에 있는 TOP 요소만 컨트롤 하기에 구현도 어렵지 않다.

 

스택  메모리

---

스택 자료구조를 이용하는 가장 대표적인 것은 스택 메모리다.

스택 메모리는 함수가 호출되며 생성되는 지역변수, 매개변수가 저장되는 메모리 영역이다.

 

function sum(a, b) {
  return a + b;
}

function print(value) {
  console.log(value);
}

print(sum(5, 10));

 

1. 먼저 가장 안쪽에 위치한 sum 함수가 실행된다.

    함수가 실행되면서 스택 메모리에는 지역변수, 매개변수, 반환 주소값이 push 되어 기록된다.

    sum 함수 실행이 종료되어 값이 반환되면 스택 메모리에서 pop이 수행되며 제거된다.

 

2. 이어서 print 함수가 실행된다.

     아까 반환된 값으로 실행되어 스택 메모리에 기록된다.

     print 함수 내의 console.log 함수가 실행되면서 다시 스택 메모리에 쌓이게 된다.

     무사히 로그 출력을 마쳤다면 스택 메모리에서 제거된다.

     print도 함수 호출이 완료되면서 스택 메모리에서 제거된다. 

 

 

함수 호출은 이런 식으로 스택 메모리를 통해 자료구조에 기록되고 제거된다.

 

 Array 로 표현하기

---

스택을 Array로 표현할 수 있다.

push를 하면 배열의 첫번째부터 순차적으로 요소가 삽입되고, pop을 하면 가장 마지막 요소를 제거한다.

이런 방식은 배열의 단점인 중간요소  추가, 삭제 로직이 전혀 삭제되지 않기 때문에 굉장히 유리한 방식이라 할 수 있다.

특히 자바스크립트에서는 배열의 크기가 유연하게 증감되기 때문에 더 편하게 구현이 가능하다.

물론 자바스크립트의 배열은 엄밀히 따져서 진짜 배열이라고 할 수는 없지만 말이다.

 

Linked List 로 표현하기

---

C언어나 Java와 같은 언어에선 스택의 크기가 고정되지 않는 경우에 유한한 배열 대신 연결 리스트를 이용하여 구현하는 경우가 많았다. 이 경우엔 연결리스트의 헤드가 TOP 이라고 할 수 있다.

 

Javascript 로 사용하는 법

 

1. Array 로 구현

 

---

편리한 push, pop 함수가 있기 때문에 편하게 배열을 이용하면 된다.

const stack = [];

// Push
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack); // [1, 2, 3]

// Pop
stack.pop();
console.log(stack); // [1, 2]

// Get Top
console.log(stack[stack.length - 1]);

 

 

2. Linked List로 구현

---

연결리스트로 구현하는 방식은 조금 더 복잡하다. 기존 연결리스트의 코드에서 헤드를 탑으로 지정하고,

제거 로직은 오직 헤드를 제거하는 방식으로 로직을 수정하면 된다.

 

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

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

  push(value) {
    const node = new Node(value);
    node.next = this.top;
    this.top = node;
    this.size += 1;
  }

  pop() {
    const value = this.top.value;
    this.top = this.top.next;
    this.size = -1;
    return value;
  }

  size() {
    return this.size;
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // 3
stack.push(4);
console.log(stack.pop()); // 4
console.log(stack.pop()); // 2