[자료구조] 쌓아올리는 자료구조 스택에 대해서

(00) :: Introduciton

대학교 학부 시절때 공부했던 이론 내용들을 리마인드 하기 위해서 작성된 게시글입니다.

정확하지 않은 내용이 포함되어 있는 경우, 댓글로 남겨주시면 수정할 수 있도록 하겠습니다.

이 게시글은 한 번에 완성되는 게시글이 아니며 내용을 지속적으로 추가할 예정입니다.

 

(01) :: Define a Concept

스택 자료구조는 한 쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조로 먼저 들어간 원소가 제일 나중에 나오는 선입후출 방식으로 동작합니다. 다른 말로는 FILO(First In, Last Out) 자료구조라고 부르기도 합니다.

예시) 프링글스

-----------
|    4    |
|    3    |
| 12(TOP) |
|    1    |
-----------

 

(02) :: Property

스택은 특정 위치에서만 원소를 삭제하거나 뺄 수 있게 제한을 둔 덕분에 다양한 특성을 갖고 있습니다.

#1 원소를 추가나 제거하는 경우 O(1) 비용 밖에 들지 않는다.
#2 제일 상단(TOP)의 원소 확인하는 경우도 O(1) 비용 밖에 들지 않는다.
#3 제일 상단이 아닌 나머지 원소들을 확인하거나 변경하는 것이 원칙적으로는 불가능하다.

#1의 경우 원소를 넣거나 뺄 수 있게 제한을 두었기 때문에 O(1) 밖에 소요되지 않습니다.

마치 배열의 마지막 인덱스에 원소를 추가하거나 삭제하는 것과 같습니다.

 

#2의 경우도 바로 TOP에 접근하면 되기 때문에 O(1) 밖에 소요되지 않습니다.

 

#3은 배열을 활용하면 최상단 외의 다른 위치의 원소 확인이 가능하도록 만들 수는 있으나 실제로 많이 사용되지는 않습니다.

특히, 사용 사례들을 보면 원소의 추가 및 제거 혹은 최상단 원소 확인만으로도 충분히 역할을 수행할 수 있습니다.

 

(03) :: Stack, How it works?

스택의 특성 부분에서 다룬 스택의 2가지 기능에 대해서 알아봅시다.

#1 원소를 추가나 제거하는 경우 = O(1)
#2 제일 상단(TOP)의 원소 확인하는 경우 = O(1)

 

#1의 경우 값을 추가하고 스택의 TOP 위치만 조정해 주면 됩니다.

삭제하는 경우도 추가하는 것과 동일한 원리로 동작합니다.

1. 크기 3의 스택이 있다고 가정합니다.
-----------
|    X    |
|    X    |
|    X    |
-----------

2. 스택에 13을 넣습니다.
-----------
|    X    |
|    X    |
| 13(TOP) |
-----------

3. 스택에 12를 넣습니다.
-----------
|    X    |
| 12(TOP) |
|    13   |
-----------

 

#2의 경우 스택의 TOP 위치를 통해 값에 접근해서 조회하면 됩니다.

4. TOP에 접근해 데이터를 출력합니다.
-----------
|    X    |
| 12(TOP) |
|    13   |
-----------

-- 출력 결과 --
-------------------
| 터미널 출력: 12 |
-------------------

 

 

(04) :: Stack, How to use in Java?

- 자바 API 활용한 사용 방법

- 실제 구현

 

(FF) :: Reference

참고자료는 다음과 같습니다.

# -- Thanks to --
#1 blog.encrypted.gg