[자료구조] 스택 - 정리 및 연습문제

이전 포스팅

1. [자료구조] 자료구조란 무엇인가? - 정리 및 연습문제
https://atoz-develop.tistory.com/entry/entry/자료구조-자료구조란-무엇인가-정리-및-연습문제

2. [자료구조] 배열 - 정리 및 연습문제
https://atoz-develop.tistory.com/entry/자료구조-배열-정리-및-연습문제

 

1. 스택(Stack)의 개념

스택은 이 동전 더미처럼 위로 쌓아올린 모습으로 표현할 수 있다.

- 스택은 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 추상 자료형이다.

- 가장 늦게 입력된 자료가 가장 먼저 출력되는 관계를 표현한다.

- LIFO(Last In First Out, 후입선출)

- 하나의 스택 포인터 변수(일반적으로 top으로 명명)를 사용한다.

- top은 스택의 삽입과 삭제가 일어나는 지점을 가리킨다.

- 삽입 시 top을 증가시키고 삭제 시 감소시킨다.

 

2. 스택의 추상 자료형(ADT)

* Object(객체)
0개 이상의 원소를 갖는 유한 순서 리스트

* Functions(연산)
stack∈Stack, item∈element, maxStackSize∈positive integer인 모든 stack, item, maxStack에 대하여 다음과 같은 연산이 정의된다. stack은 0개 이상의 원소를 갖는 스택, item은 스택에 삽입되는 원소, maxQueueSize는 스택의 최대 크기를 정의하는 정수이다.

① Stack CreateStack(maxStackSize) ::=
    스택의 크기가 maxStackSize인 빈 스택을 생성하고 반환한다;

② Boolean IsFull(stack) ::=
    if((stack의 element 개수) == maxStackSize))
    then { 'TRUE' 반환 }
    else { 'False' 반환 }

③ Stack Push(stack, item) ::=
    if(isFull(stack))
    then { 'stackFull' 출력 }
    else { 스택의 가장 위에 item을 삽입하고 스택을 반환한다; }

④ Boolean isEmpty(stack) ::=
    if(stack == CreateStack(maxStackSize))
    then { 'TRUE' 반환 }
    else { 'False' 반환 }

⑤ Element Pop(stack) ::=
    if(isEmpty(stack))
    then { 'stackEmpty' 출력 }
    else { 스택의 가장 위에 있는 element를 삭제하고 반환한다; }

 

3. 스택 연산 수행

① CreateStack(3);
② Push(stack, 'S');
③ Push(stack, 'T');
④ Pop(stack);
⑤ Push(stack, 'R');
⑥ Push(stack, 'P');
⑦ Push(stack, 'Q');
⑧ Pop(stack);

 

①~⑧ 연산 결과 (출처: 한국방송통신대학교)

 

4. 배열을 이용한 스택의 구현

다음은 C언어로 구현한 int형 스택이다.

 

4-1. 스택의 생성

#define STACK_SIZE 5
typedef int element;
element stack(STACK_SIZE);
int top = -1;

1라인: 스택의 사이즈를 정의한다.

2라인: int형을 스택 element의 자료형으로 정의한다.

3라인: 스택을 생성한다.

4라인: 스택의 top을 -1로 초기화하여 공백 상태로 한다.

 

스택 생성 결과

 

4-2. 스택의 삭제(pop)

element pop(int *top) {
    if(*top == -1) {
        printf("Stack is Empty\n");
        return 0;
    }
    else return stack[*top--];
}
 

2~4라인: 스택 공백 여부 확인 및 처리

6라인: *top이 가리키는 위치의 값을 return하고 *top을 1 감소시킨다. (순서 중요)

 

스택 삭제(pop) 결과

 

4-3. 스택의 삽입(push)

void push(int *top, element item) {
    if(*top >= STACK_SIZE -1) {
        printf("Stack is Full\n");
        return;
    }
    else stack[++*top] = item;
}
 

2~4라인: 스택 full 확인 및 처리

6라인: top의 주소값을 1 증가시키고 top이 가리키는 주소에 item을 저장한다. (순서 중요)

 

 

스택 삽입(push) 결과

5. 스택의 응용 분야

- 스택은 왔던 길을 되돌아 가는 경우에 많이 사용된다.

- 시스템 스택(system stack) : 변수의 메모리 할당과 수집. 즉 생명주기 관리

- 서브루틴 호출(subroutine call) 관리 : 서브루틴의 수행이 끝난 후에 되돌아갈 함수 주소를 저장

- 수식 계산 : 연산자들 간의 우선순위 결정

- 인터럽트(interrupt) : 프로그램 수행 중 발생되는 인터럽트의 처리와 되돌아갈 명령 수행 지점 저장

- 컴파일러 : 문법 검사

