5.1 Linked Structures - Stack

생성일: 2021년 10월 8일 오후 9:31

기존의 Stack를 Linked Structure로 구현

Stack in Linked Structures

• 기존의 Stack은 초기에 array의 크기를 정하거나 동적할당으로 필요한 만큼을 한번에 정해야 함
• Linked 형식은 1개씩 아이템을 추가할 때 마다 공간을 새롭게 할당하여 붙여 나간다.
• Applicatoin Level의 사용자는 Stack이 linked 형식인지 Array 형식인지 인지하지 못한다. (같은 기능 지원)

넣고자 하는 Item을 Node라는 Structure에 담는다.

Node는 해당 Item을 담는 Info와 다음 Node의 주소를 담는 Next로 구성된다.

위의 그림처럼 Node들이 꼬리에 꼬리를 물고 서로 다음 Node를 가르킨다.

(자신보다 앞에 있는 Node에 대한 정보는 가지지 않는다.)

가장 위의 Node를 topPtr이 가르킨다. (Stack Pointer)

💡 주의할점 동적 할당으로 메모리를 할당하는 구조이므로 Item을 삭제하거나 Stack 객체 자체를 지울 때는 무조건! delete를 통해 할당된 메모리를 반납해야한다.

새로운 아이템을 추가 할때에는 새로운 아이템을 담을 Node를 만들고 해당 Node의 Next값을 이전의 topPtr로 주고 topPtr은 이 Node를 가르키게 한다.

Array와 Linked로 구현한 Stack의 비교

Linked Structure로 구현한 Stack은 필요한 만큼 조금 씩 공간을 할당 할 수 있기 때문에 비교적 적은 용량의 데이터를 저장할 때 유리하다.

하지만 일정량 이상의 데이터를 저장 할 때에는 Array로 구현한 Stack을 사용하는것이 좋다. 왜냐하면 Linked 형식은 각 데이터를 담은 노드가 다음 노드를 가리키는 주소 또한 가지고 있어야 하기 때문에 이것이 쌓이다보면 필요한 메모리 공간이 더 커지게 된다.