1. 스택 ADT

스택이란?

스택을 영어사전으로 찾아보면 '(건초, 밀집 따위를 쌓아 놓은) 더미, 낟가리'를 의미한다

식당에 쌓여있는 접시 더미, 책상에 쌓여있는 책, 창고에 쌓여있는 상자 등이 스택의 전형적인 예이다.

 

입출력 형태 : 후입선출 (LFO : Last-In First-Out)

창고에서 새로운 상자들을 쌓을 때는 상자더미의 맨 윗부분에 놓는다. 상자가 필요하면 상자더미의 맨 위에 있는 상자를 꺼낸다. 따라서 가장 최근에 들어온 상자가 가장 위에 있고, 또 먼저 나가게 된다. 

 

스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다.

스택 상단 (stack top)

: 스택에서 입출력이 이루어지는 부분

 

스택 하단 (stack bottom)

: 반대쪽인 바닥 부분

 

요소 (element)

: 스택에 저장되는 것

 

공백 스택 (empty stack)

: 요소가 하나도 없을 때의 스택 상태

 

*스택은 특히 자료의 출력순서가 입력순서의 역순으로 이루어져야 할 경우에 매우 긴요하게 사용된다

ex) A,B,C,D,E => E,D,C,B,A

---

스택의 추상 자료형

추상 자료형으로서의 스택은 0개 이상의 요소를 가지는 선형 리스트의 일종으로 정의되며 스택에 요소를 추가하거나 삭제하는 연산과 현재 스택 상태를 검사하는 연산들로 구성된다

 

스택의 두 가지 기본 연산

: 삽입 연산 (push 연산), 삭제 연산 (pop 연산)

• is_empty : 스택이 공백 상태에 있는지 검사하는 함수
• is_full : 스택이 포화 상태에 있는지 검사하는 함수
• create : 스택을 생성
• push(A) : 비어 있는 스택에 A가 삽입
• push(B) : B가 A위에 쌓임
• push(C) : C가 B위에 쌓임
• pop() : 가장 위에 쌓여있는 C가 삭제
• peek : 요소를 스택에서 삭제하지 않고 보기만 하는 연산

 

push 오류

: 스택이 가득차서 입력이 불가능하다면 오류 발생

 

pop 오류

: 스택에 데이터가 없어서 출력이 불가능하다면 오류 발생

---

스택의 활용 예

ex) 시스템 스택을 이용한 함수 호출

컴퓨터 안에서는 수많은 함수 호출이 이루어지는데, 함수는 실행이 끝나면 자신이 호출한 함수로 되돌아가야 하고 이때 스택이 사용된다. 즉 스택은 복귀할 주소를 기억하는데 사용된다

 

활성 레코드 (activation record)

: 시스템 스택에는 함수가 호출될 때마다 활성 레코드가 만들어지며 복귀 주소가 저장된다

시스템 스택에는 다음과 같은 순서로 활성 레코드가 만들어졌다가 없어지게 된다

---

스택을 구현 방법

배열을 이용하는 방법

: 간단하고 성능이 우수한 반면, 스택의 크기가 고정되는 약점이 있음

 

연결 리스트를 이용하는 방법

: 구현이 약간 복잡한 반면, 스택의 크기를 필요에 따라 가변적으로 변동 가능

=> 포인터를 이용해야 함