Chapter06 스택(Stack)

2017/12/21 - [프로그래밍/자료구조] - Chapter05 연결 리스트(Linked List) 3

06-1 스택의 이해와 ADT 정의

스택(Stack)의 이해

"먼저 들어간 것이 나중에 나온다!"

'후입선출 방식의 자료구조', 'LIFO(Last-In, First-Out) 구조의 자료구조'

실제로 스택은 쉽게 이해할 수 있고 또 쉽게 구현할 수 있는 자료구조이다.

다만, 스택! 하면 '스택의 활용' 혹은 '스택 기반의 알고리즘'과 관련된 전통적인 예가 하나 있는데, 이것이 의외로 간단하지 않다. 오히려 스택을 공부하는 것보다 이것을 경험하는데 더 많은 시간과 노력이 필요할 것이다.

스택 ADT의 정의

스택을 대표하는 넣고, 꺼내고, 들여다 보는 연산을 가리켜 각각 push, pop, peek이라 한다.

스택 자료구조의 ADT

void StatckInit(Stack *pstack);

- 스택의 초기화를 진행한다.

- 스택 생성 후 제일 먼저 호출되어야 하는 함수이다.

int SIsEmpty(Stack *pstack);

- 스택이 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환한다.

void SPush(Stack *pstack, Data data);

- 스택에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.

Data SPop(Stack *pstack);

- 마지막에 저장된 요소를 삭제한다.

- 삭제된 데이터는 반환이 된다.

- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

Data SPeek(Stack *pstack);

- 마지막에 저장된 요소를 반환하되 삭제하지 않는다.

- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

06-2 스택의 배열 기반 구현

배열 기반의 경우 간단하게 구현 가능

06-3 스택의 연결 리스트 기반 구현

"스택도 연결 리스트이다. 다만 저장된 순서의 역순으로 조회(삭제)가 가능한 연결 리스트일 뿐이다!"

06-4 계산기 프로그램 구현

계산기 구현에 필요한 알고리즘

수식의 표기법: 중위(infix), 전위(prefix), 후위(postfix) 표기법

계산기의 구현에 앞서, 중위 표기법의 수식을 전위 표기법 또는 후위 표기법의 수식으로 변환할 줄 알아야 한다.