[자료구조] 스택
1. 스택의 구조
- 스택은 LIFO(Last In, Fisrt Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따름
- LIFO: 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책
- FILO: 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책 - 대표적인 스택의 활용
- 컴퓨터 내부의 프로세스 구조의 함수 동작 방식 - push 시, head에 새로운 데이터가 붙는다.
- pop 시, head에서 데이터가 나온다.
2. 스택 구조와 프로세스 스택
- 스택 구조는 프로세스 실행 구조의 가장 기본
- 함수 호출시 프로세스 실행 구조를 스택과 비교해서 이해 필요
왜 위 사진과 같은 출력 결과가 나올까?
🌟 프로세스 동장 방식에 스택이라는 자료구조를 사용하기 때문에,
recursive(4)를 호출했을 때, recursive(4)가 스택에 담기고,
recursive(4) 안에서 print(4)를 하고 recursive(3)을 호출하기 때문에 recursive(3)이 스택에 담긴다.
마찬가지로 print(3)을 하고 recursive(2)가 스택에 담기고,
print(2)을 하고 recursive(1)가 스택에 담기고,
print(1)을 하고 recursive(0)가 스택에 담기고,
print(0)을 하고 recursive(-1)가 스택에 담긴다.
이제 x가 -1이기 때문에 (0보다 작음) 더이상 recursive()를 호출하지 않고 print("ended")가 실행된다.
그 후에는 스택의 head가 가리키는 recursive(-1)부터 print("returned", 0)을 하고,
순서대로 print("returned", 1), print("returned", 2), print("returned", 3), print("returned", 4) 까지 진행된다.
3. 자료 구조 스택의 장단점
- 장점
- 구조가 단순해서, 구현이 쉽다.
- 데이터 저장/읽기 속도가 빠르다. - 단점 (일반적인 스택 구현시)
- 데이터 최대 갯수를 미리 정해야 한다. (파이썬의 경우 재귀 함수는 1000번까지만 호출이 가능함)
- 저장 공간의 낭비가 발생할 수 있음 (미리 최대 갯수만큼 저장 공간을 확보해야 함)
스택은 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적임. 이 경우, 위에서 열거한 단점이 있을 수 있음
4. 파이썬 리스트 기능에서 제공하는 메서드로 스택 사용해보기
5. 프로그래밍 연습
리스트 변수로 스택을 다루는 pop, push 기능 구현해보기 (pop, push 함수 사용하지 않고 직접 구현해보기)
💛 개인 공부 기록용 블로그입니다. 👻