- 순환 호출(recursion call) 관리 : 순환 호출이 끝나고 되돌아갈 실행 주소 저장

 

 

6. 수식의 전위/후위/중위 표현

  연산자들 간의 우선순위를 결정하여 수식을 계산하는데 스택이 사용된다. 프로그램에서 수식을 입력받기 위해 사용될 수 있는 수식의 표기 방법은 연산자와 피연산자의 위치에 따라 다음의 세 가지가 있다.

 

• 중위 표기법(infix notation): 연산자를 피연산자의 사이에 표기하는 방법; A+B
• 전위 표기법(prefix notation, polish notation): 연산자를 피연산자의 앞에 표기하는 방법; +AB
• 후위 표기법(postfix notation): 연산자를 피연산자의 뒤에 표기하는 방법; AB+

후위 표기법이 컴퓨터로 처리되기에 효율적인 표기법이다.

 

  중위 표기법을 전위, 후위 표기법으로 변환하는 방법으로는 스택을 이용하는 방법과 트리를 이용하는 방법이 있다. 다음에서 전위 표기법으로의 변환 방법으로 트리를, 후위 표기법으로의 변환 방법으로 스택과 트리를 이용하는 방법을 다룰것이다.

 

변환할 식 : A/B+C

 

6-1. 중위 표기법 -> 전위 표기법 변환

① 주어진 식을 트리로 그린다.

 

A/B+C를 트리로 표현

  리프 노드에 피연산자 A, B, C를, 부모 노드에는 연산자를 우선순위 순서로 위치하도록 그린다. 위 그림을 보면 쉽게 이해할 수 있을 것이다.

 

② 트리를 전위(preorder) 순회하며 값을 출력한다.

트리의 전위 순회

   전위 순회는 그림과 같이 root → left → right 순으로 방문하는 방법이다. 위 트리를 전위 순회하면 출력 순서는 +/ABC가 되며 이것이 주어진 식 A/B+C의 전위 표기법으로 표현된 결과이다.

 

[중위 표기법] A/B+C → [전위 표기법] +/ABC

 

6-2. 중위 표기법 -> 후위 표기법 변환

6-2-1. 트리 이용

① 주어진 식을 트리로 그린다.

 

A/B+C를 트리로 표현

  동일하게 트리를 그린다.

 

② 트리를 후위(postorder) 순회하며 값을 출력한다.

트리의 후위 순회

  후위 순회는 그림과 같이 left → right → root 순으로 방문하는 방법이다. 위 트리를 후위 순회하면 출력 순서는 AB/C+가 되며 이것이 주어진 식 A/B+C의 후위 표기법으로 표현된 결과이다.

 

[중위 표기법] A/B+C → [전위 표기법] AB/C+

 

6-2-2. 스택 이용

① 주어진 식을 왼쪽에서 오른쪽 방향으로 읽는다.
② 피연산자는 스택에 저장하지 않고 바로 출력시킨다.
③ 연산자는 스택에 저장하나, 다음의 규칙을 따른다.
    - 새로 입력할 연산자(A)와 스택의 가장 위에 저장되어 있는 연산자(B)의 우선순위를 비교한다.
    - B가 A의 우선순위보다 높거나 같으면 B를 삭제하고 출력한다.
    - A가 B보다 우선순위가 높은 경우에만 바로 스택에 저장한다.

 

다음은 주어진 중위 표기식 A/B+C를 스택을 이용해 후위 표기식으로 변환하는 과정이다.

① 왼쪽에서부터 읽어 첫 번째 입력값(토큰)은 'A'이다. 피연산자는 스택에 저장하지 않고 바로 출력한다.

② 연산자 '/'는 스택에 저장한다. 스택이 비었으므로 비교할 연산자가 없다.

③ 피연산자 'B'는 스택에 저장하지 않고 바로 출력한다.

④ 연산자 '+'는 스택의 가장 위에 저장된 연산자 '/'보다 우선순위가 낮으므로 '/'를 삭제, 출력하고 '+'를 저장한다.

⑤ 연산자 'C'는 스택에 저장하지 않고 바로 출력한다.

⑥ 더 이상 입력값이 없으므로 스택을 차례로 삭제, 출력한다.

 

6-3. 후위 표기식의 계산 알고리즘 구현(C)

element evalPostfix(char *exp) {
    int oper1, oper2, value, i=0;
    int length = strlen(exp);
    char symbol;
    top = -1;
 
    for(i=0; i<length; i++) {
        symbol = exp[i];
        if(symbol != '+' && symbol != '-' && symbol != '*' && symbol != '/') {
            value = symbol - '0';
            push(value);
        }
        else {
            oper2 = pop();
            oper1 = pop();
            switch(symbol) {
                case '+': push(oper1 + oper2); break;
                case '-': push(oper1 - oper2); break;
                case '*': push(oper1 * oper2); break;
                case '/': push(oper1 / oper2); break;
            }
        }
    }
    
    return pop();
}
 

