[자료구조] 스택 Stack

 

---

 

1. 스택

• 스택은 데이터를 순서대로 쌓아 올린 형태로 구성되는 자료구조이다.
• 후입선출(LIFO, Last-In, First-Out) 방식으로, 가장 마지막에 삽입된 데이터가 가장 먼저 제거되는 구조를 가진다.

2. LIFO

• 후입선출(LIFO)은 스택의 작동 방식을 정의하는 가장 중요한 원칙이다.
• 데이터를 추가하는 것을 ‘푸시(Push)’, 데이터를 제거하는 것을 ’팝(Pop)’이라고 한다.
• 항상 스택의 가장 위(Top)에서만 이러한 작업이 이루어진다.

 

3. 특징

장점

• 단순한 구조: 데이터가 한쪽 끝에서만 추가되고 제거되므로 구조가 매우 단순하고 이해하기 쉽다.
• 구현 용이성: 배열이나 연결 리스트를 사용하여 쉽게 구현할 수 있다.
• 빠른 연산 속도: Push 및 Pop 연산은 일반적으로 O(1)의 매우 빠른 시간 복잡도를 가진다.

단점

• 제한된 접근성: 스택의 가장 위에 있는 요소(Top)에만 직접 접근할 수 있으며, 그 외의 요소에는 접근하려면 상위 요소들을 모두 Pop 해야 한다. 따라서 특정 요소의 검색이나 수정이 비효율적이다.
• 크기 제한 (배열 기반 구현 시): 배열을 사용하여 스택을 구현하는 경우, 초기에 설정한 크기를 넘어서 데이터를 저장할 수 없는 단점이 있다. (동적 배열을 사용하면 해결 가능하나, 크기 조정에 비용 발생)