스택(Stack)

스택은 가장 윗부분에만 자료의 추가와 삭제가 일어나는 자료구조이다. 때문에 실행속도가 빠르고 구현이 쉬운 효율적인 자료구조다. 수식평가에서부터 함수 호출까지 프로그래밍 언어 구현의 다양한 영역에서 스택이 사용되고 있다.

4.1스택의 동작

스택은 요소 리스트로 구성되며 top이라고 불리는 리스트의 한쪽 끝으로만 요소에 접근 할 수 있다. (LIFO 후입 선출 자료구조. 식당에 쌒아놓은 쟁반같다.) 그래서 스택의 밑바닥에 있는 요소에 접근하려면 모든 요소를 제거하는 수밖에 없다. 스택은 요소를 추가하거나 제거하는 두가지 동작을 제공한다. (push, pop)

탑요소의 위치와 새 요소를 추가할 위치는 top변수를 이용해 관리한다. 새요소를 스택에 추가했을 때는 top변수를 증가시키고, 스택의 요소를 제거했을 때는 top변수를 감소시킨다. 스택은 push,pop,peek외에도 다양한 기능과 프로퍼티가 있다. List에도 있었던clear,length프로퍼티들이 있고, peek를 사용하면 스택의 탑에 있는 요소를 제거하지 않고 내용만 확인할 수 있다. empty 프로퍼티는 스택에 요소가 있는지 여부를 알수있다.

4.2 스택구현

스택을 구현하려면 스택 요소를 내부적으로 저장할 자료구조를 결정해야 한다.

function Stack(){
    this.dataStore = []; //스택요소를 저장하는 배열
    this.top = 0; //스택의 탑 위치
    this.push = push;
    this.pop  = pop;
    this.peek = peek;
    this.length = length;
    this.clear = clear;
}
// 위 함수들(push,pop,peek)는 프로토타입으로 다시만든후 삭제한다.

push()함수를 구현한다. 새 요소를 현재 top 위치에 저장한 다음스택에 추가한뒤 빈공간을 새로운 탑이 가리키도록 top변수를 증가시킨다.

Stack.prototype.push = function(element){
    this.dataStore[this.top++] = element;
}

number++ 는 해당 위치(루프나 스코프?)에서 이전값으로 사용된후 증가한다.

++number 는 우선 증가된후 사용된다. 따라서 push에서 사용할경우 [undefined, element]가 될수 있기 때문에

number++ 를 사용한다.

pop()은 push()의 반대이다. top 요소를 반환한 다음 top변수를 감소시킨다.(실제로 dataStore에서 해당값을 빼버리진 않는다. 이상함.)

Stack.prototype.pop = function(){
    return this.dataStore[--this.top];
}

peek()함수는 배열의 top-1위치의 요소에 접근해 스택의 탑요소를 반환한다. 스택이 비어있을때(top이 0일때) peek()함수를 호출하면 undefined를 반환한다.

Stack.prototype.peek = function(){
    return this.dataStore[top-1];
}

스택에 얼마나 많은 데이터가 저장되어 있는지 알아야 할 때는 length()메서드를 사용한다.

Stack.prototype.length = function(){
    return this.top;
}

마지막으로 스택의 모든요소를 삭제하고 싶다면(top을 0으로 만들고 싶다면) clear()를 사용한다.

Stack.prototype.clear = function(){
    this.top = 0;
}

Stack 클래스 전체코드

function Stack(){
    this.dataStore = [];
    this.top = 0;
}

Stack.prototype.push = function(element){
    this.dataStore[this.top++] = element;
}

Stack.prototype.pop = function(){
    return this.dataStore[this.top--];
}

Stack.prototype.peek = function(){
    return this.dataStore[top-1];
}

Stack.prototype.length = function(){
    return this.top;
}

Stack.prototype.clear = function(){
    this.top = 0;
}

4.3 Stack 클래스 이용하기

4.3.1 진법변환

어떠한 진법에서 다른 진법으로 숫자를 변환할 때 스택을 이용할 수 있다. n이라는 숫자가 있고, b라는 진법으로 변환할 때 다음과 같은 알고리즘을 이용할 수 있다.

n의 가장 오른쪽 숫자는 n&b다. 이 값을 스택에 추가한다.
n을 n/b으로 치환한다.
n=0이 되고 나머지가 없을 때까지 1번, 2번 과정을 반복한다.
스택에 저장된 숫자를 모두 꺼내 변환된 숫자 문자열을 만든다.

이 알고리즘은 2진수부터 9진수 사이에서만 동작한다.

function mulBase(num, base){
    var s = new Stack();
    do {
        s.push(num % base);
        num = Math.floor(num /= base);
    }while(num>0);
    var converted = "";

    while(s.length() > 0){
        converted += s.pop();//첫값이 1일 경우. 즉, 홀수일경우 마지막에 1을 붙임. 짝수일경우 0
    }
    return converted;
}


var num = 9,
    base = 2,
    newNum = mulBase(num, base);
console.log(num + " converted to base " + base + " is " + newNum);

num = 125;
base = 8;

var newNum = mulBase(num, base);
console.log(num + " converted to base " + base + " is " + newNum);

9 converted to base 2 is 1001

125 converted to base 8 is 175

4.3.2 회문

스택을 이용해 어떤문자열이 회문¹인지 여부를 판단할 수 있다. 문자열을 받아 왼쪽에서 오른쪽으로 각 문자를 스택에 추가한다. 문자열을 끝까지 추가했다면 원래 문자열의 역순으로 위치한다. 이때 역순으로 바뀐 문자열과 원래 문자열을 비교하여 결과가 같으면 회문이다.

function isPalindrome(word){
  var s = new Stack();
  for(var i = 0; i < word.length; ++i){
    s.push(word[i]);
  }
  var rword = "";
  while (s.length() > 0){
    rword += s.pop();
  }
  if (word == rword) {
    console.log(word + " is a palinedrome.");
    return true;
  }else{
    console.log(word + " is not a palinedrome.");
    return false;
  }
}


var word = "hello";
isPalindrome(word);

word = "racecar"
isPalindrome(word);

4.3.3 재귀

스택을 이용해 재귀를 구현해보자.

재귀 함수

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

console.log(factorial(5)); // 120

스택을 이용한 재귀

function fact(num){
  var s = new Stack(),
      product = 1;

  while(num > 1){
    s.push(num--); //스택에 요소를 넣은다음 1씩 감소. 1은 저장할 필요없음. 곱할것이기 때문에
  }

  while(s.length() > 0){
    product *= s.pop(); //스택의 맨 위 값을 빼서 product변수와 반복하여 곱한다. (재귀적)
  }
  return product;
}

console.log(fact(5)); // 120

4장 스택