스택(stack)

스택(stack)이란?

- 스택은 한쪽 끝에서만 데이터를 넣고 뺄 수 있는 제한적으로 접근할 수 있는 후입선출(Last-In-First-Out) 형태의 선형 구조이다.

 

 

스택의 주요 연산

• Push: 데이터를 스택의 맨 위에 추가하는 연산
• Pop: 스택의 맨 위 데이터를 제거하고 반환하는 연산
• Peek(Top): 스택의 맨 위 데이터를 제거하지 않고 확인하는 연산
• isEmpty: 스택이 비어있는지 확인하는 연산 (boolean 타입을 반환)

 

스택의 구조

• Bottom: 가장 밑에 있는 데이터 또는 인덱스
• Top: 가장 위에 있는 데이터 또는 인덱스
• Capacity: 스택에 담을 수 있는 데이터의 총 용량
• Size: 현재 스택에 담겨져있는 데이터의 개수

 

스택의 동작원리

[초기 상태]
(Stack이 비어있음)

Push(1) → [1]
Push(2) → [1, 2]
Push(3) → [1, 2, 3]
Pop()   → [1, 2]  (반환값: 3)
Peek()  → [1, 2]  (반환값: 2)

 

스택의 활용 예시

• 함수 호출(재귀 호출): 함수가 호출될 때 실행 상태를 스택에 저장하고, 호출이 끝나면 스택에서 제거
• 웹 브라우저 뒤로 가기: 방문한 페이지를 스택에 저장하고, 뒤로 가기 시 최근 페이지를 제거
• 괄호 검사: 코드에서 괄호가 올바르게 닫혔는지 확인하는 데 사용
• DFS(깊이 우선 탐색): 그래프 탐색 알고리즘에서 활용

 

코딩 테스트에서 자주 나오는 예제

1. 올바른 괄호검사

function isValidParentheses(s) {
    const stack = [];
    const map = { ')': '(', '}': '{', ']': '[' };
    
    for (let char of s) {
        if (char in map) {
            if (stack.length === 0 || stack.pop() !== map[char]) {
                return false;
            }
        } else {
            stack.push(char);
        }
    }
    
    return stack.length === 0;
}

console.log(isValidParentheses("(){}[]")); // true
console.log(isValidParentheses("(]")); // false
console.log(isValidParentheses("({})")); // true

 

2. 다음 큰 요소 찾기 (Next Greater Element)

function nextGreaterElement(nums) {
    let stack = [], result = Array(nums.length).fill(-1);
    
    for (let i = 0; i < nums.length; i++) {
        while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    
    return result;
}

console.log(nextGreaterElement([2, 1, 2, 4, 3])); // [4, 2, 4, -1, -1]

 

스택의 장점과 단점

장점

• 구현이 간단하고 빠름 (O(1) 시간 복잡도로 Push, Pop 가능)
• 메모리 사용이 효율적 (필요할 때만 공간을 사용)

단점

• 한쪽 방향으로만 데이터 접근 가능 (LIFO 특성)
• 크기가 제한된 배열 기반 스택의 경우 오버플로(Overflow) 발생 가능

 

 

참고 자료

https://velog.io/@alkwen0996/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack