[자료구조] 스택/큐

 

스택/큐

스택과 큐는 추상적 자료구조(Abstract Data Type)에 속한다.

이것은 자료구조의 방법이 코드로 정의된 것이 아니라 그 구조의 행동 양식만 정의된 것을 말한다.

스택과 큐는 배열을 기반으로 어떤 규칙을 설정한 것이라 할 수 있다.

 

스택은 배열이 수직으로 쌓여있는 식이라고 생각하면 된다.

배열에 어떤 요소를 추가하거나 배열에서 어떤 요소를 제거할 때는 맨 위에서부터 한다.

후입선출(Last In, First Out) 구조라고 할 수 있다. 

실생활의 예로는 웹페이지 뒤로가기 버튼을 누르는 것을 들 수 있다.

뒤로가기는 곧 히스토리 스택의 맨 위에서 한 페이지씩 가져가는 것이다.

Ctrl + Z로 최근의 실행 작업을 되돌리는 것도 스택 자료구조이다.

 

큐는 말 그대로 줄서기를 생각하면 된다.

가장 먼저 큐에 진입한 요소가 가장 먼저 나가게 된다.

선입선출(First In, First Out) 구조라고 할 수 있다.

예시로는 쇼핑몰의 선착순 주문 처리 같은 것을 생각할 수 있다.

 

문제 풀이

프로그래머스 - 같은 숫자는 싫어

문제 보기

function solution(arr)
{
    let stack = [];
    arr.forEach((target) => {
        if(target !== stack[stack.length -1]) stack.push(target)
    })
    return stack;
}

 

프로그래머스 - 올바른 괄호

문제 보기

function solution(s){
    //처음에 닫는 괄호이거나 끝에 여는 괄호면 false 리턴
    if(s[0] === ')' || s[s.length-1] === '(') return false
    let stack = []
    //배열의 마지막에 여는 괄호가 있고 현재 문자열이 닫는 괄호일 경우 스택에서 pop
    //아니면 스택에 넣기
    for(i=0; i<s.length; i++){
        if(s[i] === ')' && stack.at(-1) === '(') stack.pop()
        else stack.push(s[i])
    }
    return stack.length === 0;
}