[자료구조] 스택(Stack)의 모든 것-개념, 예시, 파이썬 내장함수

안녕하세요. 진또배기입니다. 시작하기 전에 스택에 대한 썰을 잠시 풀겠습니다. 제가 IT기업에서 면접을 보던 중 큐와 스택의 차이점에 대해서 물어보시는 면접관분이 계셨습니다. 어렵지않은 질문이기에 각각의 개념, 특징, 사용예시에 대해서 멋있게(?) 말했습니다. 그 다음 질문으로 '스택으로 큐를 만들 수 있을까요?'라고 물어보셨습니다. 왠지 분위기상 만들 수 있을 것 같았는데 잘 몰라서 그냥 모르겠다고 답했습니다. 정답은 만들 수 있습니다. 스택 두개를 사용해 Stack1에 데이터를 차례로 넣고 LIFO 규칙에 따라 Stack1에서 나온 데이터들을 다시 차례로 Stack2에 집어 넣습니다. 그리고 다시 LIFO규칙(후입선출)으로 데이터들을 pop시키면 큐의 규칙인 FIFO으로 나오게 됩니다! 그때 1차면접에서는 붙었지만 2차면접에서 떨어져 아쉬웠습니다ㅠㅠ 이처럼 스택과 큐는 서로 잘 비교되며 두 개념을 같이 이해하시는 것을 추천드립니다
자 그럼 시작합니다!
---------------------------------------------------------------------------------------------------------------------------------

1. 스택이란?

스택이란 군대물품 중 하나인 군장과 같습니다. 여자분들한테는 음....화장품 클러치와 같다고 할 수 있을까요?
즉, 가장 먼저들어간 데이터가 가장 나중에 나오는 자료구조입니다. 이 규칙을 LIFO라고 해요. Last-In First-Out의 줄임말
그림으로 표현하면 

처럼 데이터가 삽입되고 추출됩니다. 예를 들면 군장물품을 쌀 때, 텐트는 가장 먼저(1번 자리에) 넣습니다. 왜냐하면 텐트는 모든 훈련이 마친 뒤 밤에 설치하기 위해서에요. 따라서 가장 하루의 마지막에 쓰이는 (무겁기도 하고, 군장물품중에 제일 무거움ㅠ)텐트를 맨 밑에 넣음으로써 효율적으로 군장을 싸는 방법입니다.

즉, 스택이란 다른 말로하면 가장 나중에 들어온 자료가 가장 먼저 처리되는 LIFO(Last-In-First-Out) 선형 자료구조입니다. Stack을 영어로 직역하면 쌓음, 더미라고 번역되는데 이 이유는 이제 아시겠죠?
---------------------------------------------------------------------------------------------------------------------------------

2. 스택 사용 예시

스택은 어디에서 쓰일까요? 이를 알기 위해서는 가장 최근 데이터가 필요한 영역일 것입니다.
예를 들면 여러분의 왼쪽 상단에 있는 '뒤로가기'나 실행 취소를 해주는 Ctrl+x정도가 있을 것입니다. 
또한 파이썬에는 reverse()

 

listA=[1,2,3,4]
listA.reverse()
listA
[4,3,2,1]

 

라는 내장 함수가 있는데 listA의 요소들을 역순으로 뒤집어 출력해주는 역할을 합니다. 리스트의 요소들을 출력하고 가장 먼저 출력된 요소를 가장 안쪽에 밀어 넣음으로써 스택이 활용됩니다.
---------------------------------------------------------------------------------------------------------------------------------

3. 파이썬에서의 스택 활용

파이썬에서는 스택 자료구조를 지원하지 않습니다. 자바는 지원하는데 말이죠. 하지만 기본 클래스인 list를 통해 스택을 구현할 수 있습니다. 이제부터는 리스트를 통해 스택 활용하는 내장함수를 알려드리겠습니다.

 

1) stack 구현 ## 파이썬에서는 리스트로 스택을 흉내 냅니다.
stack = []
stack
---------------------------------
[]

2) stack에 원소 넣기 ## append 메소드를 이용해 리스트의 가장 마지막에 원소를 넣도록 합니다.
stack = [1,2,3]
stack.append(4)
stack
---------------------------------
[1, 2, 3, 4]

3) 원소 추출하기 pop() ## 스택에서 원소를 제거할 때에는 pop 메소드를 이용해 리스트의 가장 마지막 원소를 제거해줍니다.
                       ##이때, pop 메소드에 의해 제거한 원소를 리턴 받을 수 있습니다.
stack = [1,2,3]
top = stack.pop()
print(top)
stack
---------------------------------
3
[1, 2]

4) 스택의 top 가져오기 ##스택에서 원소를 제거하지 않고 가져오기만 할 때에는 [-1]을 이용하도록 합시다.
stack = [1,2,3]
top = stack[-1]
top
---------------------------------
3

 

기본적인 스택 활용은 다음과 같습니다.
조금 더 심화된 스택 활용을 해보겠습니다. 제가 초반에 코딩테스트 문제들을 풀어보면서 알게된 것들인데요.

 

Q. 가장 큰 수를 출력하세요.

stack=[5,1,9,2,8,4]
stack.sort()  #리스트내 요소 오름차순 정렬 [1,2,4,5,8,9]로 정렬됩니다.
answer = 0
if stack:
    anwer = stack.pop()
    return answer

 

if stack: 이렇게 표현한다는 것에 정말 놀라웠습니다. 이 문법은 stack에 요소가 있다면 if문을 실행, 아무것도 없다면 if문을 실행하지 않습니다. 사실 이 문법은 스택뿐만아니라 큐, 해시 등으로도 많이 사용됩니다.

오늘은 여기까지 하겠습니다. 다음엔 큐에 대해서 포스팅을 하겠습니다.

항상 감사합니다
-진또배기 올림