Archive

03 Stack

8 min read

1. 스택

  • 스택(Stack)

    • 물건을 쌓아 올린 듯한 자료구조 (더미)

  • 특징: 후입선출(LIFO: Last-In First-Out)

    • 가장 나중에(최근에) 들어온 데이터가 가장 먼저 나가는 구조
    • top에서만 push, pop, peek가 발생하여

  • 구조

    • Top(상단): 데이터의 삽입과 삭제가 일어나는 위치
    • Bottom(하단): 스택의 가장 밑바닥

1.1. Time Complexity

  • Search: (LIFO 특성상 비효율적)
  • Insert/Delete:

1.2. Applications

  • 재귀, 백트래킹, 임시 저장 공간 등에서 사용
    • 함수 호출 스택
    • 백트래킹 알고리즘 (DFS, 퍼즐 문제 등)
    • 언어 처리기, 컴파일러 (괄호 검사, 수식 계산 등)
    • 웹 브라우저 뒤로 가기, undo 기능 등 이전 상태 복원

1.3. 교재에서 소개된 스택

  • 배열 구조의 스택
    • 스택 상단에 대한 인덱스를 별도로 저장

2. 스택의 추상 자료형 및 연산

  • 주요 연산

    • init(): 스택 초기화
    • push(e): 요소 e를 스택 맨 위(Top)에 추가 (삽입)
    • pop(): 스택 맨 위에 있는 요소를 꺼내서 반환 (삭제)
    • peek(): 스택 맨 위에 있는 요소를 삭제하지 않고 반환 (조회)
    • is_empty(): 스택이 비어있는지 검사 (True/False)
    • is_full(): 스택이 가득 찼는지 검사 (True/False)

  • 오류 상황

    • 오버플로(Overflow): 스택이 가득 찬 상태에서 데이터 입력을 시도할 때 발생
    • 언더플로(Underflow): 스택이 비어있는 상태에서 데이터 삭제(pop)나 조회를 시도할 때 발생

3. 배열을 이용한 스택 구현

  • 구조: 1차원 배열(data[MAX_SIZE])과 top 변수를 사용

  • Top의 초기값: -1 (스택이 비어있음을 의미)

  • 상태 검사

    • 공백 상태: top == -1
    • 포화 상태: top == (MAX_SIZE - 1)

  • 연산 동작 원리

    • Push: top을 1 증가시킨 후, 해당 인덱스에 데이터 저장 (data[++top] = e)
    • Pop: 현재 top 위치의 데이터를 반환하고 top을 1 감소 (return data[top--])

4. 스택의 활용 사례

스택은 자료의 순서를 뒤집거나, 되돌리기 기능 등에 주로 사용된다.

4.1. 기본 활용

  • 문자열 뒤집어 출력하기

    • 문자열을 순서대로 스택에 Push 한 뒤, Pop 하여 출력하면 역순이 된다.

  • 구조체 저장

    • 단순 데이터뿐만 아니라 구조체(예: 함수 호출 정보 등)도 스택의 요소로 저장할 수 있다.

4.2. 괄호 검사

소스 코드나 수식에서 괄호의 짝이 맞는지 검사하는 알고리즘

  • 검사 조건

    1. 왼쪽/오른쪽 괄호의 개수가 같아야 함
    2. 왼쪽 괄호가 오른쪽보다 먼저 나와야 함
    3. 서로 다른 괄호가 교차하여 쌍을 이루면 안 됨

  • 알고리즘

    • 왼쪽 괄호((, {, [)를 만나면 Push
    • 오른쪽 괄호(), }, ])를 만나면 Pop 하여 짝이 맞는지 검사
    • 문자열 끝까지 처리 후 스택이 비어있으면 성공, 남아있거나 중간에 짝이 안 맞으면 실패

4.3. 수식 계산기

컴퓨터가 수식을 계산하기 쉽게 하기 위해 후위 표기식(Postfix)을 사용한다.

  • 수식 표기법
    • 중위(Infix): A + B (사람이 사용)
    • 후위(Postfix): A B + (컴퓨터 및 스택 사용에 적합)
수식의 표현 방법전위(prefix)중위(infix)후위(postfix)
예 1+ A BA + BA B +
예 2+ 5 * A B5 + A * B5 A B * +

  • 후위 표기식의 계산

    • 피연산자(숫자)는 Push
    • 연산자를 만나면 피연산자 2개를 Pop 하여 계산 후, 결과를 다시 Push

  • 중위 표기식 → 후위 표기식 변환

    • 피연산자는 바로 출력
    • 연산자는 스택에 저장하되, 우선순위에 따라 처리 (스택 안의 연산자가 우선순위가 높거나 같으면 꺼내서 출력 후 현재 연산자 Push)
    • 오른쪽 괄호가 나오면 왼쪽 괄호가 나올 때까지 스택의 연산자를 모두 Pop 하여 출력

5. 시스템 스택과 순환 호출

5.1. 시스템 스택

  • 시스템 스택(System Stack)

    • 함수 호출 시 복귀 주소, 매개 변수, 지역 변수 등을 저장하는 메모리 공간
    • 함수가 실행되면 활성화 레코드(Activation Record)가 스택에 쌓이고, 함수가 종료되면 스택에서 제거되어 이전 함수로 돌아간다.

  • 활성화 레코드에 저장되는 정보

    • program counter: 호출된 함수가 종료되면 되돌아갈 프로그램의 위치
    • 매개변수
    • 지역변수

  • 시스템 스택을 사용하는 프로그래밍 기법

    • 순환(recursion): 어떤 함수가 자기 자신을 다시 호출하여 문제를 해결한다.

5.2. 순환

  • 순환(Recursion)

    • 어떤 함수가 자기 자신을 다시 호출하여 문제를 해결하는 기법

  • 구조

    • 문제를 더 작은 단위로 쪼개어 호출
    • 반드시 종료 조건(Base Case)이 있어야 함 (없으면 무한 루프)

  • 예제

    • 팩토리얼(Factorial): n! = n * (n-1)! (종료 조건: n=1일 때 1 반환)
    • 하노이의 탑(Hanoi Tower): 원판을 옮기는 문제를 재귀적으로 해결
      1. n-1개 원판을 임시 기둥으로 이동
      2. 가장 큰 원판을 목표 기둥으로 이동
      3. 임시 기둥의 n-1개 원판을 목표 기둥으로 이동
void hanoi_tower(int n, char from, char tmp, char to) {
	if (n == 1) printf("원판 1: %c --> %c\n", from, to);
	else {
		hanoi_tower(n - 1, from, to, tmp);
		printf("원판 %d: %c --> %c\n", n, from, to);
		hanoi_tower(n - 1, tmp, from, to);
	}
}

그래프 뷰