[자료구조] Stack(스택)



Stack(스택) 이란?

한마디 버전:

(한글) 한쪽에서만 자료를 넣고 뺄 수 있는 LIFO(Last-In-First-Out) 형식의 선형 자료구조

(영문) The linear LIFO data structure that allow push or pop  data from only one side.



1. 기본 개념

스택의 기본 개념은 영어 단어의 본연의 뜻과 같이 '쌓는다' 입니다.
그리고, 프로세스 스택의 기본적인 구조입니다.(컴퓨터는 스택프레임으로 되어있다 라는 썰 들어보셨죠?)

한쪽 끝으로만 넣고 뺄 수 있기 때문에 제한적으로 데이터에 접근할 수 있습니다.

Queue와 다른점을 아주 편하게 설명해보자면,

딩그르르는 배낭여행을 갔습니다. 제일 아래에는 가벼운 것을 넣는 것이 긴 여행에 유리하다는 말을 듣고 휴지등을 넣었습니다. 하지만, 어느순간 배가 아파서 휴지를 꺼내려고 하는데 위에서 부터 모두 꺼내야 휴지를 꺼낼 수 있는 상황입니다. 이렇게 먼저 들어간 것을 꺼내려면 제일 마지막에 꺼낼 수 있는 구조가 Stack(스택)입니다.

다행히 화장실을 다녀온 후 티켓팅을 위해 공항에서 줄을 섰습니다.  줄은 길지 않았지만, 딩그르르앞에 사람이 모두 끝난 후에야 티케팅을 할 수 있었습니다. 이 구조가 (Queue) 입니다.



2. 용어

  • Push : 배낭에 물건을 밀어 넣는 행위 (스택에 데이터를 넣는 행위)
  • Pop : 배낭에서 물건을 빼는 행위 (스택에서 데이터를 빼는 행위)



3. 재귀함수로 구현하기

재귀함수(Recursive Function)란?
함수 안에서 자기 함수를 호출하는 함수. 조건이 맞으면 스스로를 계속 호출한다.

컴퓨터는 스택프레임으로 되어 있어서 재귀함수자체가 그냥 스택구조로 호출 됩니다. 아래와 같이 한번 실행해 보겠습니다.

def recursive_function(num):
if num < 0:
print("")
else:
print(num)
recursive_function(num-1)
print('다시 재귀 함수 호출!', num)


recursive_function(5) >>> 5 >>> 4 >>> 3 >>> 2 >>> 1 >>> 0 >>> >>> 다시 재귀 함수 호출! 0 >>> 다시 재귀 함수 호출! 1 >>> 다시 재귀 함수 호출! 2 >>> 다시 재귀 함수 호출! 3 >>> 다시 재귀 함수 호출! 4 >>> 다시 재귀 함수 호출! 5

 위와 같이 함수 안에서 자기 함수를 다시 한번 호출하면서 마지막 print()는 찍히지 않고 계속 돕니다. 스택이 '착착착' 쌓이게 되죠.

하지만, 끝이 난 후? 그 동안 찍지 않았던 print를 한방에 찍어줍니다. 근데... 순서가?? 반대로 찍히죠? 스택이 '착착착' 쌓였고 이제 함수의 할일은 끝이 났으니, 위에서부터 하나씩 stack에서 없애주는 겁니다. 함수가 쌓인다는 개념으로 생각하면, 제일 위에것부터 치워준다 생각하시면 될것 같습니다.



4. 스택이 뭐가 좋아요?

구현이 쉽고 단순하다. 사람이 생각하는 방법대로 생각해도 되니까 쉬게 느껴집니다. 



5. 단점이 뭐에요?

  • 스택의 구조에서 최대한 쌓아질 수 있는 공간을 미리 확보함. 그래서 공간 효율이 떨어짐
  • 재귀 함수 역시 공간을 미리 확보함

파이썬에서도 재귀함수는 1000번까지 밖에 호출 할 수 없습니다. 만약에 호출하신다면,
"maximum recursion depth exceeded error" 를 만나시게 될 겁니다.

물론, 시스템에서 변경이 가능합니다. 다음에 재귀함수를 다루면서 자세히 이야기 해보겠습니다. 

그러나, 1000번이 넘어가면 무거운 코드로 인지하겠다. 라는 뜻으로 1000번의 리밋을 걸어 두었습니다.

하지만, 링크드리스트 와 함께 합체하여 사용한다면, 이런 단점을 상쇄할 수 있습니다.

>> LinkedList(연결리스트) 에 대해 알아보기



6. 키포인트

  • 쉽고, 구현하기 편하고, 사용할 일도 많다.
  • LIFO 정책을 사용한다.



7. 추가 Tip

  • 파이썬에서 list() 함수에서는 pop과 append 함수를 지원합니다. append는 push 역할을 합니다.
  • 이것으로 리스트형 Stack 을 만들어 볼 수 있습니다.



  • [[a.original_name]] ([[a.file_size | fileSizer]])
좋아요[[ postLike | likePlus ]]
공유
라이언

“Lead Python Engineer”

댓글 [[totalCommentCount]]
[[ comment.author__nick_name ]] [[ comment.datetime_updated | formatDate]] (수정됨)

[블라인드 처리된 글 입니다.]

답장
[[ sub.author__nick_name ]] [[ sub.datetime_created | formatDate ]] (수정됨)

취소
댓글을 남겨주세요.
'컴퓨터공학' 관련 최신 포스트
[[ post.title ]]
[[ post.datetime_published_from | DateOnly ]]