스택 (Stack)

스택의 개념

• 스택은 LIFO(Last In Firtst Out - 후입선출) 원리에 따라 정렬된 컬렉션이다.

• 스택의 자료는 항상 동일한 종단점에서 추가/삭제된다.

• 스택은 책더미를 연상하면 된다.

스택 직접 구현

function stack() {
  const items = [];

  // push
  this.push = function (element) {
    items.push(element);
  };

  // pop
  this.pop = function () {
    return items.pop();
  };

  // peek
  this.peek = function () {
    return items[items.length - 1];
  };

  // isEmpty
  this.isEmpty = function () {
    return items.length === 0;
  };

  // size
  this.size = function () {
    return items.length;
  };

  // clear
  this.clear = function () {
    items = [];
  };

  // print
  this.print = function () {
    console.log(Number(items));
  };
}

• 오랜만에 다시 스택을 직접 구현해봤다. 내 기준에서 스택은 다른 자료구조에 비해 이해하기 쉬웠어서, 빠르게 작성할 수 있었다.

Stack 클래스 사용

const stack = new Stack();
console.log(stack.isEmpty()); // true

• 아직 추가한게 없으니 true가 나올 것이다.

stack에 push를 해줄 경우

stack.push(5);
stack.push(6);
stack.push(7);

console.log(stack.peek()); // 7

• 스택에 마지막으로 들어간 게 7이니까 7이 나온다.

stack에 pop을 해줄 경우

stack.pop();

console.log(stack.peek()); // 6

• 맨 위에 있던 7이 제거되서 6이 남는다.

10진수에서 2진수로 변환

• 위 그림은 10진수 233을 2진수로 변환하는 과정을 스택을 이용해 나타난 그림이다.

• 일반적으로 JS를 사용하는 사람들은 따로 구현을 해서 진수변환을 하는게 아니라, 아마 toString()을 사용할 것이다. - 나도 그렇다.

const dec = 233; 
const bin = dec.toString(2); // "11101001"

그렇다면 메소드를 사용하지 않고 직접 구현을 한다면?

function divideBy2(decNumber) {
  const remStack = new Stack();
  let rem; // 나머지
  let binaryString = ''; // 2진수

  while (decNumber > 0) {
    rem = Math.floor(decNumber % 2); // 나눗셈 몫이 0이 아닐 때까지
    remStack.push(rem); // 나머지(rem)를 스택에 밀어 넣고
    
    // 초기값 decNumber(여기서는 233)을 2로 나눈 '몫'으로 업데이트한다.
    decNumber = Math.floor(decNumber / 2); 
  }

  // remStack 배열(스택)이 텅 빌 때까지 원소를 pop 메소드로 꺼내어 문자열로 연결하면 2진수가 완성된다.
  while (!remStack.isEmpty()) binaryString += remStack.pop().toString();

  return binaryString;
}

• 위의 그림을 코드로 구현한 것이다.

결과를 확인해보면?

console.log(divideBy2(233)); // "11101001"

• 역시나 같은 결과를 얻을 수 있다.

다른 진법으로도 변환이 가능할까?

function baseConverter(decNumber, base) {
  const remStack = new Stack();
  let rem;
  let baseString = '';
  
  // 변경 부분!
  digits = '0123456789ABCDEF'; // 0~15까지를 나타내는 16진수의 숫자들

  while (decNumber > 0) {
    rem = Math.floor(decNumber % base);
    remStack.push(rem);
    decNumber = Math.floor(decNumber / base);
  }

remStack.print() // 9,15,7,8,1

  while (!remStack.isEmpty()) {
    baseString += digits[remStack.pop()]; // 변경 부분!
  }

  return baseString;
}
// 10진수 -> 16진수
console.log(baseConverter(100345, 16)); // 187F9

• 같은 원리다. 다만, 10진수를 2진수로 바꿀 때는 나머지가 0 아니면 1이었다. 8진수로 바꾼다면 나머지는 0~7이 될 것이고, 16진수라면 숫자 0~9에 문자 A~F(10~15에 해당)까지 필요하다.

• 따라서 이런 값들을 바꾸는 로직이 추가되어야 한다. (변경 부분!을 확인해보자)