[Python : 알고리즘] Stack 이란?

Stack(스택)이란 나중에 들어온 데이터가 먼저 나가는 '후입선출'의 자료구조입니다.

한쪽이 막혀있는 원통이라고 생각하시면 이해하기 쉽습니다.

 

 

위의 그림처럼

아래가 막혀있는 원통에서 파란색, 초록색 공을 순서대로 넣은 후, 공을 빼게되면 가장 마지막에 넣은 초록색 공이 먼저 빠지게 됩니다.

이러한 형태를 stack 이라고 하며, 공을 넣는 과정을 push, 공을 빼는 과정을 pop 이라고 합니다.

 

파이썬에서는 Stack을 별도로 구현할 필요 없이 파이썬에서 제공하는 list자료구조를 사용하여 stack을 사용할 수 있습니다.

 

list의 append()를 사용하여 list의 마지막에 값을 추가해 주는 것이 stack 자료구조의 push,

list의 pop()을 사용하여 list의 마지막 값을 빼주는 것이 stack 자료구조의 pop 이라고 볼 수 있습니다.

 

def stack_example():
    stack = []
    stack.append(5)
    stack.append(2)
    stack.append(3)
    stack.append(6)
    stack.pop()
    stack.append(1)
    stack.append(7)
    stack.pop()

먼저 stack을 사용하기 위해 list를 만들어 줍니다.

이후의 값들은 아래처럼 변하게 됩니다.

 

stack.append(5)

5

stack.append(2)

5

2

stack.append(3)

5

2

3

stack.append(6)

5

2

3

6

stack.pop()

5

2

3

6 (pop)

5

2

3

stack.append(1)

5

2

3

1

stack.append(7)

5

2

3

1

7

stack.pop()

5

2

3

1

7 (pop)

5

2

3

1

 

이러한 연산이 이루어진 이후 최종 stack list의 값은 [5, 2, 3, 1] 이 됩니다.

 

위의 예제에 주석이 포함된 소스코드는 

여기 에서 보실 수 있습니다.