0x05강 스택

 

스택은 

원소의 추가

원소의 제거

제일 상단의 원소 확인

 

원칙적으로 이 세가지 기능만 가능한 자료구조이다. 

배열을 기반으로 구현을 해서 제일 상단이 아닌 원소에서 확인/변경 등을 할 수 있게 만들 수 있지만

결국 스택을 활용하는 일들은 제일 상단의 원소의 추게, 제거, 확인을 하는 것들이다. 

 

STL stack에도 결국 제일 상단 원소의 추가/제거/확인 이 있을 뿐이다. 

 

ㄷ

스택의 구현은 이런식으로 배열을 통해서 구현할 수 있고, 

POS는 다음의 데이터가 삽입될 위치를 가리키고 있다. 마지막 위치가 아니라 그 다음 위치, 다음 원소가 삽입될 위치를 가리키고 있다는것이 중요하다. 

잘 생각해보면 POS의 값이 스택의 길이, 즉 스택 내의 원소의 수를 의미한다는 것을 알 수 있다. 

 

STL stack을 쓸때에

기억해야 할것은

push, pop, top, size, empty 이렇게 있는 멤버함수들이다. 

원소의 삽입, 삭제, 확인, 거기에다가 사이즈와 비어있는지, 이렇게 두가지를 추가해서 STL stack을 활용하면 된다. 

 

스택이 비어있는데,  top이나 pop을 하면 런타임 에러를 발생한다. 

제출한 코드로 런타임 에러를 받았을때는 다양한 이유가 있을 수 있겠지만 스택이 비어있을때

top이나 pop을 한건 아닌지 확인해보도록 하자. 

 

1874번 스택 수열 

 

이 문제에서 보면 코드를 보자면

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	stack<int> s;
	int cnt = 1;
	string ans;
	while (n--)
	{
		int t;
		cin >> t;
		while (cnt <= t)
		{
			s.push(cnt++);
			ans += "+\n";
		}
		if (s.top() != t)
		{
			cout << "NO\n";
			return 0;
		}
		s.pop();
		ans += "-\n";
	}
	cout << ans;
}

이 소스코드를 보면, 여기서 중요한건, 중간 과정상에 while(cnt<=t) 부분에서

ans에 + 부분을 지속적으로 추가적으로 적립 하기만 하는거고, cout으로 출력하는건

중간 과정을 다 거친뒤에 결과에서 한번만 출력해주는것이고, 그렇기 때문에 중간 과정상에서

불가능한 상황이 발생했을때 cout<<"NO\n"; 를 통해서 NO라는 단어를 출력한뒤에

그리고 나서 return 0; 를 통해서 프로그램을 종료한다는게 중요한 부분이라고 생각된다. 

이렇게 중간 과정에서 판가름 하고, 그동안 해놓았던 결과물을 출력해놓으면 안되고, 마지막에 갈래에 따라서

결과물이 출력되어야 할때는, 그 중간 과정을 이렇듯 스트링이라면 스트링에 지속적으로 추가해놓다가, 

갈래가 갈라질때 어느방향으로 나아가야할지 선택해주면 된다. 

 

그리고 c++에서 string ans;를 보면, int sum=0;을 정의하고, 지속적으로 sum+=10; sum-=5;등처럼, 

스트링에 원하는 문자열을 추가적으로 연결해서 스트링을 늘려 나갈 수 있다. 

그걸 알아야 이 문제를 경우를 나누어서 마지막에 딱 선택해서 그동안 쭉 저장한 스트링 문자내용을

출력하면서 끝낼 수 있는 것이다.