Stack Data Structure

About Stack

Stack은 단순하고 빠르며 가장 기초적인 자료 구조 이다.

Last in First Out : 마지막에 들어온 데이터가 처음으로 나가게 된다.

 

검은책부터 -> 빨 -> 녹 -> 검 -> 빨 순으로 책을 가져간다고 연상해볼수 있다.

ADT (Abstract Data Type)

methodname	contents
push(el)	스택의 마지막 위치에 데이터 삽입
pop()	스택의 마지막 위치 데이터 꺼냄(삭제)
peek()	스택의 마지막 위치에 있는 데이터 확인
clear()	스택 데이터 초기화
length()	스택의 크기

implementation

//ES6

class Stack {
    constructor() {
        this.storage = [];
    }

    push(el) {
        this.storage.push(el);
    }

    pop() {
        return this.storage.pop();
    }

    peek() {
        return this.storage[this.storage.length - 1];
    }

    clear() {
        this.storage = [];
        return console.log('storage initialization complete.')
    }

    length() {
        return this.storage.length;
    }
}

Exercise stack

1.진법변환

function BinaryConversion(num, base) {
    let         s = new Stack(),
        converted = '';

        do {
            s.push(num % base);
            num = Math.floor(num /= base);
        } while (num > 0);

        while (s.length() > 0) {
            converted += s.pop();
        }

    return converted;
}

2.회문검사

function isPalindrome(word) {
    let s = new Stack(),
        rword = '';

    for (let i = 0; i < word.length; ++i) {
        s.push(word[i]);
    }

    while (s.length() > 0) {
        rword += s.pop();
    }
    if (word === rword) {
        return true;
    } else {
        return false;
    }
}

3.재귀

function factorial(n) {
    if (n === 0){
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

4.표기법 전환(중위 -> 후위)

function() {
    ....
}

5.괄호 검사

function blockScopeCheck(modify){

    var m_stack = new Stack();
    var maps = { "(" : ") " , "[" : "]" , "{" : "}" };

    for( var i = 0 ;  i <modify.length; i++){
        if( modify[i] ==="(" || modify[i] ==="[" || modify[i] ==="{" ){
            m_stack.push( { type : modify[i] , index : i } );
        }else{
            var check  = m_stack.pop();
                if( modify[i] !== maps[check.type]){
                    return check.index;
                }
        }
    }

    if( m_stack.length() !== 0 ){
        return m_stack.peek() +" 닫는 괄호가 없습니다."
    }

    return "문제없음";

}

6.페즈 디스펜서

function candyShop(){

  var candykind = ['red','yellow','white'];
  var c_stack = new Stack();
  var n_stack = new Stack();
  var e_stack = new Stack();

    for ( var i = 0 ; i < 20 ; i ++){
        c_stack.push(candykind[Math.floor(Math.random() * 3)])
    }

    console.log("~before~ \n" + c_stack.dataStore);

    while(c_stack.length() > 0){
        if( c_stack.peek() ==='yellow'){
            c_stack.pop();
        }else{
            n_stack.push(c_stack.peek());
            c_stack.pop();
        }
    }
    //n_stack.dataStore.reverse(); //리버스를 사용하면 한방에 해결.
    while(n_stack.length() >0 ){
        e_stack.push(n_stack.peek());
        n_stack.pop();
    }

    console.log("~after~ \n" +e_stack.dataStore);

    return e_stack.dataStore;

}