스택
📢
Last-In First-Out의 구조를 가지며 객체를 삽입 또는 제거할 수 있는 컨테이너
Last-In First-Out
스택에서 가장 중요한 성질을 나타내는 말이에요. 우리말로 번역하자면 마지막에 들어간 것이 처음으로 나온다**라고 할 수 있어요.
스택은 한 쪽이 뚫린 통이라고 생각하면 됩니다. 삽입할 때 A를 가장 먼저 넣었는데 제거를 할 때 가장 먼저 제거되는 것은 C예요. 이처럼 스택은 가장 나중에 넣은 것을 제일 먼저 꺼낼 수 있습니다.
🎨 내부 메서드 (C++)
기본적으로 스택은 C++ STL에 정의되어 있어요!
사용하려면 헤더에 #include <stack>를 선언하고
변수 선언을 통해 사용하시면 됩니다.
stack<자료형> 변수명;
| 메서드 이름 | 역할 |
|---|---|
| empty | 스택 내부가 비어있는지 알려줌 |
| size | 스택 크기 반환 |
| top | 스택의 가장 위의 요소 반환 |
| push | 스택에 요소 삽입 |
| pop | 스택에서 요소 제거 |
| swap | 스택끼리 내부 요소 교환 |
empty
stack1.empty();stack이 비어있다면 true 아니라면 false 반환
size
stack1.size();stack의 크기를 정수형으로 반환
top
stack1.top();현재 상태에서 stack의 가장 위의 요소를 반환 (stack에서 제거되지는 않는다)
push
stack1.push(5);stack에 요소를 집어넣음
pop
stack1.pop();현재 상태에서 stack의 가장 위의 요소를 제거한다 (값을 반환하지 않는다)
swap
stack<int> stackFirst, stackSecond;
stackFirst.swap(stackSecond);선언한 stackFirst의 내부 값들을 stackSecond와 바꾼다
⏰ 시간 복잡도
삽입(Insert), 제거(Delete)
- 스택의 가장 윗부분에서 이루어지는 연산이에요.
- O(1)의 시간 복잡도를 가져요.
탐색(Search)
- 스택 내부에서 원하는 데이터를 찾을 때까지 연산을 수행해요.
- O(n)의 시간 복잡도를 가져요.
📋 예제
백준 9012 - 괄호
백준 9012 - 해답
백준 9935 - 문자열 폭팔
백준 9935 - 해답
큐
📢 First-In First-Out 의 구조를 가지며 객체를 삽입 또는 제거할 수 있는 컨테이너
First-In First-Out
아까 스택에서 설명한 Last-In First-Out과 비슷하죠? 이 또한 큐의 가장 중요한 성질을 나타내는 말이에요. 우리말로 번역하자면 처음으로 들어간 것이 처음으로 나온다 라고 할 수 있어요.
큐는 양쪽이 뚫린 통 이라고 생각하면 됩니다. 한 쪽이 막혀있는 스택과 달리, 자료의 삽입과 제거가 물 흐르듯이 한 방향을 향해서 이루어집니다. 그래서 먼저 넣은 객체는 제일 먼저 제거가 가능하게 됩니다.
🎨 내부 메서드 (C++)
큐 또한 C++ STL에 정의되어 있어요!
사용하려면 헤더에 #include <queue>를 선언하고
변수를 선언하여 사용하면 됩니다.
queue<자료형> 변수명;
| 메서드 이름 | 역할 |
|---|---|
| empty | 큐 내부가 비어있는지 알려줌 |
| size | 큐 크기 반환 |
| front | 큐의 가장 앞 요소 반환 |
| back | 큐의 가장 뒤 요소 반환 |
| push | 큐의 뒤에서 요소 삽입 |
| pop | 큐 앞에서 요소 제거 |
| swap | 큐끼리 내부 요소 교환 |
empty
queue1.empty();queue가 비어있다면 true 아니라면 false 반환
size
queue1.size();queue의 크기를 정수형으로 반환
front
queue1.front();현재 상태에서 queue 가장 앞 요소를 반환 (queue에서는 제거되지는 않는다)
back
queue1.back();현재 상태에서 queue 가장 뒤 요소를 반환 (queue에서는 제거되지 않는다)
push
queue1.push(5);queue에 요소를 집어넣음
pop
queue1.pop();현재 상태에서 queue의 요소를 제거한다 (값을 반환하지 않는다)
swap
queue<int> queueFirst, queueSecond;
queueFirst.swap(queueSecond);선언한 queueFirst의 내부 요소들을 queueSecond와 바꾼다
⏰ 시간 복잡도
삽입(Insert)
- 큐의 앞부분에서 이루어지는 연산이에요.
- O(1)의 시간 복잡도를 가져요.
제거(Delete)
- 큐의 뒷부분에서 이루어지는 연산이에요.
- O(1)의 시간 복잡도를 가져요.
탐색(Search)
- 큐 내부에서 원하는 데이터를 찾을 때까지 연산을 수행해요.
- O(n)의 시간 복잡도를 가져요.
📋 예제
백준 2164 - 카드2
백준 2164 - 해답
백준 1158 - 요세푸스 문제
백준 1158 - 해답
