[C++문법] stack, queue, deque

KwangYong·2021년 11월 1일

C++

목록 보기

2/3

stack

배열을 이용한 stack

#include <iostream>
using namespace std;

const int MX = 1000005;
int dat[MX];
int pos = 0;

void push(int x) {
	dat[pos++] = x;
}

void pop() {
//그냥 pos를 하나 줄이면 된다. 그 안에 있는 값은 
//어차피 push가 들어오면 덮어써질거라서 아무 의미가 없어진다.	
	pos--;
}

int top() {
	return dat[pos-1];
}

void test() {
	push(5); push(4); push(3);
	cout << top() << '\n'; // 3
	pop(); pop();
	cout << top() << '\n'; // 5
	push(10); push(12);
	cout << top() << '\n'; // 12
	pop();
	cout << top() << '\n'; // 10
}

int main(void) {
	test();
}

STL stack

#include <iostream>
#include <stack>
using namespace std;

int main(void) {
	stack<int> s;
	s.push(10); 
	s.push(20);
	s.push(30);
	cout << s.size() << '/n';
	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"; 
	cout << s.top() << '\n'; // runtime error 발생
}

queue

배열을 이용한 큐 생성

#include <iostream>
using namespace std;

const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;

void push(int x) {
	dat[tail++] = x; // 1 2 3
}

void pop() {
	head++;
}

int front() {
	return dat[head];
}

int back() {
	return dat[tail-1];
}

void test() {
	push(10); push(20); push(30);
	cout << front() << '\n'; // 10
	cout << back() << '\n'; // 30
	pop(); pop();
	push(15); push(25);
	cout << front() << '\n'; // 30
	cout << back() << '\n'; // 25
}

int main(void) {
	test();
}

STL queue

#include <iostream>
#include <queue>
using namespace std;

int main() {
	queue<int> q;
	q.push(10); 
	q.push(20);
	q.push(30);
	cout << q.size() << '\n';
	if (q.empty()) cout << "q is empty\n";
	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 
}

※ 큐가 비어있는데 front, back, pop이 실행되면 runtime 에러 발생

deque

double ended queue
⭐ vector와 비슷한데 front에도 O(1)의 추가와 제거가 가능한 느낌이다. insert, erase, 인덱스로 원소에 접근도 가능하다. 이와같이 STL vector에서 제겅되는 기능을 STL deque에서도 다 제공해주고 front에서도 추가와 제거가 가능하니 deque가 vector의 상위호환이 아닌가 생각이 들 수 있겠지만, vector와 달리 deque는 모든 원소들이 메모리 상에 연속하게 배치되어 있지 않다. 굳이 front에서 추가, 제거가 필요하지 않고 배열과 같은 느낌으로 쓰고 싶을 땐, STL deque 말고 STL vector를 쓰면 된다.

배열을 이용한 deque 구현

#include <iostream>
using namespace std;

const int MX = 1000005;
int dat[2 * MX + 1];
int head = MX, tail = MX;
//앞뒤 모두 원소를 삽입할 수 있기 때문에 시작을 MX로 초기화한다. 
//double ended queue
void push_front(int x) {
	dat[--head] = x;
}

void push_back(int x) {
	dat[tail++] = x;
}

void pop_front() {
	++head;
}

void pop_back() {
	tail--;
}

int front() {
	return dat[head];
}

int back() {
	return dat[tail - 1];
}

void test() {
	push_back(30); // 30
	cout << front() << '\n'; // 30
	cout << back() << '\n'; // 30
	push_front(25); // 25 30
	push_back(12); // 25 30 12
	cout << back() << '\n'; // 12
	push_back(62); // 25 30 12 62
	pop_front(); // 30 12 62
	cout << front() << '\n'; // 30
	pop_front(); // 12 62
	cout << back() << '\n'; // 62
}

int main(void) {
	test();
}

📌 int head = MX, tail = MX;
앞뒤 모두 원소를 삽입할 수 있기 때문에 시작을 MX로 초기화한다.

STL deque

#include <iostream>
#include <deque>
using namespace std;

int main() {
	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.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의 모든 원소 제거
}