이번 포스팅 내용은
패스트캠퍼스 <개발자 취업 합격 패스 With 코딩테스트, 기술면접 초격차 패키지> 중,
이준희 강사님의 '자료구조 파트' 강의 내용을 정리한 것입니다.
스택
스택도 큐와 마찬가지로 LIFO, FILO 등의 여러 정책을 따른다.
가장 대표적으로 쓰이는 정책은 LIFO로, 좁은 상자에 블록을 쌓는 동작원리와 유사하다. 가장 밑바닥부터 블록을 차례로 쌓은 후, 다시 꺼낼 때는 가장 마지막에 넣은 블록부터 꺼낸다.
이와 유사하게, 스택은 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조이다.
스택의 기능
push()
- 스택에 데이터를 넣는 기능이다.
pop()
- 스택에서 데이터를 꺼내는 기능이다.
그림으로 이해해보자.
스택의 특징
스택의 구조
- 프로세스의 함수 동작방식에서 스택이 사용된다. (프로세스 : 실행중인 프로그램)
스택의 장점
- 구조가 단순해서 구현이 쉽고 데이터의 저장과 읽기 속도가 빠르다.
스택의 단점
- 보통 배열 구조를 활용해서 구현하므로, 데이터의 최대 갯수를 미리 정해야 한다.
- 메모리 낭비가 발생할 수 있기 때문에 미리 최대 갯수만큼 메모리를 확보해야 한다.
재귀함수를 활용한 프로세스 스택 구현
# 재귀함수 정의
def recursive(data):
if data < 0:
print ("ended")
else:
print(data)
recursive(data - 1)
print("returned", data)
# 함수 호출
recursive(4)
➡️ 출력
4
3
2
1
0
ended
return 0
return 1
return 2
return 3
return 4
📌 process stack : 함수와 관련된 정보들이 쌓이는 공간
return 0 부터 이해가 안간다 ....ㅠㅅㅠ
리스트 변수로 push, pop 기능 구현
# 빈 리스트 생성
stack_list = list()
# push 구현
def push(data):
stack_list.append(data)
# pop 구현 (LIFO 정책에 사용)
def pop():
data = stack_list[-1] # 꺼낼 원소를 data라는 변수에 지정
del stack_list[-1] # 리턴값이 반복되지 않도록 마지막 요소를 삭제해준다
return data
# 0부터 9까지의 수로 스택 생성
for index in range(10):
push(index)
# 생성된 스택의 길이 출력
print(len(stack_list))
# pop함수 호출(가장 마지막에 넣은 요소 출력)
print(pop())
➡️ 출력
10
9