[파이썬 | 자료구조] 스택(Stack)

안녕하세요~ ☺️

지난 시간에는 대표적인 자료구조중 하나인 큐(Queue)를 배웠습니다.

이번 시간에는 반드시 알아 두어야 할 자료구조 스택(Stack)을 배워보겠습니다.

 

스택구조

스택구조는 간단하게 책을 쌓아올리는 행위라고 보시면 됩니다.

 예를들어 책을 바닥에 하나씩 쌓아올린다고 해보죠 책을 다 쌓았으면

처음에 두었던 책은 가장마지막에 빼내고 마지막에 쌓아올렸던 책이 가장

먼저 빼지겠죠?? 이를 자료구조에서는 LIFO(Last In, Fisrt Out)방식이라고 합니다.

 

자 이해를 돕기위해 먼저 스택을 생성해보겠습니다.

해당 스택에서는 가장 처음에 들어간 데이터는 40이고 

가장 마지막에 들어간 데이터는 79입니다. 

 

여기서 데이터(53) 하나를 추가해보겠습니다. 당연히 79위에 쌓이겠죠??

이때 추가된 데이터(53)는 배열의 첫번째 요소에 추가 되었습니다.

이러한 추가방식을 스택에서 Push동작이라고 합니다.

여기서 예를들어 데이터(99)를 더 Push하게 되면 53위에 첫번째 요소로 추가가 되겠죠??

 

그렇다면 여기서 삭제를 하게되면 어떤 데이터가 가장 먼저 사라질까요??

바로 53이 제일 첫번째로 있으니까 가장 먼저 삭제되고 그다음 데이터인 79가 맨 위로 오겠죠??

 

이러한 삭제방식을 스택에서 Pop동작이라고 합니다.

여기서 예를들어 Pop을 한번 더 하게 되면 79 데이터가 삭제되고 8이 첫번째로 오겠죠??

 

그림과 같이 스택은 이러한 방식으로 동작합니다.

 

• push(): 데이터를 스택에 넣기
• pop(): 데이터를 스택에서 꺼내기

 

 

이제 파이썬에서 스택(Stack)을 한번 구현해 보기전에

스택의 장단점을 한번 살펴볼까요?!

 

자료구조 스택(Stack)의 장단점

• 장점
  • 구조가 단순해서, 구현이 쉽다.
  • 데이터 저장/읽기 속도가 빠르다.
• 단점 (일반적인 스택 구현시)
  • 데이터 최대 갯수를 미리 정해야 한다.
    • 파이썬의 경우 재귀 함수는 1000번까지만 호출이 가능함
  • 저장 공간의 낭비가 발생할 수 있음
    • 미리 최대 갯수만큼 저장 공간을 확보해야 함

파이썬에서 스택(Stack)동작 구현하기

파이썬에서 스택은 파이썬의 리스트 기능에서 제공하는 append(push), pop 메서드 이용

 

사진을 보면 리스트 기능에서 제공하는 append로 push기능을 하고있다.

리스트 배열상으로는 맨처음 40 데이터를 추가하고 마지막으로 79 데이터를 추가했다.

이를 스택구주로 보았을 때 79가 가장 위에 쌓이게 된다.

그럼 이와같은 구조를 가진 스택을 생성했다.

 

여기서 데이터(53)을 Push해보자!

이렇게 데이터(53)를 추가하면 배열에서 가장 뒤에 데이터(53)가 추가되고

스택구조로 보았을 때 이러한 스택구조를 띄게 된다.

 

자 여기서 그럼 Pop을 해보자 그럼 어떤 데이터가 삭제될까??

스택구조상 당연히 53 데이터가 삭제되고 그다음 삭제될 데이터(79) 가 위로 올라가게 될것이다.

즉 배열에서는 가장 마지막 요소가 삭제 될 것이고

스택 구조상에서는

이러한 스택 구조가 나온다.

 

이정도면 파이썬 리스트를 이용한 스택(Stack) 구현을 어느정도 이해하셨다고 봅니다!!

이제 이를 이용해서 push() 함수와 pop() 함수를 정의해서 사용해봅시다.

stack_list라는 변수를 리스트 변수로 만들고

push함수와 pop함수를 정의했습니다.

push함수는 리스트변수에 append()함수를 이용해 데이터를 추가해나가게 만들었습니다.

pop함수는 리스트변수에  마지막인덱스[-1]의 데이터를 삭제하고 반환해주게 만들었습니다.

 

자 이렇게 반드시 알아두어야 할 자료구조  스택(Stack)를 알아보고 공부해보았습니다.

다음으로는 대표적 데이터구 링크드리스트 (Linked List)를 알아보겠습니다.

읽어주셔서 감사합니다 :)