[알고리즘] 스택 (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