자료구조 : 스택(Stack)

1. 스택의 정의

스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다.

그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다.

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다.

자료를 넣는 것을 '밀어넣는다' 하여 푸시(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 보관한 자료부터 나오게 된다.

이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다.

가장 가까운 값을 O(1)만에 찾아오는 특징이 있다.

 

2. 스택의 함수

push : 스택에 데이터를 추가 

pop : 스택에서 데이터를 삭제

top :  스택의 가장 위에 있는 데이터를 확인

empty : 스택이 비어있으면 참을 리턴

size : 저장된 데이터의 개수를 리턴

 

C++의 경우 STL stack, Java의 경우 java.util.Stack을 사용하는 것이 좋다.

 

3. 스택의 구현

push의 구현

stack[size] = val;

size +=1;

 

pop의 구현

stack[size-1] = null;

size -= 1;

 

4. 스택 관련 문제

백준 10828번 스택 : https://www.acmicpc.net/problem/10828

 

스택을 구현하는 문제

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

stack<int> s;

int main(void) {
	int t;
	cin >> t;
	while (t--) {
		string cmd;
		cin >> cmd;
		if (cmd == "push") {
			int num;
			cin >> num;
			s.push(num);
		}
		else if (cmd == "pop") {
			if (!s.empty()) {
				cout << s.top() << endl;
				s.pop();
			}
			else cout << "-1" << endl;
		}
		else if (cmd == "size") {
			cout << s.size() << endl;
		}
		else if (cmd == "empty") {
			cout << s.empty() << endl;
		}
		else if (cmd == "top") {
			cout << (s.empty() ? -1 : s.top()) << endl;
		}
		

	}
	//system("pause");
}

 

백준 9012번 괄호 : https://www.acmicpc.net/problem/9012

 

스택을 이용한 구현문제

 

1. 문자열을 순차적으로 읽는다.

2.1 여는 괄호'('를 읽으면 '('을 넣는다.

2.2 이때 닫는 괄호')'를 만나면 '('을 뺀다.

2.2.1 뺄수있는 '('가 없으면 올바른 괄호문자열이 아니다.

3. 입력이 끝나면 스택의 size를 확인한다. 

3.1 size가 0이면 올바른 괄호 문자열이다.

3.2 size가 0이 아니면 올바른 괄호 문자열이 아니다.

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

stack<char> s;

string valid(string str) {
	int strsize = str.size();
	for (int i = 0; i < strsize; ++i) {
		if (str[i] == '(') {
			s.push('(');
		}
		else if (str[i] == ')') {
			if (s.empty()) return "NO";
			s.pop();
		}
	}
	if (s.size() == 0) return "YES";
	else return "NO";
	
}
int main(void) {
	int t;
	cin >> t;
	getchar();
	while (t--) {
		while (!s.empty()) s.pop();
		string str;
		cin >> str;
		cout << valid(str) << endl;
	}

	//system("pause");
}

이렇게 괄호를 직접 넣는것 말고 카운트를 세면 더 간단하게 구현할수 있다.

 

백준 10799번 쇠막대기 : https://www.acmicpc.net/problem/10799

 

스택을 이용한 구현문제

빔으로 쇠막대기를 자르는데 빔과 쇠막대기는 괄호쌍으로 표현된다.

괄호를 닫을때 빔이면 빔으로 쇠막대기를 자른다.

이때 스택의 사이즈만큼 쇠막대기 조각이 생긴다. 

괄호를 닫을때 빔이 아니면 쇠막대기 조각이다.

 

1. 문자열을 순차적으로 읽는다.

2.1 여는 괄호'('를 읽으면 '('을 넣는다.

2.2 이때 닫는 괄호')'를 만나면 '('을 뺀다.

2.2.1 닫는 괄호가 ()빔이면 정답에 스택에 사이즈만큼 더한다. 

2.2.2 닫는 괄호가 쇠막대기라면 정답에 1을 더한다.

3. 정답을 출력한다.

 

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

stack<char> s;

int valid(string str) {
	int ans = 0;
	int strsize = str.size();
	for (int i = 0; i < strsize; ++i) {
		if (str[i] == '(') {
			s.push('(');
		}
		else if (str[i] == ')') {
			s.pop();
			if (str[i - 1] == '(') ans += s.size();
			else if (str[i - 1] == ')') ans += 1;
		}
	}
	return ans;
}
int main(void) {
	string str;
	cin >> str;
	cout << valid(str) << endl;
	//system("pause");
}

 

백준 1406번 에디터 : https://www.acmicpc.net/problem/1406

 

스택을 사용한 시뮬레이터 문제

L, D, B, P $의 명령이 주어진다.

각각은 왼쪽, 오른쪽 이동, 왼쪽 삭제, 왼쪽 추가이다.

일반적인 풀이 방법으로 풀면 시간초과가 나는 문제이다.

입력의 크기가 100,000이고 명령어 수가  500,000이므로 

모든 명령을 O(1)만에 수행해야 한다.

 

문자열|

문자열|문자열 

|문자열

편집기는 위와 같이 구성되어 있다.

이를 커서를 기준으로 스택두개로 만들면 알고리즘이 간단해진다.

 

L : 왼쪽 pop, 오른쪽 push

D : 왼쪽 push, 오른쪽 pop

B : 왼쪽 pop

P : 왼쪽 push

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <stack>
#include <cstdlib>
using namespace std;

stack<char> Left, Right;

int main(void) {
	char ch;
	int t;
	while (true) {
		ch = getchar();
		if (ch == '\n' || ch == '\0') break;
		Left.push(ch);
	}
	scanf("%d", &t);
	while (t--) {
		
		scanf(" %c", &ch);
		switch (ch) {
		case 'L':
			if (!Left.empty()) {
				Right.push(Left.top());
				Left.pop();
			}
			break;
		case 'D':
			if (!Right.empty()) {
				Left.push(Right.top());
				Right.pop();
			}
			break;
		case 'B':
			if (!Left.empty()) {
				Left.pop();
			}
			break;
		case 'P':
			char c;
			scanf(" %c", &c);
			Left.push(c);
			break;
		}
	}

	while (!Left.empty()) {
		Right.push(Left.top());
		Left.pop();
	}

	while (!Right.empty()) {
		printf("%c", Right.top());
		Right.pop();
	}
	//system("pause");
}