스택

 

스택을 배열로 구현 하였다. 이때에 배열의 선언을 type name[] 으로 하지 않고 type* name으로 하고 자유저장소에 할당을 sizeof(type)*capacity 만큼 해주었다.

 

여기에서 링크트리스트로 배열을 다시 구현 하게 되면 Node 구조체에서 데이터와 다음 노드의 주소 값을 저장 하도록 하고

stack 구조체 에서는 맨 처음의 Node*와 맨 마지막의(top) Node*를 저장한다. 따라서 push를 할때에 연결리스트에서의 append와 같은 형식으로 node를 추가 한 후에 top만 수정 해 준다. pop을 할 때에는 top node를 리턴하고, 새로운 top node를 저장해 준다.

 

ps. 후위 표기 식과 중위 표기식

 

중위 표기식은 우리가 일상생활에서 활용하는 일반 적인 표시이다.

후위 표기식은 스택을 활용할 때에 사용하는 것이다.. 

예를 들어 보자면 중위 : 1 + 2 /  33 - 9 * 13 후위 : 1 2 33 / + 9 13 * -

위 두 식은 결과 값이 같다. 후위 표기식은 연산자가 나올때에 스택에 쌍았던 두개의 수를 꺼내어 연산한 후에 다시 스택에 쌓는다.