[Stack] 쌓고 꺼내는 후입선출(LIFO) 자료구조

스택(Stack) 

프로그래밍에서 자료를 효율적으로 관리하고 처리하기 위해 다양한 자료구조가 사용됩니다. 그 중에서도 스택(Stack)은 가장 기본적인 자료구조 중 하나입니다. 스택은 데이터를 "쌓았다가 꺼내는" 방식으로 동작하는데, 마지막에 넣은 데이터가 가장 먼저 나오는(LIFO, Last-In-First-Out) 특성을 가지고 있습니다. 이 간단한 원리는 다양한 알고리즘 문제, 특히 괄호 검사, 문자열 처리, 수식 계산, 깊이 우선 탐색(DFS) 등에서 매우 중요한 역할을 합니다.

 

---

1.  스택(Stack)의 개념

스택은 마치 접시를 쌓는 것과 같습니다. 마지막에 올린 접시를 먼저 꺼내야 안전하죠!

스택은 한 쪽 끝에서만 데이터를 추가하거나 삭제할 수 있는 선형 자료구조입니다. 가장 나중에 들어간 데이터가 가장 먼저 나오는 후입선출(LIFO) 구조를 가지고 있습니다.

주요 연산

• push : 스택에 데이터 삽입
• pop : 스택에서 데이터 제거 및 반환
• peek 또는 top : 스택의 가장 위 데이터 조회
• isEmpty : 스택이 비어있는지 확인

 

---

2.  문제 예시 - 올바른 괄호

괄호로 이루어진 문자열이 주어졌을 때, 괄호의 열고 닫힘이 올바른지 판별하세요.

입출력 예시

입력	출력
"()"	true
"()[]{}"	true
"(]"	false
"([)]"	false
"{[]}"	true

문제 풀이 아이디어

• 여는 괄호((, {, [)를 만나면 스택에 push
• 닫는 괄호(), }, ])를 만나면 스택의 top 과 비교하여 짝이 맞으면 pop
• 짝이 맞지 않거나 스택이 비어있으면 false
• 문자열을 다 처리한 후, 스택이 비어 있으면 true

a.  Python

def isValid(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)

    return not stack

• mapping 딕셔너리로 여닫는 괄호를 매칭합니다.
• 스택이 비어있을 때 안전하게 비교하기 위해 # 사용합니다.
• 마지막에 스택이 비었는지 확인합니다.

b.  C++

#include <stack>
#include <unordered_map>
#include <string>
using namespace std;

bool isValid(string s) {
    stack<char> stack;
    unordered_map<char, char> mapping = {{')', '('}, {'}', '{'}, {']', '['}};

    for (char& ch : s) {
        if (mapping.count(ch)) {
            char topElement = stack.empty() ? '#' : stack.top();
            if (!stack.empty()) stack.pop();
            if (mapping[ch] != topElement) return false;
        } else {
            stack.push(ch);
        }
    }
    return stack.empty();
}

• unordered_map 을 사용해 괄호를 매칭합니다.
• stack<char> 사용합니다.
• 비어있을 때 안전 처리가 필요합니다.

c.  Java

import java.util.Stack;
import java.util.HashMap;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        HashMap<Character, Character> mapping = new HashMap<>();
        mapping.put(')', '(');
        mapping.put('}', '{');
        mapping.put(']', '[');

        for (char c : s.toCharArray()) {
            if (mapping.containsKey(c)) {
                char topElement = stack.isEmpty() ? '#' : stack.pop();
                if (mapping.get(c) != topElement) return false;
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}

• Java에서는 Stack 과 HashMap 모두 클래스로 제공합니다.
• 타입 명시가 필요합니다. (Character, String )

d.  JavaScript

function isValid(s) {
    const stack = [];
    const mapping = {
        ')': '(',
        '}': '{',
        ']': '['
    };

    for (const char of s) {
        if (mapping[char]) {
            const topElement = stack.length === 0 ? '#' : stack.pop();
            if (mapping[char] !== topElement) {
                return false;
            }
        } else {
            stack.push(char);
        }
    }
    return stack.length === 0;
}

• JavaScript는 배열(Array)로 스택을 대신 사용
• pop(), push() 메서드로 스택 기능 구현

 

---

3.  마무리

• 스택은 후입선출(LIFO) 구조로, 괄호 문제 같이 순서를 지켜야 하는 문제에서 자주 사용됩니다.
• Python, C++, Java, JavaScript 모두 스택을 쉽게 구현할 수 있는 기본 자료구조 또는 라이브러리를 제공합니다.
• 언어별 문법은 다르지만, 알고리즘의 핵심 논리는 동일합니다.

함께 하면 좋은 자료

블로그 글 :

[Queue] 줄 서서 처리하는 선입선출(FIFO) 자료구조

 

---