Stack

Stack 개념

후입선출 (Last In First Out) 또는 선입후출 ( First In Last Out ) 의 선형 자료 구조

특징

1. LIFO 구조로 제일 먼저 들어간 데이터 제일 나중에 나오는 후입선출의 구조

2. 데이터를 하나씩만 넣고 뺄 수 있다.

3. 하나의 입출력 방향을 갖고 있다.

사용 사례

• 재귀 알고리즘

• 웹 브라우저 방문기록

• 실행 취소

• 역순 문자열 만들기

• 수식의 괄호 검사

• 후위 표기법 계산

코드로 Stack 구현

class Stack {
  constructor() {
    this.storage = {};
    this.top = 0; // 스택의 가장 상단을 가리키는 포인터 변수를 초기화 합니다.
  }

  size() {
    return this.top;
  }

	// 스택에 데이터를 추가 할 수 있어야 합니다.
  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  }
	
	// 가장 나중에 추가된 데이터가 가장 먼저 추출되어야 합니다.
  pop() {
    // 빈 스택에 pop 연산을 적용해도 에러가 발생하지 않아야 합니다
    if (this.top <= 0) {
      return;
    }

    const result = this.storage[this.top - 1];
    delete this.storage[this.top - 1];
    this.top -= 1;
    
    return result;
  }
}

stack을 이용하여 앞으로가기 뒤로가기 구현

문제

개발자가 되고 싶은 김코딩은 자료구조를 공부하고 있습니다. 인터넷 브라우저를 통해 스택에 대해 검색을 하면서 다양한 페이지에 접속하게 되었는데 "뒤로 가기", "앞으로 가기"를 반복하면서 여러 페이지를 참고하고 있었습니다.

그런데 새로운 페이지를 접속하게 되면 "앞으로 가기" 버튼이 비활성화돼서 다시 보고 싶던 페이지로 갈 수 없었습니다. 이러기를 반복하다가 김코딩은 스택 자료구조를 떠올리게 되었습니다.

브라우저에서 "뒤로 가기", "앞으로 가기" 기능이 어떻게 구현되는지 궁금해진 김코딩은 몇 가지 조건을 아래와 같이 작성하였지만, 막상 코드를 작성하지 못하고 있습니다.

조건

1. 새로운 페이지로 접속할 경우 prev 스택에 원래 있던 페이지를 넣고 next 스택을 비웁니다.

2. 뒤로 가기 버튼을 누를 경우 원래 있던 페이지를 next 스택에 넣고 prev 스택의 top에 있는 페이지로 이동한 뒤 prev 스택의 값을 pop 합니다.

3. 앞으로 가기 버튼을 누를 경우 원래 있던 페이지를 prev 스택에 넣고 next 스택의 top에 있는 페이지로 이동한 뒤 next 스택의 값을 pop 합니다.

4. 브라우저에서 뒤로 가기, 앞으로 가기 버튼이 비활성화일 경우(클릭이 되지 않을 경우)에는 스택에 push 하지 않습니다.

function browserStack(actions, start) {
    // TODO: 여기에 코드를 작성합니다.
    if(typeof start !== 'string') return false;
    let pre = [];
    let now = start;
    let next = [];
 
    for(let action of actions){
        if(typeof action === "string"){
            if(now[0] !== action){
                next = [];
                pre.push(now);
                now = action;
            }
        }else if(typeof action === 'number'){
            switch (action){
                case -1:
                  if(pre.length > 0){
                    next.push(now);
                    now = (pre.pop());
                    break;
                  }else{
                    break;
                  } 
                case  1:
                  if(next.length > 0){  
                    pre.push(now);
                    now = (next.pop());
                    break;
                  }else{
                    break;
                  }  
            }
        }
    }
    return [pre, now, next]
  }