[컴공]sp 2장 이금석교수님 강의노트

1. 스택(Stack)의 개념

스택은 데이터를 후입선출(LIFO, Last In First Out) 방식으로 관리하는 자료구조이다. 즉, 나중에 삽입된 데이터가 먼저 제거되는 구조를 의미하며, 가장 상단에 있는 데이터에만 접근할 수 있다는 특징이 있다. 스택은 프로그램에서 함수 호출, 연산 순서 제어, 되돌리기 기능 등 다양한 용도로 활용된다. 예를 들어, 웹 브라우저의 방문 이력은 스택 구조를 사용하여 뒤로 가기 버튼을 누를 때 이전 페이지로 쉽게 되돌아갈 수 있게 한다. 또한, 파스 트리의 후위 표기법 계산이나 역폴란드 표기법 계산에서도 스택이 핵심적으로 활용된다. 역사적으로는 1960년대 초 반도체 기술이 발전하면서 스택 구조가 컴퓨터 아키텍처에서 중요한 역할을 담당하기 시작했고, 현재는 대부분의 컴퓨터 시스템에서 수행하는 명령어 처리, 호출, 복귀 등을 위해 필수적으로 쓰이고 있다. 스택은 일반적으로 두 가지 연산인 push와 pop으로 구성되며, push는 데이터를 스택에 넣는 작업, pop은 가장 상단에 있는 데이터를 제거하고 반환하는 작업이다. 이 외에도, 스택의 크기를 조사하는 top, 스택이 비어 있는지 확인하는 isEmpty 등의 연산도 존재한다. 실제…