Name	Name	Last commit message	Last commit date
parent directory ..
README.md	README.md
Stack.py	Stack.py

Stack (스택)

1. 개념 및 정의

1.1 스택이란?

스택(Stack)은 FILO(First In Last Out) 또는 LIFO(Last In First Out) 구조의 선형 자료구조입니다.

"쌓는다" = 나중에 넣은 것이 먼저 나온다

1.2 일상 속 스택의 예

예시	설명
접시 쌓기	가장 위에 쌓은 접시를 먼저 꺼냄
웹 브라우저 뒤로가기	가장 최근 방문 페이지로 이동
되돌리기 (Ctrl+Z)	가장 최근 작업부터 취소
함수 호출 스택	가장 마지막 호출된 함수가 먼저 반환

1.3 스택의 종류

종류	설명
배열 스택	배열(리스트)을 사용하여 구현
연결 스택 (Linked Stack)	연결 리스트를 사용하여 구현

2. 스택의 구조

2.1 Position (위치 포인터)

┌─────────────────────────────────────┐
│                                     │
│  ┌─────┐ ← top (현재 위치)          │
│  │  C  │   (인덱스 2)               │
│  ├─────┤                            │
│  │  B  │   (인덱스 1)               │
│  ├─────┤                            │
│  │  A  │   (인덱스 0)               │
│  └─────┘                            │
│   바닥 (Bottom)                     │
│                                     │
│  push: top이 먼저 증가 후 데이터 삽입│
│  pop: 데이터 제거 후 top 감소        │
│                                     │
└─────────────────────────────────────┘

2.2 top 포인터 동작 원리

상태	top 값	설명
빈 스택	-1	초기 상태, 데이터 없음
첫 번째 push 후	0	첫 번째 데이터 위치
두 번째 push 후	1	두 번째 데이터 위치
pop 후	top - 1	데이터 제거 후 감소

3. 주요 연산

3.1 연산 개요

연산	설명	Python 구현
push(data)	스택에 데이터 삽입	`stack.append(data)`
pop()	스택에서 데이터 제거 및 반환	`stack.pop()`
top()	현재 위치(인덱스) 반환	`len(stack) - 1`
peek()	맨 위 데이터 확인 (제거 안 함)	`stack[-1]`

3.2 push vs pop 동작

# push: 스택에 데이터 추가
# - top이 먼저 증가
# - 데이터가 들어옴
stack = []
stack.append('A')  # top: -1 → 0
stack.append('B')  # top: 0 → 1
stack.append('C')  # top: 1 → 2

# pop: 스택에서 데이터 제거
# - 데이터가 먼저 나감
# - top이 감소
stack.pop()  # 'C' 반환, top: 2 → 1
stack.pop()  # 'B' 반환, top: 1 → 0

3.3 pop() vs peek() 차이

연산	원본 데이터	반환값	사용 상황
pop()	삭제	제거된 데이터	데이터를 꺼내서 사용할 때
peek()	유지	맨 위 데이터	데이터를 확인만 할 때

stack = [1, 2, 3]

# peek: 확인만 (원본 유지)
top_value = stack[-1]  # 3, stack은 [1, 2, 3] 유지

# pop: 꺼냄 (원본에서 삭제)
top_value = stack.pop()  # 3, stack은 [1, 2]로 변경

4. 상태 확인 함수

4.1 isEmpty() - 스택이 비어있는지 확인

def isEmpty(stack):
    """스택이 비어있으면 True, 아니면 False"""
    return len(stack) == 0

# 사용 예시
stack = []
print(isEmpty(stack))  # True

stack.append(1)
print(isEmpty(stack))  # False

4.2 isFull() - 스택이 가득 찼는지 확인

max_size = 10

def isFull(stack):
    """스택이 가득 찼으면 True, 아니면 False"""
    return len(stack) == max_size

# 사용 예시
stack = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(isFull(stack))  # True

4.3 size() - 스택 크기 확인

def size(stack):
    """스택에 저장된 데이터 개수 반환"""
    return len(stack)

