Archive

03 스택(Stack)

7 min read

1. 스택(Stack)

1.1. 추상 자료형

  • 데이터
    • 후입선출(LIFO)의 접근 방법을 유지하는 요소들의 모음
  • 연산
    • init(): stack 초기화
    • is_empty()
      • 공백 상태에서 pop(), peek() → underflow 오류
      • ∴ 공백 상태이면 true 반환
    • is_full()
      • 포화 상태에서 push(e) → overflow 오류
      • ∴ 포화 상태이면 true 반환
    • push(e): top에 e 추가
    • pop(): top 꺼내서 반환
    • peek(): top 꺼내지 않고 반환

1.2. Time Complexity

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

1.3. Features

  • LIFO(Last-In First-Out)
    • top에서만 push, pop, peek가 발생하여

1.4. Applications

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

1.5. 교재에서 소개된 스택

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

2. 스택의 활용

  • 편집기에서 방금 처리한 작업을 취소하는 되돌리기
  • 웹 브라우저의 이전 페이지로 이동

2.1. 괄호 검사 알고리즘

  • 괄호를 저장할 스택을 사용한다.
  • 입력된 문자를 하나씩 읽는다.
    • 왼쪽 괄호를 만나면 스택에 삽입한다.
    • 오른쪽 괄호를 만나면 가장 최근에 삽입된 괄호를 꺼낸다.
      • 이때 스택이 비었다면 오른쪽 괄호가 먼저 나온 상황이므로 조건에 위배된다.
      • 꺼낸 괄호가 오른쪽 괄호와 짝이 맞지 않으면 조건에 위배된다.
  • 입력 문자열을 끝까지 처리한다.
    • 스택에 괄호가 남아 있으면 괄호의 개수가 같지 않으므로 조건에 위배된다.
    • 모든 문자를 처리하고 스택이 공백 상태이면 검사 성공이다.

2.2. 계산기 알고리즘

수식의 표현 방법전위(prefix)중위(infix)후위(postfix)
예 1+ A BA + BA B +
예 2+ 5 * A B5 + A * B5 A B * +

(1) 후위 표기식 계산 알고리즘

  • 수식을 저장할 스택을 사용한다.
  • 수식을 왼쪽에서 오른쪽으로 하나씩 읽는다.
    • 피연산자가 나오면 무조건 스택에 저장한다.
    • 연산자가 나오면 스택에서 피연산자 두 개를 꺼내 연산자를 실행하고 그 결과를 다시 스택에 저장한다.
  • 이 과정을 수식이 모두 처리될 때까지 반복하면 스택에 최종 계산 결과가 남는다.

(2) 중위 표기의 후위 표기식 변환 알고리즘

  • 중위 표기식을 순서대로 하나씩 스캔한다.

    • 피연산자를 만나면 바로 (후위 표기식으로) 출력한다.
    • 연산자를 만나면 스택에 잠시 저장해야 한다. (후위 표기식은 연산자가 피연산자 뒤에 나오기 때문에 적절한 위치를 찾을 때까지 출력을 보류하는 것이다.)

  • 연산자의 우선순위

    • 스택에 넣을 연산자보다 우선순위가 높은 연산자는 모두 먼저 출력한 후 현재 연산자를 스택에 넣는다.
    • 우선순위가 같은 연산자도 먼저 출력한다. 사칙 연산자는 모두 우선순위가 같으면 먼저 나온(왼쪽) 연산자부터 처리하기 때문이다.

  • 괄호의 우선순위

    • 왼쪽 괄호는 무조건 스택에 삽입한다. 스택에 삽입된 왼쪽 괄호는 제일 우선순위가 낮은 연산자로 취급한다. 즉, 다음에 만나는 어떤 연산자도 괄호 위에 삽입한다.
    • 오른쪽 괄호를 만나면 하나의 왼쪽 괄호가 삭제될 때까지 괄호 위에 쌓여있는 모든 연산자를 출력한다.

2.3. 시스템 스택

  • 시스템 스택

    • 운영체제에서 활성화 레코드를 저장하기 위해 사용한다.

    • 활성화 레코드(activation record)

      • 호출한 함수로 복귀했을 때 이전 상태를 손쉽게 복원할 수 있도록 한다.

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

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

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

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

  • 순환의 예

    • 순환 구조의 팩토리얼 함수
    • 하노이의 탑

(1) 하노이의 탑 알고리즘

  • A에 있는 n-1개의 원판을 C를 임시 막대로 이용해서 B로 이동
  • A에 남은 하나의 원판을 C로 이동
  • B에 있는 n-1개의 원판을 A를 임시 막대로 이용해서 C로 이동
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);
	}
}

그래프 뷰