[이코테] 03-1 스택, 큐, 재귀함수

DFS/BFS 이전에 자료구조 기초를 자바스크립트로 구현하는 방법

스택, 큐

삽입 push, 삭제pop 함수가 핵심적으로 사용된다.

이외에도 오버플로, 언더플로를 고민해야한다

• 오버플로 : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할때 발생
• 언더플로 : 데이터가 들어있지 않은 상태에서 삭제 연산을 수행할때 발생

 

스택 Stack

선입후출 구조. 출입구가 하나라고 생각하면 된다.

예제 5-1

const stack = [];

stack.push(5);
stack.push(2);
stack.push(3);
stack.push(7);

stack.pop();

stack.push(1);
stach.push(4);

stack.pop();

console.log(stack);//[5,2,3,1]console.log(stack.reverse());//[1,3,2,5]

 

큐 Queue

선입선출 구조. 출입구가 두개라고 생각하면 된다.

예제 5-2

const queue = [];

queue.push(5);
queue.push(2);
queue.push(3);
queue.push(7);

queue.shift();//선입(5) pop

queue.push(1);
queue.push(4);

queue.shift();//다음 선입(2) popconsole.log(queue);//[3,7,1,4]console.log(queue.reverse());//[4,1,7,3]

 

자바스크립트 연결리스트 큐

자바스크립트에는 큐 내장 메서드가 없다. 배열과 push() shift() 로 큐 흉내를 낼 수 있다.

그러나 shift()의 경우 시간복잡도(O(n))나 성능이 좋지 않기 때문에 연결 리스트 객체로 구현하는게 좋다.

연결리스트를 사용할 경우 시간복잡도는 O(1) 시간에 해결할 수 있다.

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

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }

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

  enQueue(data) {
    const newNode = new Node(data);
    if (this.isEmpty()) {
      this.front = newNode;
    } else {
      this.rear.next = newNode;
    }
    this.rear = newNode;
    this.size++;
  }

  deQueue() {
    if (this.isEmpty()) {
      return null;
    }
    const data = this.front.data;
    this.front = this.front.next;
    this.size--;
    return data;
  }
}

 

재귀함수

자기 자신을 다시 호출하는 함수

예제 5-3

무한루프에 빠진다

const recursive = () =>{
	console.log('재귀 함수를 호출합니다.');
    recursive();
}

recursive();

 

예제 5-4. 재귀함수 종료 조건

const recursive = (i) =>{
	if (i===100) return;

	console.log(`${i}번째 재귀 함수에서 ${i+1}번째 재귀함수를 호출합니다.`);
    recursive(i+1);
    console.log(`${i}번째 재귀 함수를 종료합니다.`)
}

recursive(1);

 

예제 5-5. 팩토리얼

const factorialIterative = (n) => {
  let result = 1;
  for(let i = 2; i <= n; i++){
    result *= i;
  }
  return result;
}

const factorialRecursive = (n) => {
  if(n < 2) return 1;
  return n * factorialRecursive(n-1);
}

console.log(factorialIterative(5));
console.log(factorialRecursive(5));

 

재귀함수 내에서 특정 조건일 때 더이상 재귀적으로 함수를 호출하지 않고 종료하도록 if 문을 이용하여 꼭 종료 조건을 구현해주어야 한다.