[자료구조][Java] Stack이란?

---

📢 스택(Stack)

•  후입선출(後入先出)의 특성을 가지는 자료구조를 일컫는다.
•  맨 마지막의 데이터가 가장 먼저 출력이 된다.

🧨 예시

1.  스택은 "쌓여 있는 팬케이크" 라고 생각하는 것이 좋다.
2.  ex) 팬케이크를 하나씩 쌓게 되면 먼저 내려놓은 것이 맨 아래에 있고 나중에 쌓은 것이 맨 위에 있을 것이다.
3. 즉, Last In First Out(LIFO) -> 가장 나중에 올라온 것이 가장 먼저 나가게 되는 것이다.

🧨 스택의 종류

• 힙 영역 메모리에서 일반적인 데이터를 저장하는 스택
• 스택과 스택 영역 메모리에서 프로그램의 각 분기점에 변수와 같은 정보를 저장하기 위한 스택

---

📈  스택의 개념

• 스택은 해당 이미지처럼 출입구가 1개이다.
• 즉, 데이터의 삽입과 제거가 한 곳에서 이루어진다.
• 먼저 들어간 데이터가 늦게 나오고, 나중에 들어간 데이터가 먼저 나오는 구조를 갖게 된다.

---

📈 스택의 시간 복잡도

• 삽입 : Insertion O(1)
• 삭제 : Deletion O(1)(pop) / O(N)(remove)
• 검색(조회) : Search O(N)
• 💡 스택의 삽입과 삭제 연산은 항상 top에서만 일어나므로, 삽입과 삭제에 소요되는 시간복잡도는 O(1)로 고정

---

📈 스택의 주요 함수

• push() : 스택에 자료를 넣는 함수
• pop() : 가장 최근에 추가한 자료를 빼는 함수
• peek() : 마지막 위치(Top)에 해당하는 데이터를 읽는 함수
• isFull() : 스택이 가득 찼는지 확인하는 함수
• isEmpty() : 스택이 비었는지 확인하는 함수
• size() : 스택의 크기를 확인하는 함수
• contains(a) : a 가 있는지 확인하는 함수 

---