자료구조 - 스택(Stack)

스택의 정의
 스택이란 여러 개의 데이타 항목들이 일정한 순서로 나열된 자료 구조로, 한쪽 끝에서만 새로운 항목을 삽입하거나 기존 항목을 삭제할 수 있도록 고안된 것이다.

스택의 성질

스택에 저장된 데이타 항목들 중에 먼저 삽입된 것은 나중에 삭제되고, 나중에 삽입된 것이 먼저 삭제된다. 그래서 스택을 후입 선출 리스트(Last- In-First-Out List)라고 부른다. 선입 선출법(FIFO)을 사용하는 큐와는 상반된 성질을 가진다.

스택의 구조

• 스택은 기저(base)로부터 데이타 항목들을 차례로 쌓아올린 모양을 가진다.
• 삽입과 삭제는 현재 저장된 최상위 항목이 위치한 top 에서만 일어난다.
• top 위치는 "스택 포인터"라는 지시자가 가리킨다.
• 스택 포인터는 스택 기저에서 시작하여 항목이 삽입되면 하나 증가하고, 삭제되면 하나 감소한다.
• 스택에는 한계가 있어서 그 한계를 초과하도록 삽입할 수 없다.

a. push

데이타 항목을 삽입하려면 스택 포인터를 하나만큼 증가시켜 주고 스택의 top 에 데이타 항목을 저장한다. 데이타 항목을 삽입하기 전에 새로운 항목을 저장할 빈 공간이 있는지 검사해야 한다.

if top ? n then overflow

  else top = top + 1

   stack(top) ← 삽입

b. pop

데이타 항목을 삭제하려면 스택의 top 에 있는 데이타 항목을 제거하고 스택 포인터를 하나만큼 감소시켜 준다. 데이타 항목을 삭제하기 전에 스택이 비어있는지를 검사해야 한다.

if top ? 0 then underflow

  else 삭제 ← stack(top)

   top = top-1

c. full

다음의 그림처럼 스택이 가득차 있으면 새로운 데이타 항목을 삽입할 수 없다. 데이타 항목을 삽입하기 전에 먼저, 스택 포인터가 스택의 한계에 도달해 있는지 검사해야 한다. Full은 다른 말로 Overflow라고 불린다.

d. empty

다음의 그림처럼 스택이 비어 있으면, 데이타 항목을 삭제할 수 없다. 데이타 항목을 삭제하기 전에 스택 포인터가 기저에 도달해 있는지를 검사해야 한다. Empty는 다른 말로 Underflow라고 불린다.

스택의 응용
서브루틴 호출, 순환 프로그램, 인터럽트 처리, 수식 표기, 0-주소, 컴파일러 등

예 ) 역 폴리시 기법에의 응용

산술식을 <피연산자-피연산자-연산자>로 표현하여 피연산자 뒤에 연산자가 따라 나오는 표현 방식으로 "역 폴리시(reverse-polish)" 표기법이라고 한다. 산술식에서 연산자 우선 순위에 따라 괄호를 먼저 한 후, 모든 연산자를 자신이 속한 바로 오른쪽 괄호의 밖으로 이동한 후 괄호를 없앤 표기법이다.

스택의 구조는 어떤 수식의 값을 구하는 데 있어 매우 효율적이다. 연산식의 구성에는 다음 세 가지 방법이 있다.

A+B : infix 개념

+AB : prefix(polish) 개념

AB+ : postfix(역polish) 개념

스택을 이용하여 산술식 계산을 하기 위한 절차는 다음과 같다.

1. 수식을 역polish 형태로 변환
2. 피연산자를 순서대로 스택에 push
3. 연산자가 나타나면 다음과 같은 마이크로 연산
   
   • 스택의 top에 있는 두 값이 연산에 사용된다.
   • 스택의 값이 pop되고 연산의 결과가 top의 아래에 있는 피연산자의 자리를 차지한다.

 예) (4*7)-(5+3) -> 역polish 형태: 47*53+-

 대학교 다닐때 처음으로 자료구조를 배우고 약 3년만에 다시 복습하는 마음가짐으로 내 블로그에 정리한다. 이자료는 http://internet512.chonbuk.ac.kr/datastructure/ 에서 구했고 추가로 도움이 될만한 정보를 정리할 생각이다.