#3 코테준비 - 스택(Stack)

스택(Stack)

- 끝에서만 원소를 넣거나 빼는 자료구조

- 먼저들어간 원소가 나중에 나옴

(FILO : First In Last Out / 프링글스 통을 생각하면 편함)

 

- 최상단(top) 원소의 추가/제거/확인의 시간복잡도는 O(1) 

- 다른 원소의 확인/변경은 불가능함.

 

---

STL - Stack

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

int main(void) {

	stack<int> myStack;

	//스택에 원소 1을 삽입
	myStack.push(1);

	//스택에 원소가 있다면 최상단의 원소를 출력
	if (!myStack.empty()) cout << "최상단 원소: " << myStack.top() << endl;
	else cout << "원소 없음!"<<endl;

	//스택의 사이즈 출력
	cout << "스택의 사이즈 : " << myStack.size() << endl;

	//최상단 원소 삭제
	myStack.pop();

	//스택에 원소가 있다면 최상단의 원소를 출력
	if (!myStack.empty()) cout << "최상단 원소: " << myStack.top() << endl;
	else cout << "원소 없음!" << endl;

	//스택의 사이즈 출력
	cout << "스택의 사이즈 : " << myStack.size() << endl;
}

 

 

리스트,벡터와 다르게 쓰이는 함수가 몇개 없어서 정리 해봤다.

더 자세한 부분은 아래의 사이트에서 참고하시면 좋다.

 

https://cplusplus.com/reference/stack/stack/?kw=stack 

https://cplusplus.com/reference/stack/stack/?kw=stack

---

문제 풀어보기

백준 10828번 - 10828번: 스택 (acmicpc.net)

10828번: 스택

 

 

그냥 직접 명령어를 입력해서 stack의 기능을 구현하는 간단한 문제다.

 

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

int main(void) {

	ios::sync_with_stdio(0);
	cin.tie(0);

	int n = 0;
	cin >> n;
	stack<int> myStack;

	while (n--)
	{
		string s;
		cin >> s;

		if (s == "push")
		{
			int m;
			cin >> m;
			myStack.push(m);
		}
		else if (s == "pop")
		{
			if (myStack.empty()) cout << -1 << '\n';
			else {
				cout << myStack.top() << '\n';
				myStack.pop();
			}
		}
		else if (s == "size")
		{
			cout << myStack.size() << '\n';
		}
		else if (s == "empty")
		{
			if (myStack.empty()) cout << 1 << '\n';
			else cout << 0 << '\n';
		}
		else
		{
			if (myStack.empty()) cout << -1 << '\n';
			else cout << myStack.top() << '\n';
		}
	}

}

 

직접 스택을 구현해서 하셔도 되고 STL의 스택을 이용해서 풀어도 된다.

STL의 스택은 원소가 하나도 없을때 pop,top 함수를 사용하면 런타임 에러를 내니 조건에 맞게 함수들을 써서 구현하면 된다.