[C++] STL stack 사용법

Stack

스택 (Stack) 은 제일 마지막에 넣은 데이터가 가장 먼저 나오는 LIFO (Last In First Out) 자료 구조이다. 

Stack 구조에 대한 자세한 설명은 아래 게시글에서 확인할 수 있다.

https://readytojoin.tistory.com/35

[ Algorithm ] 스택

 

C++에서 stack 은 C++ 표준 라이브러리 (STL; Standard Template Library) 로 정의되어 있기에, 필요할 때 선언한다면 편리하게 사용할 수 있다.

 

Stack - 선언

먼저, stack 을 사용하기 위해서는 stack 이라는 헤더 파일을 전처리기로 include 한 뒤 std::stack 을 정의해야 한다.

#include <stack>
std::stack<int> s1;
std::stack<char> s2;
std::stack<double> s3;

 

using namespace std; 선언을 한 상태라면 다음과 같이 선언할 수 있다.

#include <stack>
stack<int> s1;
stack<char> s2;
stack<double> s3;

 

각각 int 형 stack, char 형 stack, double 형 stack 을 선언하였다.

 

이후 코드에 편의를 주기 위해 앞으로 등장하는 코드에서 using namespace std; 선언을 한 상태라고 가정한다.

 

Stack - 데이터 추가

stack 에 데이터를 추가하려면 push() 메소드를 활용한다.

반환형이 없는 void 메소드이다. O(1) 의 시간복잡도를 가진다.

void push (const value_type& val);

stack<int> s;
s.push(10);
s.push(20);
s.push(30);

 

Stack - 데이터 삭제

stack 에서 데이터를 삭제하려면 pop() 메소드를 활용한다. 가장 마지막에 push 한 데이터가 먼저 삭제된다.

반환형이 없는 void 메소드이다. O(1) 의 시간복잡도를 가진다.

void pop();

stack<int> s;
s.push(10);
s.push(20);
s.push(30);

s.pop(); // 30 pop
s.pop(); // 20 pop
s.pop(); // 10 pop

 

Stack - 데이터 검토

stack 에 데이터가 비어있는지, 몇 개의 데이터가 들어있는지 확인하기 위해 empty(), size() 메소드를 사용할 수 있다.

bool empty();

empty() 메소드는 스택이 비었다면 1, 비어있지 않다면 0을 반환하며 시간복잡도가 O(1) 인 메소드이다.

size_type size();

size() 메소드는 스택에 들어있는 데이터의 개수를 반환하며 시간복잡도가 O(1) 인 메소드이다.

stack<int> s;
s.push(10);
s.push(20);

cout << s.empty() << endl;
cout << s.size() << endl;

 

Stack - 데이터 가져오기

stack 은 제일 마지막에 넣은 데이터가 가장 먼저 나오는 후입선출 구조라, 최상단에 있는 데이터 (제일 마지막에 넣은 데이터)를 확인할 수 있다. 이때 top() 메소드를 사용한다.

reference top();

top() 메소드는 스택에 제일 최상단에 있는 데이터를 반환하며 시간복잡도가 O(1) 인 메소드이다.

stack<int> s;
s.push(10);
s.push(20);

cout << s.top() << endl; // 20
s.pop();
cout << s.top() << endl; // 10

 

Stack - 전체 코드

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

int main(void) {
	stack<int> s;
	s.push(10);
	s.push(20);

	cout << "Empty? " << (s.empty() ? "Yes" : "No") << endl;
	cout << "Size : " << s.size() << endl;

	cout << "Top : " << s.top() << endl; // 20
	s.pop();

	s.push(30);
	
	cout << "Top : " << s.top() << endl; // 30
	s.pop();
	
	cout << "Top : " << s.top() << endl; // 10
	s.pop();

	cout << "Empty? " << (s.empty() ? "Yes" : "No") << endl;
	cout << "Size : " << s.size() << endl;

	return 0;
}

stack 의 경우 iterator가 존재하지 않아 find 함수를 사용할 수 없다. index를 이용한 접근 및 탐색이 불가능하다.

 

Stack - STL 을 이용한 문제 풀이

https://www.acmicpc.net/problem/10828

10828번: 스택

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

int main(void) {
	int n; cin >> n;
	stack<int> s;

	while (n--) {
		string str; cin >> str;
		if (!str.compare("push")) {
			int value; cin >> value;
			s.push(value);
		}
		else if (!str.compare("pop")) {
			if (s.empty()) cout << -1 << endl;
			else {
				cout << s.top() << endl;
				s.pop();
			}
		}
		else if (!str.compare("size")) cout << s.size() << endl;
		else if (!str.compare("empty")) cout << s.empty() << endl;
		else if (!str.compare("top")) {
			if (s.empty()) cout << -1 << endl;
			else cout << s.top() << endl;
		}
	}

	return 0;
}