[Data Structure] 스택 (Stack)

✔ 스택

스택(Stack)이란?

• 배열에서 발전된 형태의 선형 자료구조
• 삽입과 삭제 연산이 후입선출로 이루어지는 자료구조

후입선출 (LIFO)

스택의 특징

1. 나중에 들어간 원소(Last In First Out, LIFO)가 먼저 나옴.
   또는 먼저 들어간 원소(First In Last Out, FILO)가 나중에 나옴
   • 새 값이 스택에 들어가면 top이 새 값을 가리킴
   • 스택에서 값을 빼낼 때 pop은 top이 가리키는 값을 스택에서 빼게 됨
   • O(N)의 시간 복잡도와 공간 복잡도를 가짐
2. 해당 위치를 기억하고 있는 스택 포인터가 필요함
   • 스택 포인터는 값이 들어갈 위치를 가리킴
   • 스택 포인터가 최대 크기와 같으면 스택이 꽉 찬 것이며
     스택이 꽉 찬 것이 아니라면 스택의 최상위 위치에 값을 저장
   • 스택 포인터가 0이 되면 스택이 빈 것이며
     스택이 빈 것이 아니라면 스택의 최상위 위치 값을 꺼내옴

스택 용어

• top : 삽입과 삭제가 일어나는 위치
• push : top 위치에 새로운 데이터를 삽입하는 연산
• pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
• peak : top 위치에 현재 있는 데이터를 단순 확인하는 연산
• isEmpty : 스택이 비어있는지 확인하는 연산

스택은 언제 사용할까?

• 깊이 우선 탐색, 백트래킹 종류의 코딩 테스트에 효과적
• 함수의 콜 스택, 문자열 역순 출력, 연산자 후위 표기법 등에 사용
• 개념 자체는 재귀 함수 알고리즘 원리와 일맥상통