👨🏫 들어가며
안녕하세요! 강창민 튜터입니다.
드디어 마지막 알고리즘 입문 강의 시간입니다! 조금만 화이팅 해보십시다!
오늘 배울 것은 뭐에요?
- 스택과 큐에 대해서 배웁니다.
- 스택과 큐는 보통의 프로그램 뿐 아니라 여러 방면에서 다양하게 활용되고 있는 자료구조에요!
- 구현은 전부 링크드리스트 기반으로 할 예정입니다. 링크드리스트 킹왕짱!
- 그리고 기초적인 정렬 알고리즘에 대해서 알아볼 겁니다! 오늘 알아볼 정렬 알고리즘은 다음과 같아요!
일단, 스택을 알아볼까요?
- 편의점 사장님이 음료수를 채울때는 끝에서부터 차곡차곡 채웁니다. 손님은 앞에서부터 음료수를 꺼내요.
- 이렇게 **LIFO(Last In First Out)**의 성격을 가진 자료구조를 스택이라고 합니다!
- 이게 넘치면 그 유명한 StackOverflow가 되는 것이죠! 실제로 반복문에서 종료 조건을 지정하지 않거나 잘못된 종료조건을 지정하여 무한 루프가 발생하면 메모리의 스택영역이 쌓이고 쌓이다 터집니다!
- 그럼 이게 언제 쓰여요?
- 모바일 앱을 사용하면 뒤로 가기 버튼을 꽤 많이 누르게 되는데 이때 활용하는 자료구조가 스택이에요!
- 뒤로 가기 버튼을 누르면 직전에 호출했던 스크린을 호출해야되는 특성때문에 그래요!
- 실제로 React에서도 네비게이션을 할 때 스택 네비게이션 기법을 사용하기도 하죠!
- 뿐만 아니라, Undo/Redo와 같은 기능도 스택을 이용합니다. 역순의 성질을 사용해야 될 때 유용해요!
- 스택에서 사용할 수 있는 기능은 대표적인 기능은 다음과 같아요!
- 픽(peek)
- 스택의 Top(맨 위) 데이터를 보는 것이에요!
- 푸시
- 스택에 원소를 삽입하는 행위에요! 원소는 Top에 들어갑니다!
- 팝
- 스택의 Top에서 원소를 가져오는 행위에요! 방금 위에서 넣었던 푸시된 원소가 나오게 되겠죠?
- 코드를 한 번 봅시다!
- 빈 스택 코드
- 링크드리스트 기반으로 스택의 peek 함수 구현하기
- 링크드리스트 기반으로 스택의 push 함수 구현하기
- 링크드리스트 기반으로 스택의 pop 함수 구현하기
- 스택 전체 코드
큐도 알아봐야겠죠?