[알고리즘] 스택 (Stack)

카테고리 : 알고리즘
태그: cs · 알고리즘 · algorithm · 자료구조 · 스택 · Stack · LIFO · 후입선출 · 10진수에서 2진수로 변환 · 진법 변환기

1. 스택

  • LIFO (Last In first Out) 원리에 따라 정렬된 컬렉션
  • 후입선출
  • ex) 책더미 , 푸드 코트 식판…
  • 변수 , 메소드 호출을 컴퓨터 메모리에 저장할 때 쓰임

2. 스택 만들기

1) 스택 클래스 생성

function Stack() {
  // property & method 기술하기
}

2) 스택의 원소를 담아둘 자료 구조

var item = [];

3) 스택에 필요한 메서드 정리

  • push(‘원소들’) : 스택 꼭대기에 원소 추가
  • pop() : 스택 꼭대기의 원소를 반환하고 해당 원소 제거
  • peek() : 스택 꼭대기의 원소를 반환하고 해당 원소 제거를 제거 하지 않음 ( 스택 변경 X)
  • isEmpty() : 스택 원소가 한개도 없으면 True / 스택 크기가 0보다 크면 False 반환
  • clear() : 스택의 모든 원소 삭제
  • size() : 스택의 원소 개수 반환

4) Stack 클래스

function Stack() {
  var items = [];

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

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

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

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

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

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

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

var stack = new Stack();
console.log(stack.isEmpty()); //outputs true
stack.push(5);
stack.push(8);
console.log(stack.peek()); //outputs 8
stack.push(11);
console.log(stack.size()); //outputs 3
console.log(stack.isEmpty()); //outputs false
stack.push(15);
stack.pop();
stack.pop();
console.log(stack.size()); //outputs 2
stack.print(); //outputs 5, 8
stack.clear();
console.log(stack.size()); //outputs 0
console.log(stack.isEmpty()); //outputs true

3. 스택 활용하기

1) 10진수 2진법 변환기

function Stack() {
  let items = [];

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

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

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

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

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

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

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

function divideBy2(decNumber) {
  let remStack = new Stack(),
    rem,
    binaryString = "";

  // 나눗셈 몫이 0이 아닐때 까지 반복
  while (decNumber > 0) {
    //2로 나눈 나머지를 스택에 추가
    rem = decNumber % 2;
    remStack.push(rem);
    //나눗셈의 몫을 정수형으로 반환해서 Math.floor 사용
    decNumber = ~~(decNumber / 2);
  }

  // 스택이 텅 빌때까지 스택에서 요소를 꺼내어 문자열로 연결
  while (!remStack.isEmpty()) {
    binaryString += remStack.pop().toString();
  }

  return binaryString;
}

console.log(divideBy2(233)); //11101001
console.log(divideBy2(10)); //1010

2) 진법 변환기

function Stack() {
  let items = [];

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

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

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

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

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

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

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

function baseConverter(decNumber, base) {
  let remStack = new Stack(),
    rem,
    baseString = "",
    digits = "0123456789ABCDEF";

  // 10진수를 2진수로 바꿀 땐 나머지가 0아니면 1
  // 8진수로 바꿀 땐 0~7
  // 16진수로 바꿀 땐 0~9, A~F
  while (decNumber > 0) {
    rem = ~~(decNumber % base);
    remStack.push(rem);
    decNumber = ~~(decNumber / base);
  }
  while (!remStack.isEmpty()) {
    baseString += digits[remStack.pop()];
  }

  return baseString;
}

console.log(baseConverter(233, 2)); //11101001
console.log(baseConverter(233, 8)); //351
console.log(baseConverter(233, 10)); //233
console.log(baseConverter(233, 16)); //E9