스택(Stack)

스택(Stack)-배열 이용

: 가장 최근에 들어간 데이터가 먼저 나오는 구조

후입선출(Last In First Out)이라고 한다.

배열은 사이즈가 정해져 있다.

현재 데이터의 위치를 알기 위해 top이라는 변수를 사용(스택포인터)

Push : 스택에 데이터를 넣는 작업

Pop : 스택에 들어 있는 데이터를 빼내는 작업

실제로 배열을 이용한 스택 구조에서는 top의 위치를 변경함으로써

데이터를 빼낸 것처럼 처리한다.

Push

: 스택에 데이터가 가득 찼는지 확인 후 가득차있지 않다면 데이터를 넣어주는 작업

Pop

: 스택에 데이터가 있는지 확인 후 데이터 배내는 작업

연결리스트를 이용한 스택

: 연결리스트를 이용한 스택 구현은 스택의 크기가 정해져있지 않고 동적으로 늘어날 수 있다.

첫 노드를 head, 마지막 노드를 top으로 가리키다.

push메서드는 스택(연결리스트)에 새노드를 이어붙이는 작업을 구현하고

pop메서드는 스택에 들어있는 마지막 노드를 제거하는 작업을 한다.

연결리스트를 이용한 스택은 배열을 이용한 스택 구조와 다르게

데이터를 뺀다는 의미에 완벽하게 들어맞는 작업을 구현할수있다.

사이즈가 정해져있기 때문에 isFull 같은 메서드를 필요하지 않으며,

isEmpty만 구현하면 된다.

Push

case 1 : 스택이 비어있을 때

case 2 : 스택이 비어있지 않을 때

case 1은 HEAD와 TOP이 NULL인 상태

HEAD와 TOP 모두 새노드를 가리키면 된다.

case 2 

새 데이터가 push되었고 case2 상황이므로

Top만 새노드를 가리킨다.

Pop

case 1: 스택이 비어있을 때

case 2 : 스택이 비어있지 않을 때

case 1은 HEAD와 Top이 NULL인 상태

case 2일 경우에는 TOP이 가리키는 노드를 삭제하고 TOP인 이전 노드를 가리키도록 한다.

스택은 후입선출이므로 마지막에 들어온 노드의 연결을 해제하고

TOP이 가리키는 위치를 이전 노드로 옮긴다.