[바킹독의 실전 알고리즘] 0x05강 - 스택
[바킹독의 실전 알고리즘] 0x06강 - 큐
[바킹독의 실전 알고리즘] 0x07강 - 덱
💡 스택(Stack)
🍥 정의
- Restricted Structure
- 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조
- FILO(FIrst In Last Out) 후입 선출 구조
🥮 성질
- 원소의 추가 O(1)
- 원소의 제거 O(1)
- 제일 상단의 원소 확인 O(1)
- 제일 상단이 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능
→ 배열을 이용해 구현하면 가능하게 만들 수는 있음
🍡 배열로 구현한 스택
- pos는 다음에 원소를 삽입할 위치 (== 스택의 길이)
const int MX = 1000005;
int dat[MX];
int pos = 0;- push
void push(int x) {
dat[pos++] = x;
}- pop
void pop() {
pos--;
}- top
int top() {
return dat[pos - 1];
}🥟 STL stack
#include <bits/stdc++.h>
using namespace std;
int main(void) {
stack<int> S;
S.push(10); // 10
S.push(20); // 10, 20
S.push(30); // 10, 20, 30
cout << S.size() << '\n'; // 3
if (S.empty()) cout << "S is empty\n";
else cout << "S is not empty\n"; // S is not empty
S.pop(); // 10, 20
cout << S.top() << '\n'; // 20
S.pop(); // 10
cout << S.top() << '\n'; // 10
S.pop(); // empty
if (S.empty()) cout << "S is empty\n"; // S is empty
cout << S.top() << '\n'; // runtime error 발생
}💡 큐(Queue)
🍘 정의
- 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조
- FIFO(First In First Out) 선입선출 구조
🍤 성질
- 원소의 추가 O(1)
- 원소의 제거 O(1)
- 제일 앞/뒤의 원소 확인 O(1)
- 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능
🍢 배열로 구현한 큐
- 앞, 뒤를 가리킬 변수 head와 tail
const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;- 큐는 배열로 구현 시 원소를 삭제할 때마다 앞쪽에 쓸모없는 공간이 생기게 됨
→ 큐에 들어갈 배열을 원형으로 만들어 해결
→ 관념적인 원형 배열
(실제로는 선형 배열이지만 인덱스를 조작하여 원형 배열처럼 동작하게 함)
- push
void push(int x) {
dat[tail++] = x;
}- pop
void pop() {
head++;
}- front
int front() {
return dat[head];
}- back
int back() {
return dat[tail - 1];
}🍣 STL queue
#include <bits/stdc++.h>
using namespace std;
int main(void) {
queue<int> Q;
Q.push(10); // 10
Q.push(20); // 10 20
Q.push(30); // 10 20 30
cout << Q.size() << '\n'; // 3
if (Q.empty()) cout << "Q is empty\n";
else cout << "Q is not empty\n"; // Q is not empty
Q.pop(); // 20 30
cout << Q.front() << '\n'; // 20
cout << Q.back() << '\n'; // 30
Q.push(40); // 20 30 40
Q.pop(); // 30 40
cout << Q.front() << '\n'; // 30
}
💡 덱(Deque)
🥣 정의
- Double Ended Queue
- Restricted Structure
- 양쪽 끝에서 원소의 삽입/삭제가 가능한 자료구조
🥗 성질
- 원소의 추가가 O(1)
- 원소의 제거가 O(1)
- 제일 앞/뒤의 원소 확인 O(1)
- 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능
- 하지만 STL deque에서는 인덱스로 원소에 접근 가능
🍜 배열로 구현한 덱
- 연결 리스트보다 배열을 이용한 구현이 더 쉬움
const int MX = 1000005;
int dat[2*MX+1];
int head = MX, tail = MX;- head와 tail의 초기값이 MX인 이유는 배열의 중간부터 원소를 삽입하면서 양쪽으로 확장하는 모양이기 때문
- push_front
void push_front(int x) {
dat[--head] = x;
}- push_back
void push_back(int x) {
dat[tail++] = x;
}- pop_front
void pop_front(int x) {
head++;
}- pop_back
void pop_back(int x) {
tail--;
}- front
int front(int x) {
return dat[head];
}- back
int back(int x) {
return dat[tail-1];
}🍝 STL deque
- vector와 비슷하지만 front에도 O(1)에 원소의 추가가 가능
- 하지만 deque은 vector와 달리 모든 원소들이 메모리 상에 연속하게 배치되어 있지 않음
- 앞과 뒤에서 모두 원소의 추가/제거가 필요하다면 deque 사용
- 앞뒤 모두에서 원소 추가/제거가 필요한 것이 아니고 배열처럼 사용하고 싶다면 vector 사용
#include <bits/stdc++.h>
using namespace std;
int main(void) {
deque<int> DQ;
DQ.push_front(10); // 10
DQ.push_back(50); // 10 50
DQ.push_front(24); // 24 10 50
for (auto x : DQ) cout << x;
cout << DQ.size() << '\n'; // 3
if (DQ.empty()) cout << "DQ is empty\n";
else cout << "DQ is not empty\n" // DQ is not empty
DQ.pop_front(); // 10 50
DQ.pop_back(); // 10
cout << DQ.back() << '\n'; // 10
DQ.push_back(72); // 10 72
cout << DQ.front() << '\n'; // 10
DQ.push_back(12); // 10 72 12
DQ[2] = 17; // 10 72 17
DQ.insert(DQ.begin()+1, 33); // 10 33 72 17
DQ.insert(DQ.begin()+4, 60); // 10 33 72 17 60
for (auto x : DQ) cout << x << ' ' ;
cout << '\n';
DQ.erase(DQ.begin()+3); // 10 33 72 60
cout << DQ[3] << '\n'; // 60
DQ.clear(); // DQ의 모든 원소 제거
}끄읏
