스택

학습목표

1. 스택의 추상 자료형을 이해한다.

2. 스택의 삭제 연산과 삽입 연산에 대해서 이해한다.

3. 스택을 이용한 사칙연산의 계산 방법을 이해한다.

4. 사칙연산의 전위 표기법, 후위 표기법, 중위 표기법을 이해한다.

 

1. 스택의 개념

스택의 정의

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

  : 가정 먼저 입력된 자료가 가장 나중에 출력되는 관계를 표현함

- 0개 이상의 원소를 갖는 유한 순서 리스트

- push(add)와 pop(delete)연산이 한곳에서 발생되는 자료구조

 

 

 

 

2. 스택의 추상 자료형 

CreateS 연산

- Stack CreateS (maxStackSize)

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

 

Push연산

ElementPush(stack,item)::=
  if(IsFull(stack))
    then{‘stackFull’을 출력한다;}
      else{스택의 가장 위에 item을 삽입하고, 
           스택을 반환한다;}

Pop연산

ElementPop(stack)::=
  if(IsEmpty(stack))
   then{‘stackEmpty‘을 출력한다;}
    else{
     스택의 가장 위에 있는 원소(element)를
     삭제하고 반환한다; 
   }

 

 

3. 스택의 응용

스택의 다양한 응용

- 변수에 대한 메모리의 할당과 수집을 위한 시스템 스택

- 서브루틴 호출 관리를 위한 스택

- 연산자들 간의 우선순위에 의해 계산 순서가 결정되는 수식 계산

- 인터럽트의 처리와,이후 리턴할 명령 수행 지점을 저장하기 위한 스택

- 컴파일러,순환 호출 관리

 

 

4. 스택의 연산

스택의 삭제 연산

- ‘top--’에서 사용된 ‘--’연산자의 위치에 따라 연산의 적용순서가 달라질 수 있음

 

 

스택의 생성

#define STACK_SIZE 10
typedef int element;
element stack[STACK_SIZE];
int top = -1;

 

스택의 삭제 연산

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

 

스택의 삽입 연산

voidpush(elementitem){//스택의 삽입 연산,item=400
	if(top>=STACK_SIZE-1){//스택이 이미 FULL인 경우
		printf(“StackisFull!!\n”);
		return;
	}
	else
		stack[++top]=item;
}

 

 

5. 사칙연산식의 전위/후위/중위 표현

수식의 계산

- 연산자의 계산순서를 생각해야 함

ex) A+B*C+D

→ ((A+(B*C))+D)

 

수식의 표기 방법

 

중위 표기법(infixnotation)

- 연산자를 피연산자 사이에 표기하는 방법

- A+B

 

전위 표기법(prefixnotation)

- 연산자를 피연산자 앞에 표기하는 방법

- +AB

 

후위 표기법(postfixnotation)

- 연산자를 피연산자의 뒤에 표기하는 방법

- AB+ 

 

 

중위 표기식의 후위 표기식 변환 방법

- 먼저 중위 표기식을 연산자의 우선순위를 고려하여(피연산자,연산자,피연산자)의 형태로 괄호로 묶어줌

- 각 계산뭉치를 묶고 있는 괄호 안에서 연산자를 계산뭉치의 가장 오른쪽으로 이동시킴

- 각 계산뭉치를 하나의 피연산자로 고려하여 위를 반복함

- 괄호를 모두 제거함

후위 표기식(369*+) 을 계산하는 연산

element evalPostfix(char *exp) {
	int oper1, oper2, value, i=0;
	int length = strlen(exp);
	char symbol;
	top = -1;