5. 구현 코드

5.1 옛날 패턴 (전통적 구현)

"""
전통적인 스택 구현
- 최대 크기 제한
- 상태 체크 함수 포함
- 안정성 높은 구현
"""

stack = []
max_size = 10

def isFull(stack):
    """스택이 가득 차 있는지 확인하는 함수"""
    return len(stack) == max_size

def isEmpty(stack):
    """스택이 비어 있는지 확인하는 함수"""
    return len(stack) == 0

def push(stack, data):
    """
    스택에 데이터를 추가하는 함수
    - 매개변수: stack(스택), data(추가할 데이터)
    - push 전에 isFull 검사 필수
    """
    if isFull(stack):
        print("스택이 가득 찼습니다!")
        return False
    else:
        stack.append(data)
        print(f"데이터 '{data}' push 완료")
        return True

def pop(stack):
    """
    스택에서 데이터를 꺼내는 함수
    - 매개변수: stack(스택)
    - pop 전에 isEmpty 검사 필수
    """
    if isEmpty(stack):
        print("스택이 비어있습니다!")
        return None  # None == Null
    else:
        return stack.pop()

def peek(stack):
    """스택의 맨 위 데이터를 확인하는 함수 (삭제 안 함)"""
    if isEmpty(stack):
        print("스택이 비어있습니다!")
        return None
    else:
        return stack[-1]

# 사용 예시
push(stack, 'A')  # 데이터 'A' push 완료
push(stack, 'B')  # 데이터 'B' push 완료
push(stack, 'C')  # 데이터 'C' push 완료

print(f"현재 스택: {stack}")       # ['A', 'B', 'C']
print(f"peek: {peek(stack)}")      # C
print(f"pop: {pop(stack)}")        # C
print(f"현재 스택: {stack}")       # ['A', 'B']

5.2 최근 패턴 (간결한 구현)

"""
현대적인 스택 구현
- 간결하고 직관적
- Python 리스트 메서드 활용
- 코딩테스트에 주로 사용
"""

stack = []

def push(stack, data):
    """스택에 데이터 추가"""
    stack.append(data)

def pop(stack):
    """스택에서 데이터 꺼내기"""
    if len(stack) == 0:
        return None
    return stack.pop()

def peek(stack):
    """스택 맨 위 데이터 확인"""
    if len(stack) == 0:
        return None
    return stack[-1]

def is_empty(stack):
    """스택이 비어있는지 확인"""
    return len(stack) == 0

5.3 클래스 기반 구현

"""
클래스를 사용한 스택 구현
- 객체지향적 접근
- 캡슐화로 데이터 보호
"""

class Stack:
    def __init__(self, max_size=None):
        self.items = []
        self.max_size = max_size

    def push(self, item):
        """데이터 삽입"""
        if self.max_size and len(self.items) >= self.max_size:
            raise OverflowError("스택이 가득 찼습니다")
        self.items.append(item)

    def pop(self):
        """데이터 제거 및 반환"""
        if self.is_empty():
            raise IndexError("스택이 비어있습니다")
        return self.items.pop()

    def peek(self):
        """맨 위 데이터 확인"""
        if self.is_empty():
            raise IndexError("스택이 비어있습니다")
        return self.items[-1]

    def is_empty(self):
        """비어있는지 확인"""
        return len(self.items) == 0

    def is_full(self):
        """가득 찼는지 확인"""
        if self.max_size is None:
            return False
        return len(self.items) >= self.max_size

    def size(self):
        """크기 반환"""
        return len(self.items)

    def __str__(self):
        """문자열 표현"""
        return str(self.items)

# 사용 예시
stack = Stack(max_size=5)
stack.push(1)
stack.push(2)
stack.push(3)
print(stack)         # [1, 2, 3]
print(stack.peek())  # 3
print(stack.pop())   # 3
print(stack)         # [1, 2]

5.4 코딩테스트용 초간단 구현

"""
코딩테스트에서 가장 자주 사용하는 패턴
- 별도 함수 없이 리스트 메서드 직접 사용
"""

