스택 (Stack)
스택 (Stack)이란?
스택 (Stack) 은 ` (깔끔하게 정돈하여) 쌓다` 라는 뜻으로, 물건 등을 쌓아 올리듯이 데이터를 쌓아 올려가는 자료 구조라고 할 수 있다.
스택은 그림과 같이 나중에 넣은 데이터가 먼저 나오게 되는 후입선출 (LIFO, Last In First Out) 구조를 가지고 있다.
Push와 Pop
스택에 데이터를 추가하는 동작을 Push, 스택에서 데이터를 꺼내는 동작을 Pop이라고 한다.
자바에서는 java.util.Stack 클래스를 통해 스택을 제공하고 있다.
stack.pop()은 스택의 마지막 데이터를 꺼내고 그 데이터를 반환해주며,
stack.peek()은 스택의 마지막 데이터를 꺼내지 않고, 반환만 해준다.
알고리즘 문제에서 스택의 제일 마지막 데이터 (제일 처음 꺼낼 데이터)를 stack.peek()를 통해 확인하고 특정 조건에 맞을 경우 stack.pop()을 통해 실제로 꺼내어 어떠한 작업을 해주는 패턴의 문제를 자주 접할 수 있다.
Stack 시간복잡도
| 동작 | 시간복잡도 |
| 삽입 (Push) | O(1) |
| 삭제 (Pop) | O(1) |
| 읽기 (Peek) | O(1) |
| 탐색 (Search) | O(n) |
'자료구조 > 선형 자료구조' 카테고리의 다른 글
| [Java] 큐(Queue)의 개념과 구현 (0) | 2023.12.15 |
|---|