코딩 테스트 공부 : 스택/큐

개발자로 성장을 위해 프로그래머스 사이트를 이용하여 코딩 테스트 풀이를 꾸준히 하고 있다. 저번에 공부했던 해시 개념에 이어, 오늘은 스택/큐 개념에 대해 공부해보고자 한다.

스택(stack)?

스택 자료구조는 책을 쌓은 것처럼, 차곡차곡 쌓아 올린 형태의 자료구조를 의미한다.
LIFO(Last In First Out)으로 후입선출 구조이다.

스택의 특징

• 스택 내부의 데이터는 top을 통해서만 접근 가능하며, 여기서 top은 가장 최근(가장 마지막)에 들어온 자료를 의미한다.
• 스택에 데이터를 넣을 때에는, top 위에 쌓인다. (push)
• 스택에서 데이터를 삭제할 때에는, top에 위치한 데이터를 삭제한다. (pop)

스택 활용의 예시

• 웹 브라우저 방문 기록(뒤로 가기) : 가장 마지막에 열린 페이지부터 다시 보여준다.
• 실행 취소(undo) : 가장 마지막에 실행된 것부터 취소된다.
• 역순 문자열 만들기

등 LIFO에 해당되는 경우

큐(queue)?

큐는 줄을 서서 기다린다는 사전적 의미로, 먼저 들어온 게 먼저 나가는 FIFO(First In First Out) 자료 구조를 가진다.

큐의 특징

• 큐는 스택과 달리 삽입과 삭제가 다른 방향에서 이루어진다.
• 삭제 연산만 수행되는 곳을 front, 삽입 연산만 수행되는 곳을 rear라고 한다.
  (삭제 연산 : dnQueue / 삽입 연산 : enQueue)
• 가장 먼저 삽입된 데이터가 가장 먼저 삭제된다.

큐 활용의 예시

• 일상 생활에서, 줄을 서서 기다리는 모든 행동에 해당된다.
• 프로세스 관리
• 너비 우선 탐색(BFS-Breadth First Search) 구현
• 캐시 구현

<참고>
https://devuna.tistory.com/22

스택/큐 코딩 테스트 공부 : 프로그래머스 <기능 개발>

function solution(progresses, speeds) {
	// 남은 진행률 계산
    let lefts = progresses.map(v => 100-v)
    
    // 배포 완료까지 남을 일정 계산
    let leftDays = [];

        for(let i=0; i<speeds.length; i++){
            leftDays.push(Math.ceil(lefts[i]/speeds[i]))
        }
	
    // 첫 번쨰의 기능이 완료되고 배포가 되어야, 남은 순번의 기능이 배포될 수 있다.
    // 두 번째 기능이 먼저 완료되었다고 하더라도, 첫 번째 기능이 완료되지 않아 배포되지 않으면, 두 번째 기능을 배포할 수 없다.
    
    let answer = [0];
    let completeWork = leftDays[0]

        for(let i=0, j=0; i<leftDays.length; i++){
            if(leftDays[i] <= completeWork){
                answer[j] += 1
            } else {
                completeWork = leftDays[i]
                answer[++j] = 1
            }
    }
    return answer
}