stack

스택

스택: Last In First Out

큐: First In First Out

호출스택 분석

우선 호출과 선언을 구별해야한다.

1. (익명)스택: 실행하려는 파일을 하나의 익명 함수로 보면 된다.

2. 함수가 호출되면 선언부가 실행됨 - a() 호출이 생기고 호출스택에 a가 들어간다.

3. 7번째 줄 코드가 실행된다.

4. 9번째 줄 console도 호출이기 때문에 호출스택에 log가 들어간다. 그리고 바로 10번째 코드인 function b()로 가는게 아니라 console.log(’a’) 의 선언한 부분으로 가야하지만 알 수 없기 때문에 호출스택에는 보이지 않는다. 호출스택에 들어갔다가 빠졌다고 보면 된다.

5. 15번째 줄 b() 가 호출스택으로 들어간다. 그리고 10번째 줄의 b()의 선언 부분으로 돌아간다.

6. 12번째 줄 console.log(’b’)가 호출스택에 들어갔다가 빠진다.

7. 13번째 줄 c() 가 호출 스택으로 들어간다. (14번째 줄로 가는게 아니라) 2번째 줄 c()선언부로로 돌아간다.

8. 4번째 줄 console.log(’c’) 가 호출스택에 들어갔다 빠진다.

선언부가 모두 실행되면 이제 호출스택에 쌓인 호출들이 빠져나갈 차례다.

1. 5번째 줄 c()함수가 끝나면 c가 빠져나간다.

2. 14번째 줄의 b()함수가 끝나면서 b가 빠져나간다.

3. 16번째 줄의 a() 함수가 끝나면서 a 가 빠져나간다.

4. 19번째 줄의 c() 함수가 호출되면서 2번째 줄의 c() 함수가 실행된다. 4번째 줄의 console.log(’c’)가 호출스택에 들어갔다 빠진다.

결론: 호출할 때마다 호출스택에 들어가고 함수가 끝날때마다 호출스택에서 빠져나온다.

스택 메서드 활용

class ArrayStack {
  static SIZE = 3;
  constructor(size = ArrayStack.SIZE) {
    this.stack = new Float32Array(size);
    this.top = -1;
  }

  push(data) {
    // 예외처리
    if (typeof data !== 'number') {
      throw new Error('숫자를 입력해주세요');
    }
    // ArrayStack의 top과 ArrayStack의 size(3 - 1) 이 같으면 Stack Overflow
    if (this.top === this.size - 1) {
      throw new Error('스택이 가득 찼습니다 (Stack Overflow) \\n');
    }
		// 상기 2가지 edge case 외에는 스택 끝에 push
    this.stack[++this.top] = data;
  }

  pop() {
		// 스택 부족현상 확인 예외처리
    if (this.top === -1) {
      console.error('스택이 비어있습니다 (Stack Underflow)');
      return null;
    }
    return this.stack[this.top--];
  }

	// 가장 늦게 들어온 자료인 '최상위 자료'를 읽은 후 이를 반환하는 연산
  peek() {
    return this.stack[this.top];
  }

	// top이 0보다 작은지 확인 boolean값 반환
  isEmpty() {
    return this.top < 0;
  }
}

const arrayStack = new ArrayStack(3)

// arrayStack.push(1)
// arrayStack.push(2)
// arrayStack.push(2)

// arrayStack 
// > ArrayStack {stack: Float32Array(3), top: 2}
// **stack**: Float32Array(3) [1, 2, 3, buffer: ArrayBuffer(12), byteLength: 12, byteOffset: 0, length: 3, Symbol(Symbol.toStringTag): 'Float32Array'] **top**: 2

// arrayStack.pop()
// > 3
// arrayStack.pop()
// > 2
// arrayStack.pop()
// > 1

// arrayStack.isEmpty()
// > false

// arrayStack.pop()
// > 스택이 비어있습니다 (Stack Underflow)

• peek 또는 top : stack의 가장 위에 있는 값(현재 값)을 반환한다.

• push : stack에 데이터를 입력한다.

• pop : stack에 데이터를 삭제한다.

• empty : stack에 데이터가 없으면 참(true), 없으면 거짓(false)을 반환한다.

스택의 Big O

삽입: O(1)

제거: O(1)

검색: O(n)

접근: O(n)