stack = []

# push
stack.append(1)
stack.append(2)
stack.append(3)

# peek (확인만)
top = stack[-1]  # 3

# pop
value = stack.pop()  # 3

# is_empty 체크
if stack:  # 비어있지 않으면
    pass
if not stack:  # 비어있으면
    pass

# 길이 체크
if len(stack) == 0:
    pass

6. 실전 문제

6.1 문제 1: 괄호 짝 맞추기

문제 설명

소괄호는 짝을 맞춘 열린 괄호 "(" 와 닫힌 괄호 ")"로 구성되어 있다.
열린 괄호나 닫힌 괄호가 마구 뒤섞인 문자열이 주어진다.
이때, 소괄호가 정상적으로 닫혀있는지 판별하는 함수를 구현하시오.
만약 정상이면 True, 그렇지 않으면 False를 반환한다.

조건:
- 반드시 열린 괄호는 자신과 가장 가까운 닫힌 괄호를 만나면 상쇄
- 열린 괄호가 먼저 와야 함
- 상쇄할 괄호가 없을 때까지 반복

예시:
"(())()" → True
"(()" → False
"())(" → False

풀이 접근법

1. 열린 괄호 '('를 만나면 스택에 push
2. 닫힌 괄호 ')'를 만나면:
   - 스택이 비어있으면 → False (짝이 없음)
   - 스택에서 pop (짝 맞춤)
3. 모든 문자 처리 후 스택이 비어있으면 → True
4. 스택에 남아있으면 → False (열린 괄호가 남음)

정답 코드

def solution(st):
    """
    괄호 짝 맞추기

    Args:
        st: 괄호로 이루어진 문자열

    Returns:
        bool: 올바른 괄호면 True, 아니면 False
    """
    stack = []

    for c in st:
        if c == "(":
            # 열린 괄호: 스택에 push
            stack.append(c)
        elif c == ")":
            # 닫힌 괄호: 짝 확인
            if not stack:  # 스택이 비어있으면 짝이 없음
                return False
            else:
                stack.pop()  # 짝 맞춤

    # 스택이 비어있으면 모든 괄호가 짝이 맞음
    if stack:
        return False
    else:
        return True

# 테스트
print(solution("(())()"))  # True
print(solution("(()"))     # False
print(solution("())("))    # False
print(solution(""))        # True

한 줄로 간결하게

def solution(st):
    stack = []
    for c in st:
        if c == "(":
            stack.append(c)
        elif c == ")" and stack:
            stack.pop()
        elif c == ")":
            return False
    return len(stack) == 0

6.2 문제 2: 짝지어 제거하기 (프로그래머스)

문제 설명

알파벳 소문자로 구성된 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾는다.
짝을 찾은 다음에는 그들을 제거한 뒤 앞뒤로 문자열을 이어 붙인다.
이 과정을 반복하여 문자열을 모두 제거한다면 짝지어 제거하기가 성공한다.

문자열이 주어졌을 때 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 작성하시오.
성공하면 1, 실패하면 0을 반환한다.

예시:
"baabaa" → 1 (성공)
  baabaa → baa (aa 제거) → ba (aa 제거) → "" (bb가 아니므로)
  실제: baabaa → baa → b... (틀림)

  baabaa에서 가운데 aa 제거 → bbaa
  bbaa에서 bb 제거 → aa
  aa 제거 → "" (빈 문자열)
  → 성공!

"cdcd" → 0 (실패)
  연속된 같은 문자가 없어서 제거 불가

풀이 접근법

1. 문자를 하나씩 순회
2. 스택의 맨 위와 현재 문자가 같으면:
   - 스택에서 pop (짝 제거)
3. 다르면:
   - 스택에 push
4. 모든 문자 처리 후 스택이 비어있으면 → 성공(1)
5. 스택에 남아있으면 → 실패(0)

정답 코드

