[알고리즘] 스택 Stack

스택 Stack

- 프링글스 과자통을 생각하자!!!!!! 

- 가장 마지막으로 들어간 데이터가 가장 첫번째로 나오는 성질을 가졌다. 그런 자료구조이다

 후입선출 last-in, first-out  LIFO 

- push로 추가, pop으로 제거

- pop으로도 스택의 top에 있는 요소를 확인할수있지만, pop은 스택에서 영구적으로 요소를 꺼낸다.

peek을 이용하면 top에 있는 요소를 제거하지 않고 내용만 확인할수있다.

- 탑 요소의 위치와 새 요소를 추가할 위치는 top변수를 이용해 관리한다.

- clear 프로퍼티는 스택의 모든 요소를 삭제한다.

-length 프로퍼티는 스택에 포함된 요소의 수를 저장한다.

-재귀, 진법변환, 회문 등에 이용된다.

 

function Stack(){
    this.dataStore = [];
    this.top = 0;
    this.push = push;
    this.pop = pop;
    this.peek = peek;
    this.clear = clear;
    this.length = length;
}

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

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

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

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

function length(){
    return this.top;
}

   

 

let s = new Stack();
s.push("D");
s.push("R");
s.push("B");
print("length: " + s.length());
print(s.peek());

 

---

재귀에서 사용한 예시를 보여주겠다

원래 이렇게 쓴다

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

 

스택을 이용하면

function fact(n){
    let s = new Stack();
    while (n>1){
        s.push(n--);
    }
    let product = 1;
    while (s.length()>0){
        product *= s.pop();
    }
    return product;
}

 

 

print(factorial(5));  //120출력
print(fact(5));  //120출력