1라인: element evalPostfix(char *exp)

스택을 사용해 후위 표기식을 계산하는 함수를 evalPostfix라고 정의한다. 앞의 스택의 생성에서 typedef int element;로 정의한 스택 element 자료형을 반환한다. char형 포인터 매개변수로 수식이 저장된 배열을 가리키는 exp를 전달받는다. 계산할 후기 표기식은 369*+라고 가정한다.

 

수식이 저장된 배열의 모습

 

2라인: int oper1, oper2, value, i=0;

oper1, oper2 : 피연산자

value : 후위 표기식에서 char형으로 저장된 숫자를 int형으로 변환하여 저장

i : for문

 

3라인: int length = strlen(exp);

char형 포인터 매개변수로 전달받은 후위표기식 배열의 길이 저장한다. 배열의 길이만큼 반복 수행하기 위함이다. 현재 식이 '369*-'이므로 length에 5가 저장된다.

 

4라인: char symbol;

배열을 하나씩 읽어 저장할 변수

 

5라인: top = -1;

top 초기화

 

8라인: symbol = exp[i];

 

9라인: if(symbol != '+' && symbol != '-' && symbol != '*' && symbol != '/')

symbol이 연산자인지 확인

 

10라인: value = symbol - '0';

연산자이면 char를 int로 형변환하기 위해 '0'을 뺀 값을 저장

 

11라인: push(value);

연산자이면 스택에 저장

 

i=2까지 반복문이 실행됐을 때 배열과 스택

 

14~15라인: oper2 = pop(); oper1 = pop();

symbol이 연산자이면 스택에 저장돼있는 피연산자를 꺼내서 저장

 

16~20라인: switch(symbol)...

symbol이 연산자이면 해당하는 연산 수행하고 결과를 스택에 저장

 

i=3까지 실행됐을 때 배열과 스택

 

7라인: for(i=0; i<length; i++)

25라인: return pop();

i=5일때 배열과 스택. 반복문이 종료된다.

i가 5가 되면 반복문을 종료하고 스택에 저장되어 있는 결과값을 pop하여 반환하고 후위 표기식 계산 함수를 종료한다.

후위 표기식 369*+의 계산 결과는 57이다.

 

7. 연습문제

1. A*B+C를 후위 표기식으로 나타낸 것은?
① AB*C+
② ABC*+
③ AC*B+
④ AC+B*

2. 스택의 응용분야가 아닌것은?
① 시스템 스택
② 서브루틴 호출
③ 작업 스케줄링
④ 수식의 계산

3. 다음 문장의 옳고 그름을 결정하시오. (O, X)
스택의 추상 자료형에서 정의된 연산은 시스템 개발자에 따라 다르게 정의되고 구현될 수 있고, 컴파일러의 설계자에 따라 프로그래밍 언어에서 다르게 제공될 수 있다.

4. 다음 중 스택의 응용에 대한 설명이 아닌것은?
① 중앙처리 장치 할당을 위한 RR 기법
② 서브루틴의 수행이 끝난 후에 되돌아갈 함수 주소 저장
③ 프로그램에서 사용되는 변수들의 생명주기 관리
④ 연산자들 간의 우선순위에 의해 계산 순서가 결정되는 수식 계산

5. 다음은 스택의 연산들이다. ④를 수행한 결과는 무엇인가?

6. 다음 설명 중 가장 틀린 것은 무엇인가?
① 스택은 자료의 삽입과 삭제가 같은 변수를 통해 제어된다.
② 스택은 객체와 객체가 저장되는 순서를 기억하는 방법에 관한 추상자료형이다.
③ 스택의 크기는 가변적이다.
④ 후위 표기식은 연산자를 피연산자의 뒤에 표기하는 방법이다.

7. 다음은 스택의 연산들이다. ⑥을 수행한 결과는 무엇인가?

8. A+B+C*D를 전위 표기식으로 나타낸 것은?
① ++AB*CD
② ABCD++*
③ ++*ABCD
④ AB+B+C*

9. 다음은 스택에 대한 연산이다. ⑧ 연산을 수행한 후의 스택의 모습은 무엇인가?

10. 다음은 배열을 이용해 스택을 구현하고 스택에 데이터를 삽입하는 과정을 나타내는 코드이다. [가]에 들어갈 코드로 가장 알맞은 것은 무엇인가?

 

정답 ▼

1 : ①
2 : ③
3 : O
4 : ①
5 : ②
6 : ③
7 : ④
8 : ①
9 : ①
10 : ②