def solution(st):
    """
    짝지어 제거하기

    Args:
        st: 알파벳 소문자로 이루어진 문자열

    Returns:
        int: 성공하면 1, 실패하면 0
    """
    stack = []

    for c in st:
        # 스택이 비어있지 않고, 맨 위와 현재 문자가 같으면
        if stack and stack[-1] == c:
            stack.pop()  # 짝 제거
        else:
            stack.append(c)  # 다르면 push

    # 스택이 비어있으면 성공(1), 아니면 실패(0)
    return int(not stack)  # not []은 True → int(True)는 1

# 테스트
print(solution("baabaa"))  # 1
print(solution("cdcd"))    # 0
print(solution("aa"))      # 1
print(solution("aabb"))    # 1

동작 과정 시각화

입력: "baabaa"

단계별 진행:
┌────┬──────┬───────────────────────────────┐
│문자│스택  │동작                            │
├────┼──────┼───────────────────────────────┤
│ b  │ [b]  │스택이 비어있음 → push 'b'      │
│ a  │[b,a] │'b' != 'a' → push 'a'          │
│ a  │ [b]  │'a' == 'a' → pop (짝 제거)     │
│ b  │ []   │'b' == 'b' → pop (짝 제거)     │
│ a  │ [a]  │스택이 비어있음 → push 'a'      │
│ a  │ []   │'a' == 'a' → pop (짝 제거)     │
└────┴──────┴───────────────────────────────┘

결과: 스택이 비어있음 → 성공(1)

6.3 문제 3: 올바른 괄호 (다양한 괄호)

문제 설명

세 종류의 괄호 '()', '{}', '[]'가 섞인 문자열이 주어진다.
모든 괄호가 올바르게 짝을 이루는지 확인하시오.

예시:
"({[]})" → True
"({[}])" → False (짝이 맞지 않음)
"(((" → False (닫는 괄호 없음)

정답 코드

def solution(st):
    """
    다양한 괄호 짝 맞추기
    """
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}

    for c in st:
        if c in '({[':  # 여는 괄호
            stack.append(c)
        elif c in ')}]':  # 닫는 괄호
            if not stack:  # 스택이 비어있으면
                return False
            if stack[-1] != pairs[c]:  # 짝이 안 맞으면
                return False
            stack.pop()  # 짝이 맞으면 제거

    return len(stack) == 0

# 테스트
print(solution("({[]})"))  # True
print(solution("({[}])"))  # False
print(solution("((())"))   # False

6.4 문제 4: 주식 가격 (프로그래머스)

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때,
가격이 떨어지지 않은 기간은 몇 초인지를 return 하시오.

prices = [1, 2, 3, 2, 3]
return = [4, 3, 1, 1, 0]

설명:
- 1초 시점의 1은 끝까지 떨어지지 않음 (4초)
- 2초 시점의 2는 끝까지 떨어지지 않음 (3초)
- 3초 시점의 3은 1초 뒤에 떨어짐 (1초)
- 4초 시점의 2는 끝까지 떨어지지 않음 (1초)
- 5초 시점의 3은 0초간 유지 (0초)

정답 코드

def solution(prices):
    """
    주식 가격
    - 스택에는 아직 가격이 떨어지지 않은 시점의 인덱스를 저장
    """
    n = len(prices)
    answer = [0] * n
    stack = []  # 인덱스 저장

    for i in range(n):
        # 스택에 있는 시점보다 현재 가격이 낮으면 → 가격 하락
        while stack and prices[stack[-1]] > prices[i]:
            j = stack.pop()
            answer[j] = i - j  # 가격이 떨어지지 않은 기간
        stack.append(i)

    # 스택에 남아있는 것들은 끝까지 가격이 안 떨어진 것
    while stack:
        j = stack.pop()
        answer[j] = n - 1 - j

    return answer

# 테스트
print(solution([1, 2, 3, 2, 3]))  # [4, 3, 1, 1, 0]

7. 스택 문제 유형 정리

7.1 스택으로 풀어야 하는 유형

