[코딩테스트][C++]이론3. 스택과 큐

스택

스택은 LIFO의 규칙, 즉 가장 나중에 들어온(최근에 들어온)값이 먼저 나가지는 자료구조로 보통 DFS나 백트레킹 문제에서 많이 사용된다.

큐

큐는 FIFO의 규칙, 즉 먼저 들어온(입력이 제일 먼저된)값이 먼저 나가지는 자료구조로 BFS에서 많이 사용된다.

문제 예1. 

오큰수

오큰수는 기준값을 기준으로 오른쪽에 있으면서  큰 수 중에서 가장 왼쪽에 있는 수를 뜻한다.

이 문제는 스택을 통해 풀 수 있는데 스택에 새로 들어오는 수가 top에 있는 수보다 크면 오큰수 배열에 저장한다. 

이때, 스택에는 수열의 값이 아닌 인덱스를 저장하여 pop되는 index에 오큰수를 저장한다. 

전체 배열을 순회하며 오큰수를 저장하고 정답배열을 순회하며 오큰수가 없는 칸에는 -1을 넣어준다. 

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	vector<int> a(n, 0);
	vector<int> answer(n, 0);
	
	stack<int> st;
	st.push(0);
    
    for(int i=0;i<n;i++){
        cin>>a[i];
    }

	for (int i = 1; i < n; i++) {
		while (!st.empty() && a[st.top()] < a[i]) {
			answer[st.top()] = a[i];
			st.pop();
		}
		st.push(i);
	}

	while (!st.empty()) {
		answer[st.top()] = -1;
		st.pop();
	}

	for (int i = 0; i < n; i++) {
		cout << answer[i] << " ";
	}

}

 

문제 예2.

절댓값 힙 구현하기

이 문제는 절댓값 힙을 구현하면 되는데  우선순위 큐를 사용하여 구현하면 된다. 우선 순위 큐는 큐와 달리 우선순위를 가진 값이 먼저 나가게 되는 자료구조이다. 

그리고 정렬기준을 따로 지정해줄 수 있는데 지정해준 기준대로 자동으로 정렬이 된다. 

이 문제에서는 정렬기준을 절댓값으로 두고 만약 절댓값이 같다면 음수를 우선 정렬해준다. 

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

struct compare
{
	bool operator()( int a, int b) {
		int first = abs(a);
		int second = abs(b);
		if (first == second) {
			return a > b;		//b가 우선순위
		}
		else {
			return first > second;		//second가 우선순위
		}
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	priority_queue<int, vector<int>, compare> pq;
	
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int rq;
		cin >> rq;

		if (rq == 0) {
			if (pq.empty()) {
				cout << "0\n";
			}
			else {
				cout << pq.top() << "\n";
				pq.pop();
			}
		}
		else {
			pq.push(rq);
		}
	}

}