Stack 스택_연결리스트 구현

Stack 스택

스택,큐,트리와 같은 자료 구조는 자신이 행위적 측면을 포함하는 구조이다.

스택은 밑이 막힌 긴 통이라 생각하고 입,출구가 하나인 과자통을 생각하면 쉽다(프링글스)

 먼저 들어간 것은 가장 나중에 빠져 나오게 된다. (후입선출)LIFO

반대로 가장 늦게 들어간 데이터가 가장 먼저 빠져나가게 되는 것이다.

스택에는 구현방법이 배열구현과 리스트구현 두가지가 있다.

배열은 처음 배열의 크기를 설정해두고 시작해야 하기 때문에 나중에 배열의 크기를 변경 할 수 없는 반면에 리스트구현은 동적인 할당을 통해서 구현되기 때문에 연결리스트로 구현 하는것이 유연하다.

배열로 구현한 스택구조가 더 빠르다고 하는데 하드웨어가 발단된 지금에서는 별 차이가 없다.

그렇기에 이번 학습일지에도 리스트를 이용한 스택구현을 연습!

입출구가 하나이기 때문에 연단순결리스트로 쉽게 구현이 가능하다.

Node클래스

PUSH 데이터 노드 삽입

연결리스트를 이용 할 경우 TOP이라는 변수의 역할은 머리 노드가 대신한다.

머리노드의 다음 노드가 스택의 상단이 되는 것이다.

POP데이터 노드 삭제

후입선출이기 때문에 최상단 노드를 삭제한다.

머리노드의 다음 노드가 꼬리 노드이면 비어있는 스택이다. 

출력

POP하고 다시 출력