키워드	확률	설명
"짝 맞추기"	100%	괄호 검사, 짝지어 제거 등
"가장 가까운"	90%	가장 가까운 큰 수, 가장 가까운 작은 수
"최근"	90%	최근 데이터 접근, 되돌리기
"뒤집기"	높음	문자열 뒤집기, 순서 역전
"히스토리"	높음	방문 기록, 실행 취소

7.2 스택 문제 판별법

문제에서 다음 패턴이 보이면 스택을 고려하세요:

1. 짝(pair)을 맞춰야 하는 문제
   → 괄호 검사, 태그 매칭

2. 가장 최근/가까운 것을 찾는 문제
   → 가까운 큰 수, 히스토리 관리

3. 역순으로 처리해야 하는 문제
   → 문자열 뒤집기, 재귀 시뮬레이션

4. 후입선출(LIFO) 동작이 필요한 문제
   → 되돌리기(Undo), DFS 탐색

7.3 대표적인 스택 문제들

문제 유형	예시
괄호 검사	올바른 괄호, VPS 검사
짝 제거	짝지어 제거하기, 같은 문자 제거
히스토리	뒤로가기, 실행 취소
수식 계산	후위 표기식 계산
모노토닉 스택	주식 가격, 오큰수
DFS	깊이 우선 탐색 구현

8. 시간복잡도

8.1 스택 연산 시간복잡도

연산	시간복잡도	설명
push	O(1)	맨 뒤에 추가
pop	O(1)	맨 뒤에서 제거
peek	O(1)	맨 뒤 확인
isEmpty	O(1)	길이 확인
size	O(1)	길이 반환
search	O(n)	특정 요소 검색

8.2 공간복잡도

저장된 요소 수에 비례: O(n)

참고 자료

Python 리스트 스택 메서드 정리

메서드	스택 연산	설명
`list.append(x)`	push	맨 뒤에 추가
`list.pop()`	pop	맨 뒤 제거 및 반환
`list[-1]`	peek/top	맨 뒤 확인
`len(list)`	size	요소 개수
`not list` 또는 `len(list) == 0`	isEmpty	비어있는지 확인

주의사항

# 빈 스택에서 pop() 시 에러 발생
stack = []
stack.pop()  # IndexError: pop from empty list

# 항상 비어있는지 확인 후 pop
if stack:
    stack.pop()

# 또는 조건부로 처리
value = stack.pop() if stack else None

FilesExpand file tree

C_01_Stack

Directory actions

More options

Directory actions

More options

Latest commit

History

C_01_Stack

Folders and files

parent directory

README.md

Stack (스택)

목차

1. 개념 및 정의

1.1 스택이란?

1.2 일상 속 스택의 예

1.3 스택의 종류

2. 스택의 구조

2.1 Position (위치 포인터)

2.2 top 포인터 동작 원리

3. 주요 연산

3.1 연산 개요

3.2 push vs pop 동작

3.3 pop() vs peek() 차이

4. 상태 확인 함수

4.1 isEmpty() - 스택이 비어있는지 확인

4.2 isFull() - 스택이 가득 찼는지 확인

4.3 size() - 스택 크기 확인

5. 구현 코드

5.1 옛날 패턴 (전통적 구현)

5.2 최근 패턴 (간결한 구현)

5.3 클래스 기반 구현

5.4 코딩테스트용 초간단 구현

6. 실전 문제

6.1 문제 1: 괄호 짝 맞추기

문제 설명

풀이 접근법

정답 코드

한 줄로 간결하게

6.2 문제 2: 짝지어 제거하기 (프로그래머스)

문제 설명

풀이 접근법

정답 코드

동작 과정 시각화

6.3 문제 3: 올바른 괄호 (다양한 괄호)

문제 설명

정답 코드

6.4 문제 4: 주식 가격 (프로그래머스)

문제 설명

정답 코드

7. 스택 문제 유형 정리

7.1 스택으로 풀어야 하는 유형

7.2 스택 문제 판별법

7.3 대표적인 스택 문제들

8. 시간복잡도

8.1 스택 연산 시간복잡도

8.2 공간복잡도

참고 자료

Python 리스트 스택 메서드 정리

주의사항