[Coding Interview University] 스택 : 이론 및 구현

<본 블로그는 코딩인터뷰대학 님의 Git과 서적을 참고해서 공부하며 작성하였습니다 :-)>

 

🫧 스택

: 데이터를 쌓아 올린다

: LIFO (Last In First Out) 에 따라 자료를 배열한다

: 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목

: 배열과 달리 스택은 상수 시간에 i 번째 항목에 접근할 수 없음

: 스택에서 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능하다

 

🫧 스택이 유용할 경우

: 재귀 알고리즘을 사용할 때 유용함

: 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어 주고, 재귀 함수를 빠져 나와 퇴각 검색(backtrack) 할 때는 스택에 넣어 주었던 임시 데이터를 빼 줘야 한다

: 일련의 행위를 직관적으로 가능하게 해 준다

: 재귀 알고리즘을 반복적 형태 (iterative) 를 통해서 구현할 수 있게 함

 

🫧 스택 구현하기

function Stack(arr = Array()) {
  this.arr = arr;
}

let stk = new Stack();
let stk2 = new Stack(['test', 'test2']);

➡️ isEmpty() : 비어있는지 확인(반환값 t/f)

Stack.prototype.isEmpty = function(){
  return this.arr.length === 0;
}

➡️ push(data) : 스택에 데이터 추가하기

Stack.prototype.push = function (data) {
  this.arr.push(data);
};

➡️ pop() : 스택 맨 위의 데이터 삭제하기

Stack.prototype.pop = function () {
  return this.arr.pop();
};

➡️ top() : 스택 맨 위의 데이터 확인하기

Stack.prototype.top = function () {
  return this.arr.slice(-1);
};

➡️ size() : 스택의 데이터 개수 출력

Stack.prototype.size = function () {
  return this.arr.length;
};