(Javascript) [자료구조] Stack

Stack(스택)

• 선입후출(LIFO, Last In First Out), 먼저 들어간 게 나중에 나중에
• 브라우저 History(이전,다음 페이지) 또는 Ctrl+z로 이전작업을 취소하는 등의 동작에 쓰이는 자료구조
• Call stack
  • JS 코드가 실행되며 생성되는 실행 콘텍스트(Execution Context)를 저장하는 자료구조
  • 함수를 호출하면 실행 컨텍스트가 생성되며, 이를 Call stack에 추가한 다음 함수를 수행
  • 함수에 의해 호출되는 모든 함수(내부 함수들)는 Call stack에 추가되고 해당 위치에서 실행
  • 함수의 실행이 종료되면 해당 실행 콘텍스트를 Call stack에서 제거한 후 중단 된 시점부터 다시 시작
  • 만약 스택이 할당된 공간보다 많은 공간을 차지 하면 Stack Overflow 발생

스택 개념 이미지 화

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

class StackNode extends Node {
    constructor(data, head) {
    super(data);
    this.head;
    }
    push(data) {
        if (!this.data) this.data = data;
        else if (this.head) {
            this.head.push(data);
        } 
        else {
            this.head = new StackNode(data);
        }
    }
    pop() {
    if (this?.head?.head) return this.head.pop();
    else if (!this?.head) {
        const temp = this.data;
        this.data = undefined;
        return temp;
    } else {
        const temp = this.head.data;
        delete this.head;
        this.head = undefined;
        return temp;
        }
    }
}
const stack = new StackNode(1);
stack.push(2);
stack.push(3);
stack.push(4);
console.log(stack);
console.log(stack.pop());
console.log(stack.pop());
console.log(stack);

위 stack코드에 관한 결과 창

push 메서드

• if(!this.data) this.data = data; : 만약 data가 없으면 현재 노드의 data에 전달받은 매개변수 data를 정의한다.
• else if(this.head){ this.head.push(data); } : head가 있다는 마지막 스택이 아니라는 뜻이기에 다음 노드에 data를 넣어 준다.
• else { this.head = new StackNode(data); } : 다음 데이터가 없고, 현재 데이터는 있을 때 head에 data를 담은 새로운 스택노드를 추가해준다.

pop 메서드

• if(this?.head?.head)  :  return this.head.pop() : 현재 헤드의 헤드가 있으면 그 현재 헤드를 다시 pop 메서드 호출, 실행한다.
• else if(!this?.head) { const temp = this.data; this.data = undefined; return temp ; } : 현재 헤드의 헤드가 없고, 현재의 헤드마저 없다면 현 데이터를 임시 temp 변수에 정의하고 현재 데이터를 undefined로 재정의하고 저장했던 temp를 리턴(반환)하여 현재 데이터를 뽑아낸다.
• else { const temp = this.head.data; delete this.head; this.head = undefined; return temp; } : 현재 헤드의 헤드는 없지만 현재 헤드만 있을 경우 현재 헤드의 데이터를 임시 변수 temp에 저장하고 현재 헤드를 지우고 undefined로 재정의하면서 임시변수에 넣어두었던 현재 헤드의 데이터를 리턴(반환) 해준다.