자료구조 스택

해당 자료는 유튜브 신찬수 한국외대 교수님 강의를 시청하고 정리했으며
코딩테스트 합격자되기 자바스크립트편 도서를 읽고 추가적으로 정리되어 있습니다. 🙏🏻

Stack (스택)

• 삽입은 가장 아래부터 쌓이게 되고, 가장 맨 위에(마지막에 들어온) 있는 값이 가장 먼저 삭제된다. (LIFO)

스택의 연산

• 삽입: push
• 삭제: pop

강의 내에는 파이썬으로 작성되어있어,
해당 코드는 코딩테스트 합격자되기 도서를 참고해서 작성했습니다.

const stack = []; // 스택 초기화
const maxSize = 10; // 스택의 최대 크기

function isFull(stack) {
	return stack.length === maxSize;
}

function isEmpty(stack) {
	return stack.length === 0;
}

function push(stack, item) {
	if(isFull(stack)) {
    	console.log('가득 찼습니다');
    } else {
    	stack.push(item);
    }
}

function pop(stack){
	if(isEmpty(stack)) {
    	return null;
    } else {
    	return stack.pop();
    }
}

연산의 수행시간

• isFull : O(1)(상수 시간)
• isEmpty : O(1)
• push: O(1)
• pop: O(1)

스택 예제 1) 괄호 맞추기

(코딩테스트 합격자되기 도서 참고)

• 소괄호는 짝을 맞춘 열린 괄호''와 닫힌 괄호''로 구성
• 문제에서는 열린 괄호나 닫힌 괄호가 마국 뒤섰인 문자열을 준다.
• 이때 정상으로 열고 닫혔는지 판별하는 solution()함수 구현
• 정상적으로 열고 닫혔다면 true, 아니라면 false return

function solution(str) {
	cosnt stack = []; // 하나씩 담을 저장소 
    
    for(const s of str) {
    	if(s === '(') {
        	stack.push(s);
        } else if (s === ')') {
        	if(stack.length === 0) {
            	return false;
            } else {
            	stack.pop();
            }
        }
    }
    
    return stack.length === 0;
}

• 열린 괄호 '('는 언젠가는 닫혀야 하는 괄호이므로 스택에서 기다리게 할 것.
• 닫는 괄호 ')'는 앞에서 열린 게 있어야 닫을 수 있으니까 스택에서 마지막에 연 괄호를 pop해서 짝을 맞추는 역할

case1 '('가 먼저 있다 => stack에 push
case2 ')'가 왔고 스택이 비어있다? => 바로 false => 예) ')('
case3 ')'가 왔고, 스택이 비어있지 않다 => '('는 있을테니까 열고 닫히게 되었으므로 stack pop!