[자료구조] 스택 (Stack)

• 굉장히 많이 쓰이는 핵심적인 자료 구조 중 하나

스택 구조

• LIFO, FILO 방식을 따름
• 데이터를 제한적으로 접근할 수 있는 구조 (한쪽 끝에서만 자료를 넣거나 뺼 수 있는 구조)
• 대표적인 활용 방식: 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
• 주요 기능: push(), pop() (스택에 넣기, 스택에서 꺼내기)
• 보통 배열 구조를 활용해서 구현하는 것이 일반적임

스택 구조와 프로세스 스택

• 스택 구조는 프로세스 실행 구조의 가장 기본
• 함수가 호출될때마다 프로세스 스택으로 위에 계속 쌓임

def recursive(data):
	if data<0:
		print("ended")
	else:
		print(data)
		recursive(data - 1)
		print("returned", data)

장단점

장점

• 구조가 단순해서 구현이 쉬움
• 데이터 저장/읽기 속도가 빠름

단점

• 데이터 최대 갯수를 미리 정해야함 (파이썬의 경우, 재귀 함수는 1000번까지만 호출 가능)
• 미리 최대 갯수만큼 저장 공간을 확보해야해서 저장 공간의 낭비 발생

---

코드 구현

파이썬 리스트 기능에서 제공하는 메서드 활용

• append, pop 메서드 제공

data_stack = list()

data_stack.append(1)
data_stack.append(2)

data_stack.pop()
#2

pop, push 함수 사용하지 않고 직접 구현

• pop 구현할 때 마지막 element의 index는 언제나 -1

stack_list = list()

def push(data):
	stack_list.append(data)

def pop():
	last_data = stack_list[-1]
	del stack_list[-1]
	return last_data