Data-Structure-&-Algorithm

210128 자료구조(Data structure) Stack(스택)

이번 포스팅에서 정리 할 내용은

스택에 대한 개념이다. 스택을 비유로 들면, 바닥에 쌓여있는 책들을 예로 많이 들고 있는데, 그 이유는 스택은 데이터를 제한적으로 접근할 수 있는 구조로 되어있기 때문이다.

여기서 제한적인 접근이란?

한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조로 되어있다는 것을 말한다.
따라서 LIFO(Last-In-First-Out)의 정책을 가지고 있는 구조이다.
이는 다음에 정리할 큐(queue)의 FIFO(First-In-First-Out)정책과 상반되는 구조이다.

스택은 어디에서 사용되나?

스택은 대표적으로 우리가 사용하는 컴퓨터 내부의 프로세스 구조의 함수 동작 방식에서 사용이 된다.
스택 구조는 프로세스 실행 구조의 가장 기본으로, 함수 호출시 프로세스 실행 구조를 스택과 비교해서 이해할 필요가 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def recursive(data):
  if data < 0:
    print("ended")
  else:
    print(data)
    recursive(data - 1)
    print("return", data)

recursive(4)

# output :
"""
4
3
2
1
0
ended
returned 0
returned 1
returned 2
returned 3
returned 4
"""

위의 재귀함수 실행을 살펴보면, 4부터 0까지 데이터가 들어간 다음에 탈출조건에 만족하는 입력 데이터 들어가게 되면, “ended”가 출력이 되고, 그 다음에 마지막에 삽입된 데이터부터 역으로 함수 내의 재귀호출 실행부의 아래에 있는 출력문이 실행되고 있음을 알 수 있다.

스택의 주요 기능

스택의 주요 기능은 데이터를 스택에 넣는 (push())와 데이터를 스택에서 꺼내는 (pop())이 있다.

스택의 장단점

스택의 장점은 구조가 단순해서 구현이 용이하다는 점과 데이터 저장과 데이터 읽기 속도가 빠르다는 점이 있다.
스택의 단점은 일반적인 스택을 구현할 경우, 데이터의 최대 갯수를 미리정해야 된다는 점이 있다. 이러한 한계는 링크드 리스트(Linked List)를 구현해서 극복할 수 있으며, 최대로 쌓을 수 있는 공간을 확보함으로써 생기는 메모리 낭비에 대한 문제점도 해결할 수 있다.