[Algorithm] 웹 브라우저 앞으로 가기 뒤로 가기 구현하기

 

 

브라우저 앞으로 가기 뒤로가기

 

스택 알고리즘을 활용한 실예제 중 대표적인 것이 웹 브라우저 앞으로 가기와 뒤로 가기다. 웹 브라우저에서 앞으로 가기와 뒤로가기는 스택(Stack) 자료구조를 활용해서 구현되었다. 브라우저에서 앞으로 가기와 뒤로가기를 구현하기 위한 조건은 아래와 같다.

 

• 새로운 페이지에 접속하는 경우 pre 스택에 원래 페이지를 push하고 next 스택을 비워준다.
• 뒤로 가기 버튼을 클릭하는 경우 현재 페이지를 next 스택에 push 한다. pre 스택의 Top 위치에 있는 페이지를 pop하여 현재 페이지로 사용한다.
• 앞으로 가기 버튼을 클릭하는 경우 원래 페이지를 pre 스택에 push 하고 next 스택에서 pop하여 현재 페이지로 사용한다.
• 브라우저에서 앞으로 가기와 뒤로 가기 버튼이 비활성화 되어있는 경우 스택에 push 하는 작업을 생략한다.

 

예시

const actions = ["B", "C", -1, "D", "A", -1, 1, -1, -1];
const start = "A";
const output = browserStack(actions, start);

 

 

소스 코드 구현

 

브라우저 환경에서 앞으로가기와 뒤로가기를 구현하기 위해서는 2개의 스택이 필요하다. 기본적인 push와 pop, 그리고 size를 확인할 수 있는 class를 구현한다.

주어진 입력 배열을 순회하면서, 뒤로가기(-1)과 앞으로가기(1)인 경우 생성한 2개의 스택을 이용해서 push와 pop을 반복해서 구현한다. 

 

function browserStack(actions, start) {
  
    class Stack {
        constructor() {
        this.storage = [];
        this.top = 0; // 포인터 변수
        }

        // 스택 사이즈
        size() {
          return Object.keys(this.storage).length;
        }

        // 데이터 입력(Input)
        push(element) {
          this.storage[this.top] = element;
          this.top += 1;
        }

        // 데이터 출력(Output)
        pop() {
          if (this.top<=0) {
            return;
          }

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

          return result;
        }
  }
  const preStack = new Stack();
  const nextStack = new Stack();

  if(typeof start !== 'string') return false;

  let currentPage = start;
  
    for(item of actions){
         
        // 새로운 페이지 접속
        // pre 스택에 item을 push
        // next 스택을 비움
        if(typeof item === 'string'){
            preStack.push(currentPage);
            nextStack.storage = [];
            nextStack.top = 0;
            currentPage = item;  
        }

        // 뒤로가기
        // 현재 페이지를 next 스택에 push
        // pre 스택의 top 페이지로 이동
        // pre 스택의 값을 pop
        else if(item === -1 && preStack.top > 0){
            nextStack.push(currentPage);
            currentPage = preStack.pop();
        }

        // 앞으로 가기
        // 현재 페이지를 pre 스택에 push
        // next 스택의 top 페이지로 이동
        // next 스택의 값을 pop
        else if(item === 1 && nextStack.top > 0){
            preStack.push(currentPage);
            currentPage = nextStack.pop()
            

        }
    }

    return [preStack.storage.filter((item)=>item!==undefined || item!==null), currentPage, nextStack.storage.filter((item)=>item!==undefined || item!==null)];
  
  }

 

정리

 

브라우저에서 앞으로 가기와 뒤로 가기 구현은 스택의 개념만 이해하고 있다면 쉽게 풀 수 있는 문제다. 

 

스택의 구조

• 데이터 입출력 방향이 같다. 삽입과 삭제가 한 곳에서만 발생한다.
• 1개의 스택 포인터를 가진다. 가장 마지막에 삽입된 데이터의 위치를 가리키게 된다.
• 데이터가 push 될 때 마다 스택 포인터는 1씩 증가한다.
• 데이터가 pop 될 때 마다 스택 포인터는 1씩 감소한다.

 

 

 

[Algorithm] Data Structure and Algorithm Stack vs Queue