📌 스택

스택(Stack)은 자료의 삽입과 삭제가 한쪽 끝에서만 일어나는 선형 자료구조이다.
후입선출(LIFO, Last In, First Out) 원칙에 따라 데이터를 저장하고 접근한다.

후입선출(LIFO)란?
가장 마지막에 삽입된(가장 최근에 들어온) 데이터가 가장 먼저 빠져나가는 구조를 뜻한다.

💡 용어

• top : 스택의 최상단(가장 최근에 들어온 데이터)
• push : 스택에 데이터를 삽입하는 행위
• pop : 스택의 top에 위치한 데이터를 제거하는 행위

peek?

스택에는 기본적으로 push와 pop 두 기본 연산만 존재한다.
따라서 스택에 데이터를 변경하지 않고 top에 위치한 데이터가 무엇인지 알아내는 동작이 존재하지 않는다.
이를 peek 라는 연산으로 해결한다.
peek는 데이터의 삽입 / 삭제 없이 단순하게 스택의 top에 해당하는 값을 반환하는 동작을 한다.

💡 시간복잡도

• 삽입(insert) : O(1)
• 삭제(delete) : O(1)
• 탐색(search) : O(n)

💡 스택 오버플로우와 스택 언더플로우

스택은 생성할 때 미리 메모리를 할당해야하기 때문에 용량이 제한되어 있다.
따라서 스택에 저장할 수 있는 데이터의 개수는 한계가 있으며, 이 한계를 넘어서 저장하려고 하면 스택 오버플로우(Stack Overflow) 에러가 발생한다.
반대로, 스택이 비어있는 상태에서 스택에서 데이터를 pop하려고 한다면 스택 언더플로우(Stack Underflow) 에러가 발생한다.

이 두가지 에러 모두 프로그램에서 심각한 오류를 발생시킬 수 있기 때문에 이러한 에러가 발생하지 않도록 유의하여 스택을 사용하여야 한다.

💡 장 / 단점

장점

1. 두가지 기본 연산만 가지고 있기 때문에 구현과 사용이 쉽다.
2. 재귀적인 알고리즘의 구현에 매우 용이하다.

단점

1. 중간에 있는 요소에 직접적으로 접근할 수 없다.
2. 스택의 크기가 고정된 크기로 제한되어 동적으로 변경할 수 없다.

Reference

스택 - 위키백과
스택 - TTA정보통신용어사전
[자료구조] 스택(Stack)과 큐(Queue)이해하기
🧱 자바 Stack 구조 & 사용법 정리
[Data Structure] 스택(Stack)과 큐(Queue) 개념, 특징, 활용 예시
1-4. [자료구조이론] 스택(Stack)