[C++ STL] stack(스택)

스택(stack)

스택은 한쪽 끝에서만 자료를 넣고 빼는 후입선출(LIFO, Last In Last Out)의 속성을 지닌다. 이런 속성으로 스택은 전산학에서 많이 쓰인다. 함수의 호출이 끝나고 이전 함수로 돌아갈 때, 이 함수 바로 이전의 함수로 돌아가야 한다. 이때 컴퓨터 내부적으로 스택을 이용해 함수들의 문맥을 관리한다.

 

 

• 스택 선언
• 요소 삽입/삭제
• 스택에서 꺼낸(삭제한) 요소 저장
• 스택의 각 요소 출력

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

int main() {

	//스택선언
	stack<int> stk;

	//스택에 요소 삽입
	for (int i = 0; i < 5; i++) {
		stk.push(i);
	}

	//스택에서 요소 제거
	int out = stk.top();
	stk.pop();

	//스택의 전체요소 출력
	while (!stk.empty()) {
		cout << stk.top()<<" ";
		stk.pop();
	}

	cout << endl;
	
	return 0;
}

 

예제 (짝이 맞지 않는 괄호)

괄호의 쌍이 맞는 지 안맞는지 확인하는 작업은 스택의 아주 유명한 예이다. 각 테스트케이스마다 주어진 괄호의 짝이 잘 맞는다면 yes, 아니면 no를 출력하라.

 

 

입력: test case갯수, string

출력: yes or no

 

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

bool wellMatched(string& formula);
int main() {

	int T;
	string data[1000];

	cin >> T;

	for (int i = 0; i < T; i++) {
		cin >> data[i];
	}

	for (int i = 0; i < T; i++) {
		if (wellMatched(data[i])) cout << "Yes" << endl;
		else cout << "No" << endl;
	}

	return 0;
}

bool wellMatched(string& str) {
	stack<char> stk;
	const string opening("({[");
	const string closing(")}]");

	for (int i = 0; i < str.size(); i++) {
		//여는 괄호일 때, stack에 넣는다.
		if (opening.find(str[i])!=-1) stk.push(str[i]);
		//닫는 괄호일 때, stack의 제일 처음거를 꺼내서 같은 지 확인한다.
		else {
			//스택이 비어있으면 실패
			if (stk.empty()) return false;
			//제일 처음꺼를 꺼내봤을 때 opening에 있는 애랑 짝이 안맞으면 실패
			if (opening.find(stk.top()) != closing.find(str[i])) return false;
			
			//둘다에 안걸리면 성공
			stk.pop();
		}
	}

	//for문을 다 돌았을 때, 아무것도  없어야 성공

	return stk.empty();

}

Reference

프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 구종만