스택 ADT

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다.

    https://github.com/AeroCodeX/

스택 ADT

접시를 쌓고 빼는 것 처럼,

나중에 삽입한 데이터가 먼저 빠져나오는 자료구조 인터페이스.

Last-In  First-Out  (LIFO)

First-In  Last-Out  (FILO)

스택 ADT의 특성

• 나중에 삽입한 데이터가 먼저 빠져나옴.  (LIFO or FILO)
• 스택의 TOP에서만 조회/삽입/삭제가 일어남.

구현에 따른 스택의 성능

스택의 TOP에서만 끝에서만 동작이 이루어지기 때문에,

마지막 또는 첫번째 위치에서 효율적으로 동작하는 구현을 사용하는 것이 좋다.

• 배열?

마지막 지점을 TOP으로 잡으면 성능이 좋다.

노드기반이 아니라, 마지막 위치에서 삽입/삭제시 관리비용도 없다.

다만, 한번 정해진 스택의 크기를 변경하기 힘들다.

• 단일 연결 리스트?

첫 지점을 TOP으로 잡으면 성능이 좋다.

다만, 삽입/삭제시 노드 관리비용이 소요되나,  적은편.

논리적인 허용량이 무제한이라,

스택의 크기를 유동적으로 변경할 수 있다.

중간과 마지막 지점에서 조회성능이 좋지 않지만,

스택의 특성상 디메리트가 되지 않는다.

스택의 일반적인 구현으로 사용됨.

• 이중 연결 리스트?

어느쪽을 TOP으로 잡아도 성능이 좋다.

포인터 관리비용이 좀 더 증가하나,  (포인터가 노드당 2개!)

봐줄만한 편.

중간 노드를 조회해야 한다면 이것을 사용해야 하나,

이런 경우에는 굳이? 스택을 사용해야할지 다시 살펴볼 것.

• 벡터?

마지막 지점을 TOP으로 사용하면 성능이 좋다.

다만, 벡터의 수용량이 자주 확장된다면 성능이 떨어질 수 있다.

처음부터 벡터의 수용량을 충분히 크게 설정할 것.

• 스킵 리스트?

어느쪽을 TOP으로 잡아도 다른 구현에 비해 성능이 나쁘다.

레벨관리를 위해 메모리도 더 잡아먹는다.

스킵 리스트는 이분검색을 사용하기 위한 구현임을 생각한다면,

스택의 구현으로 사용하는 것은 옳지 못하다.

• 환형 배열?

어느쪽을 TOP으로 잡아도 성능이 좋다.

Front, Rear 관리비용이 있긴 하나,  없는것과 마찬가지.  (단일 연결 리스트는 노드당 1개)

중간 지점에서의 조회성능도 나쁘지 않으나,

스택의 특성상 굳이 어필되지 않는 장점.

• 덱 (데크) ?

어느쪽을 TOP으로 잡아도 성능이 좋다.

유의점은 벡터와 같다.

스택을 적용하면 좋은 문제

• 괄호 짝이 맞는지 검사  →  괄호가 포함된 수식계산에 응용
• 트리에서 깊이우선 순회
• 재귀호출 해소
• 히스토리 저장
• ...