3강. 스택

학습개요

스택은 입출력 순서를 중심으로 자료들 간의 관계가 성립되는 자료구조입니다. 즉, 입력이 가장 늦게 된 자료가 가장 먼저 출력되는 관계를 표현합니다. 그렇기 때문에 스택은 왔던 길을 되돌아가는 경우에 많이 사용되고, 예전에 처리했던 값들을 역순으로 되돌아가며 찾아내서 처리해야 하는 경우에 많이 사용됩니다.

스택 구조는 입력 연산을 수행하기 전에 정의된 스택의 크기를 항상 확인해야 합니다. 스택의 크기보다 더 많은 자료를 입력하면 에러가 발생하기 때문입니다. 그리고 삭제 연산을 수행하기 전에 스택에 삭제할 자료가 남아 있는지를 확인해야 합니다. 마지막으로 스택을 이용한 사칙 연산식의 계산을 보여드립니다. 컴퓨터에서 처리되어야 할 사칙연산을 위해 사용되는 스택을 설명하면서, 연산자의 우선순위를 고려한 연산자들의 삽입 연산과 삭제 연산이 이루어지는 내용을 보여드립니다.

학습목표

1. 스택의 추상 자료형을 이해할 수 있다.
2. 스택의 삭제 연산과 삽입연산에 대해서 이해할 수 있다.
3. 스택을 이용한 사칙연산의 계산 방법을 이해할 수 있다.
4. 사칙연산의 전위 표기법, 후위 표기법, 중위 표기법을 이해할 수 있다.

연습문제

1. A*B+C
   1. 지문의 수식을 후위 표기식으로 바르게 나타낸 것은 ?
      1. AB*C+
      2. ABC*+
      3. AC*B+
      4. AC+B*
         –
2. 스택의 응용 분야가 아닌 것은 ?
   1. 시스템 스택
   2. 서브루틴 호출
   3. 작업 스케쥴링
   4. 후위 수식의 계산
      –
3. 스택의 추상 자료형에서 정의된 연산은 시스템 개발자에 따라 다르게 정의되고 구현될 수도 있고, 컴파일러 설계자에 따라 프로그래밍 언어에서 다르게 제공될 수도 있습니다.
   1. O
   2. X

정리하기

1. 스택을 생성하는 연산은 프로그래머가 지정한 크기의 새로운 스택을 생성하는 연산이며, 매개변수인 maxStack은 스택이 저장할 수 있는 최대 개수의 element를 의미합니다.
2. StackIsFull(stack, maxStackSize) 연산은 스택이 가득 찼는지를 확인하며, 저장된 원소의 수가 maxStackSize와 같으면 TRUE(‘스택이 가득 찼다’)를 반환하고 아니면 FALSE(‘스택에 여유 저장 공간이 있다’)를 반환합니다.
3. Stack Push(stack, item) 연산은 스택에 새로운 원소를 삽입합니다. 만일 스택이 가득 찼다(Full)면 더 이상의 원소를 스택에 삽입할 수 없으며, ‘stackFull‘ 메시지를 출력합니다.
4. Boolean StackIsEmpty(stack) 연산은 스택 상태가 빈 상태인지를 확인합니다. 만일 스택이 빈 상태이면 ‘TRUE’ 값을 반환하고, 스택에 하나 이상의 원소라도 있다면 ‘FALSE’ 값을 반환합니다.
5. Element Pop(stack) 연산자는 스택이 빈 상태라면 삭제할 원소가 없으므로 ‘stackEmpty‘를 출력합니다. 하지만, 빈 상태가 아니라면 삭제할 원소가 있으므로, 스택의 top이 가리키는 원소를 삭제하고 그 원소를 반환합니다.
6. 스택의 추상 자료형에서 정의된 연산은 시스템 개발자에 따라 다르게 정의되고 구현될 수도 있고, 컴파일러 설계자에 따라 프로그래밍 언어에서 다르게 제공될 수도 있습니다.
7. 스택은 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 추상 자료형입니다.
8. 중위 표기법(infix notation)은 연산자를 피연산자의 사이에 표기하는 방법이며 일반적으로 가장 많이 사용되는 표기 방법(A+B)입니다.
9. 전위 표기법(prefix notation)은 연산자를 피연산자의 앞에 표기하는 방법 (+AB)입니다.
10. 후위 표기법(postfix notation)은 연산자를 피연산자의 뒤에 표기하는 방법 (AB+)입니다.