[Python] Stack (스택) 기본 사용법

 

코딩 테스트를 볼 때 많이 사용하는 자료구조인 Stack

파이썬에서는 리스트를 사용해서 스택의 기본 연산을 구현한다.

 

 

---

 

 

Stack (스택) 기본 정의

---

• 한쪽 끝에서만 자료의 삽입, 삭제가 가능한 LIFO (Last In First Out) 형식의 선형 자료구조
• 프링글스와 같이 가장 나중에 삽입한 자료가 가장 먼저 반환되는 구조
• push, pop, top, isempty, isfull 등의 연산을 가짐

 

출처 : TOPCIT에센스

 

데이터가 입력된 순서로 기억공간에 저장되어 출력 시 가장 나중에 쌓인 데이터가 가장 먼저 출력하게 되는 자료구조

 

흔히 비유하는 것인데, 프링글스 통에서 제일 처음 넣은 과자가 가장 밑에 있는 것처럼 후입선출 구조를 따른다.

짝을 맞추어 제거하는 문제 (ex. 괄호 찾기, 쌍으로 제거) 또는 역순으로 파악하기 등등의 알고리즘 문제에 유용하다.

 

+) 인터럽트 처리, 재귀 프로그램의 순서 제어, 서브루틴의 복귀 번지 저장, 후위(Postfix) 표기법으로 표현된 수식의 연산, 텍스트 에디터 Undo 기능 등에 활용 가능

 

 

 

선언 (init)

---

• 리스트를 사용하기 때문에 리스트의 선언과 같음
• [ ]로 선언 및 초기화

 

# Stack (init)

mystack = []

 

리스트와 마찬가지로 비어 있는 자료구조를 선언할 수 있다.

 

 

 

push : 데이터 삽입

---

• 스택에 데이터 삽입
• stack.append(x)

 

# Stack (push)

mystack = []
mystack.append(1)
mystack.append(2)

mystack	# [1, 2]

 

리스트와 마찬가지로 append를 사용하면 push처럼 가장 마지막인 맨 끝 (맨 위)에 원소가 삽입된다.

 

 

 

pop : 데이터 삭제

---

• 스택에서 데이터 삭제하여 반환
• stack.pop(x)

 

# Stack (pop)

mystack = [1, 2, 3, 4]

mystack.pop()	# 4
mystack		# [1, 2, 3]

 

리스트와는 달리 pop을 사용하며, 제거와 동시에 값이 반환된다.

즉, 가장 마지막에 삽입된 맨 끝(맨 위)에 있는 원소가 삭제된다.

 

 

 

top() : 데이터 반환

---

• 스택의 맨 위에 있는 데이터 값 반환
• stack[-1]

 

# Stack (top)

mystack = [1, 2, 3, 4]

mystack[-1]	# 4

 

가장 마지막에 삽입한 데이터 맨 끝(맨 위)에 있는 원소를 삭제하지 않고 반환하는 top을 구현한다.

 

 

 

isEmpty() : 비어 있는지 확인

---

• 스택에 원소가 없으면 true 값 반환, 있으면 false 값 반환

 

# Stack (isEmpty)

mystack = [1, 2, 3, 4]
isEmpty = False

if len(mystack) == 0:
	isEmpty = True

 

조건문을 사용해 스택에 현재 원소가 있는지를 확인한다.

 

 

 

isFull() : 원소가 있는지 확인

---

• 스택에 원소가 없으면 true 값 반환, 있으면 false 값 반환

 

# Stack (isEmpty)

mystack = [1, 2, 3, 4]
isFull = True

if len(mystack) == 0:
	isEmpty = False

 

조건문을 사용해 스택에 현재 원소가 있는지를 확인한다.