자료구조 - Stack / Queue

Song·2021년 11월 16일

bootcamp

목록 보기

5/11

자료구조란?

여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의하는 것.
다양한 데이터를 유용하게 사용하기 위해서는 데이터를 분석하고 활용할 수 있어야 한다. 또한 데이터를 사용하려는 목적에 맞게 분류하고 구분지어야 필요한 곳에 적절히 활용 가능하다.
스택,트리,큐 등과 같은 방식으로 데이터를 효율적으로 다루는 자료구조가 사용된다.
많은 자료구조를 익혀둘수록 문제해결에 적합한 해결방안을 찾기 수월해진다.

자료구조가 가지는 특징
자료구조를 사용하기 적합한 상황
자료구조의 작동원리 - 직접 구현
다른 자료구조와의 차이점

Stack

데이터를 순서대로 쌓는 선형(Linear)자료구조로 가장 나중에 들어온 데이터가 가장 먼저 나갈 수 있는(Last In First Out(LIFO)/First In Last Out(FILO)) 방식으로 데이터의 입출력이 한 방향으로만 흐른다.

직접 구현해보기

뒤로가기, 앞으로 가기 동작

수도코드로 표현을 해본다면,

function browser(동작, 시작페이지){
  let 현재페이지, 다음페이지 스택, 이전페이지 스택
  if(새로운 페이지 접속시){
    현재페이지를 이전페이지 스택에 보관,
    새로운 페이지를 현재페이지로 저장
  	}
  if(뒤로가기){
    현재페이지를 다음페이지 스택에 보관,
    이전페이지 스택에 있던 페이지를 불러와 현재페이지로 저장
     }
  if(앞으로 가기){
    현재페이지를 이전페이지 스택에 보관,
    다음페이지 스택 중 가장 위에 있던 페이지를 불러와 현재페이지로 저장
     }

}

실제 코드로 구현을 해보게 된다면 다음과 같다.

// actions = [A,-1,C,D,1,1,-1] , start = 'E'
//1은 앞으로 가기, -1은 뒤로 가기, 문자열은 접속한 페이지
function browser(actions, start) {
  let prev = [];	//뒤로가기에 필요한 stack
  let next = [];	//앞으로가기에 필요한 stack
  let prevTop = 0; 
  let nextTop = 0;
  let nowPage = start;

for(let i=0;i<actions.length;i++){
  //새로운 페이지로 접속할 경우 prev 스택에 원래 있던 페이지를 넣고 next 스택을 비웁니다.
  if(typeof(actions[i]) === 'string'){
    prev.push(nowPage);
    prevTop++;
    nowPage = actions[i];
    nextTop = 0;
    next = [];
  }
  // 뒤로 가기 버튼을 누를 경우 원래 있던 페이지를 next 스택에 넣고 
  //prev 스택의 top에 있는 페이지로 이동한 뒤 
  //prev 스택의 값을 pop 
  if(actions[i] === -1 && prevTop > 0){
    next.push(nowPage);
    nextTop++;
    prevTop--;
    nowPage = prev[prevTop];
    prev.pop();
  }
  //앞으로 가기 버튼을 누를 경우 원래 있던 페이지를 prev 스택에 넣고 
  //next 스택의 top에 있는 페이지로 이동한 뒤 
  //next 스택의 값을 pop
  if(actions[i] === 1 && nextTop > 0){
    prev.push(nowPage);
    prevTop++;
    nextTop--;
    nowPage = next[nextTop];
    next.pop();
  }
  //브라우저에서 뒤로 가기, 앞으로 가기 버튼이 비활성화일 경우(클릭이 되지 않을 경우)에는 스택에 push 하지 않음 (prevTop, nextTop이 0보다 작을 경우 스택에서 꺼내올 수 없음)

}
return [prev, nowPage, next]
}