백준 9012번 : 괄호

링크 : https://www.acmicpc.net/problem/9012

자료구조 수업 들을 때 큐랑 스택 이용해서 푼 적이 있는 문제다.

큐로만 구현하면 어떻게 되는 것이고 스택으로만 이용하면 어떻게 되는지 복습해보자.

우선 문제는 스택으로만 구현하였다.

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

bool isVps(stack<char>& st, string& w) {
	int sizes = w.size();
	for (int i = 0; i < sizes; i++) {
		if (w[i] == '(')
			st.push('(');
		else {
			if (st.empty())
				return false;
			st.pop();
		}
	}
	if (st.empty())
		return true;
	else
		return false;
}

int main() {
	int n;
    	string word;
	cin >> n;
	for (int i = 0; i < n; i++) {
		stack<char> stk;
		cin >> word;
		if (isVps(stk, word))
			cout << "YES" << endl;
		else
			cout << "NO" << endl;

	}
	return 0;
}

큐로만 구현하면 어떻게 될까?

큐로 우선 값을 다 받고 (는 +1로, )는 -1로 받는다. 마지막에는 0으로 나와야 하고 선입선출하며 값을 계산하는 과정에서 음수가 되면 false를 return한다.