스택 개념을 이해하고, 이를 바탕으로 스택의 ADT를 작성하고 구현할 수 있습니다. 스택을 활용해 주어진 문제를 풀 수 있습니다.
총 2편으로 준비했습니다.
1. 스택의 개념과 정의
1. 스택 개념
스택(Stack) 어원은 ‘쌓는다’입니다. 스택은 어원에서 짐작할 수 있듯이 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조입니다. 스택은 우리 주변에서도 쉽게 찾아볼 수 있습니다. 티슈를 생각해봅시다. 티슈를 만들 때는 먼저 넣은 티슈가 가장 아래에 위치합니다. 그래서 티슈를 사용할 때는 가장 위에 있는 티슈부터 사용할 수 있죠. 이렇게 먼저 들어간 것이 마지막에 나오는 규칙을 선입후출 또는 FILO(First In Last Out)라고 합니다. 이때 스택에 삽입하는 연산을 푸시(Push), 꺼내는 연산을 팝(Pop)이라고 합니다.
1.1 스택의 동작 원리 이해하기
다음 그림을 통해 스택에서 원소가 이동하는 과정을 이해해봅시다.
01단계 초기에는 빈 스택이 있습니다.
02단계 여기에 데이터 ‘1’을 푸시해봅시다. 그럼 다음과 같을 겁니다.
03단계 그럼 여기에 데이터 ‘2’를 또 푸시하면 어떻게 될까요? ‘1’ 위로 ‘2’가 올라갑니다.
04단계 그럼 팝을 하면 어떻게 될까요? 가장 위에 있는 데이터인 ‘2’가 빠져나옵니다.
05단계 그리고 다시 데이터 ‘3’을 푸시를 하면? 다시 ‘1’위에 ‘3’이 위치하게 되었습니다.
06단계 팝을 2번 연속으로 하면 ‘3’, ‘1’ 순서로 데이터가 빠져나올 겁니다.
이를 통해 스택에서 데이터가 이동하는 원리를 잘 이해했기 바랍니다.
2. 스택의 정의
스택이 어떤 방식으로 동작하는지는 이해했을 겁니다. 이제 스택의 ADT라는 것을 정의해보고 실제 스택이 동작하는 원리를 설명하겠습니다. ADT는 우리말로 추상 자료형abstract data type인데요. 추상 자료형이란 인터페이스만 있고 실제로 구현은 되지 않은 자료형입니다. 일종의 자료형의 설계도라고 생각하면 됩니다. 그렇다면 스택은 어떤 정의가 필요한 자료구조일까요?
※ 언어에 따라 표준 라이브러리에서 스택 제공 여부는 다릅니다. 파이썬의 경우 스택을 제공하진 않지만 대안으로 리스트 메서드인 append( ) 메서드, push( ) 메서드로 스택을 대체할 수 있습니다.
※ 덱(deque)은 한쪽으로만 데이터 삽입, 삭제할 수 있는 스택과 다르게 양쪽에서 데이터를 삽입하거나 삭제할 수 있는 자료구조입니다. 이런 덱의 특징을 조금만 응용하면 스택처럼 사용할 수 있습니다. 이 방법은 기출 문제를 풀면서 충분히 다루겠습니다.
2.1 스택의 ADT
우선 스택에는 ❶푸시(Push), ❷팝(Pop), ❸가득 찼는지 확인(isFull), ❹비었는지 확인isEmpty과 같은 연산을 정의해야 합니다. 그리고 스택은 최근에 삽입한 데이터의 위치를 저장할 변수인 ❺탑(Top)도 있어야 합니다. 표와 그림으로 정리하면 다음과 같습니다.
※ 여기서는 스택의 내부 데이터를 배열로 관리하는 모습을 예로 들었습니다. 하지만 스택의 원소는 배열이 아니라 다른 자료 구조로 관리할 수도 있습니다.
그림은 스택의 ADT를 나타낸 겁니다. 스택 외부와 내부에 네모 모양으로 표현한 연산과 상태가 보입니다. 그림에서는 연산 시 해야 할 동작과 상태가 가지고 있어야 할 값을 정의하고 있기는 하지만 세부 구현 내용, 즉, 프로그래밍 언어는 무엇을 사용해야 하고 데이터는 이렇게 저장해야 한다는 등의 내용은 없습니다. data 배열을 보면 최대 크기는 maxsize이므로 인덱스의 범위는 0부터 maxsize – 1입니다. top은 가장 최근에 추가한 데이터의 위치를 참조합니다. 지금 그림에서는 아무 데이터도 없으므로 top에 -1이 들어 있습니다. 만약 top이 0이면 데이터가 1개 있는 것이므로 초깃값을 0이 아니라 -1로 했음에 주목하세요.
그렇다면 우리는 스택을 공부를 할 때 ADT만 알면 되고 세부 구현은 몰라도 될까요? 사실은 세부 구현을 알아두면 도움이 됩니다. 왜냐하면 어떤 문제도 ‘스택으로 푸세요’라고 대놓고 알려주지는 않기 때문입니다. 만약 여러분이 어떤 문제를 보고 ‘스택으로 푸는 게 좋겠다’라는 생각이 떠오르려면 스택의 세부 동작을 충분히 아는 것이 좋습니다.
💡 합격 조언 자료구조의 세부 동작을 공부하면 큰 도움이 됩니다
자료구조의 세부 동작을 이해하면 코딩 테스트뿐 아니라 면접에도 큰 도움이 됩니다. 왜냐하면 자료구조의 세부 동작을 공부하면 그 자료구조의 성능 및 특성을 이해하는 것이고, 이는 효율적인 알고리즘을 떠올릴 수 있게 해주기 때문입니다. 실제로 자료구조의 이해도를 요구하는 문제가 출제되기도 합니다. 꼭 한 번은 자료구조의 세부 동작을 공부하기 바랍니다.
2.2 스택 세부 동작에 대해 조금 더 자세히 알아보기
스택에 데이터를 추가하는 경우를 생각해봅시다. 이번에 설명할 내용은 이 푸시 연산을 수행할 때 스택 내부에서 일어나는 과정입니다. 그림은 push(3) 연산을 수행하며 데이터 3이 추가되는 모습을 보여줍니다.
연산 과정은 push(3)을 호출하면 내부적으로 ➊ IsFull( )을 수행해 우선 data 배열에 데이터가 가득 찼는지 확인하고, ➋ 그렇지 않다면 top을 1만큼 증가시킨 후 top이 가리키는 위치➌ data[0]에 3을 추가합니다.
반대로 pop( ) 연산을 수행한다면 어떨까요?
그림에서 보듯 pop( ) 함수를 수행하면 내부적으로 ➊ IsEmpty( ) 함수를 우선 수행해 data 배열에 데이터가 없는 건 아닌지 확인하고, 데이터가 있다면 ➋ top을 1만큼 감소시키고 ➌ 데이터 ‘3’을 반환합니다. 여기서 ‘3이 남아 있는데?’라고 생각할 수도 있습니다. 앞서 정의한 스택의 ADT에서 top은 최근에 삽입한 데이터의 위치라고 했습니다. 즉, top이 가리키는 위치는 -1이므로 실제 data 배열에 데이터가 남아 있더라도 스택은 비어 있다고 보아도 됩니다.
2.3 스택 구현하기
코딩 테스트에서는 문제에 적용할 자료구조 혹은 알고리즘을 파악하는 능력이 중요합니다. 문제에서 의도한 데이터 흐름이 스택에 딱 맞는지 알아차리는 것이 중요하죠. 예를 들어 데이터를 그냥 저장하고 순서와 상관 없이 임의 접근하기만 해도 되면 배열을 사용하면 되지만 최근에 삽입한 데이터를 대상으로 뭔가 연산해야 한다면 스택을 떠올리는 것이 좋습니다. 본격적인 문제를 풀기 전에 앞서 정의한 스택 ADT를 구현하면 다음과 같습니다.
stack = [ ] # 스택 리스트 초기화
max_size = 10 # 스택의 최대 크기
def isFull(stack):
# 스택이 가득 찼는지 확인하는 함수
return len(stack) == max_size
def isEmpty(stack):
# 스택이 비어 있는지 확인하는 함수
return len(stack) == 0
def push(stack, item):
# 스택에 데이터를 추가하는 함수
if isFull(stack):
print("스택이 가득 찼습니다.")
else:
stack.append(item)
print("데이터가 추가되었습니다.")
def pop(stack):
# 스택에서 데이터를 꺼내는 함수
if isEmpty(stack):
print("스택이 비어 있습니다.")
return None
else:
return stack.pop( )
그러나 파이썬의 리스트는 크기를 동적으로 관리하므로 max_size나 isFull( ) 함수, isEmpty( ) 함수는 실제 문제를 풀 때 구현하지 않습니다. 실제로 다음 코드를 보면 max_size, isFull( ) 함수는 사용하지 않고 isEmpty( ) 함수는 len(stack) == 0으로 검사합니다.
stack = [ ] # 스택 리스트 초기화
def push(stack, item):
# 스택에 데이터를 추가하는 함수
stack.append(item)
print("데이터가 추가되었습니다.")
def pop(stack):
# 스택에서 아이템을 꺼내는 함수
if len(stack) == 0:
print("스택이 비어 있습니다.")
return None
else:
return stack.pop( )
그런데 push( ) 함수, pop( ) 함수를 구현한 부분을 보면 실제 이 함수들이 하는 일은 리스트의 append( ) 메서드, pop( ) 메서드를 호출하는 것이 전부입니다. 그러므로 push( ) 함수와 pop( ) 함수는 다음과 같이 굳이 구현하지 않아도 됩니다.
stack = [ ]
# 스택에 데이터 추가
stack.append(1)
stack.append(2)
stack.append(3)
# 스택에서 데이터 꺼냄
top_element = stack.pop( )
next_element = stack.pop( )
# 스택의 크기를 구함
stack_size = len(stack)
# top_element : 3
# next_element : 2
스택은 개념 자체는 크게 어렵지 않으므로 비교적 쉽게 이해할 수 있습니다. 하지만 실전에 들어가 문제를 풀다 보면 스택을 몰라서 풀지 못하는 것이 아니라 ‘이 문제는 스택을 활용해야 풀 수 있다’라는 생각 자체를 못해서 풀지 못하는 경우가 대부분입니다. 따라서 스택 관련 문제를 많이 풀어보며 ‘이 문제는 스택을 사용하는 게 좋겠다’라는 감을 익히기를 권합니다.
다음 편은 스택 몸풀기 문제입니다.
자료구조, 알고리즘, 빈출 100 문제로 대비하는 코테 풀 패키지
[되기] 코딩 테스트 합격자 되기(파이썬 편)
저자 박경록
매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.
1 Comment