자료구조 - Stack

최인규·2023년 7월 24일

DFS stack 자료구조

자료구조

목록 보기

2/3

앞서 자료구조의 기본이라고 볼 수 있는 Array와 Vector에 대해서 학습했다.

이번 포스팅과 다음 포스팅에서는 스택(Stack)과 큐(Queue) 자료구조에 대해서 정리해본다.

스택과 큐는 완전탐색 알고리즘인 BFS/DFS의 핵심과도 같다보니 반드시 잘 학습하고 넘어가야한다. 내장함수도 자주 쓰이다보니 외우기를 추천한다.
~~(사실 사용하다보면 저절로 외워지..)~~

자료구조의 특성에 대해서 소개하고, 코드로 사용하는 방법을 소개한 후에
이를 활용한 간단한 문제풀이까지 진행해본다.

1. What is Stack?

스택(Stack)은 "쌓다"라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태이다.
스택 구조를 가지는 실생활 속의 사례는 매우 많지만, 아래 그림을 통해
스택을 직관적으로 이해해보자. (출처: Data Structure Approach 2nd)

또한 스택은 정해진 방향으로만 쌓을 수 있으며, top으로 정한 곳을 통해서만 접근할 수 있다. 새로 삽입되는 자료는 top이 가리키는 가장 맨 위에 쌓이게 되며, 자료를 삭제할 시에도 top을 통해서 삭제 가능하다.

스택에 자료를 삽입하는 연산을 "Push", 삭제하는 연산을 "pop"이라고 하며, 이러한 스택의 구조를 "LIFO(Last in First out)"라고 부른다.

실생활 속 컴퓨터의 동작 중 다음과 같은 것들이 스택 자료구조를 활용한다.

뒤로 가기 기능(Ex: 웹 브라우저 방문 기록)

실행 취소

2. How to Use Stack?

1) Stack 선언

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main() {
	stack<int> st;
	stack<char> letter;
	stack<string> words;

	return 0;
}

앞서 학습했던 Vector와 매우 유사하다고 생각하면 된다.
C++ 기준으로는 Stack STL을 제공하기에 stack을 include 해준 후에 스택에 담을 자료형들을 <> 안에 표기해준 후에 선언해주면 된다...!
(위의 코드 기준, 각각 정수/문자/문자열을 담기 위해 Stack을 선언해줌!)

2) Stack 데이터 처리 및 접근

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main() {
	stack<int> st;
	
	//스택에 값 추가
	st.push(1);
	st.push(2);
	st.push(3);

	//top에 있는 원소에 접근
	cout << st.top();

	//스택에 값 제거(위에서부터!)
	st.pop();
	
	return 0;
}

그림과 코드를 함께 보면 된다.
코드 기준 중간에 top의 원소에 접근해서 출력한다면 가장 상단에 위치한
3이 출력됨을 확인할 수 있다..!

3) 기타 함수(size/empty)

크기를 출력해주는 내장함수 Size와 비어있는지 확인하는 empty에 대해
코드와 함께 확인해보고 정리를 해보자.

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main() {
	stack<int> st;
	
	//스택에 값 추가
	st.push(1);
	st.push(2);
	st.push(3);

	//top에 있는 원소에 접근
	cout << st.top() << "\n";
	cout << st.size() << "\n";
	
	if (st.empty())
		cout << "THIS IS EMPTY" << "\n";
	else
		cout << "THIS IS NOT EMPTY" << "\n";
	//스택에 값 제거(위에서부터!)
	st.pop();
	st.pop();
	st.pop();
	if (st.empty())
		cout << "THIS IS EMPTY";
	else
		cout << "THIS IS NOT EMPTY";

	return 0;
}

결과값을 예상해보고 아래 결과와 확인을 해보자.
1,2,3 차례대로 넣은 상태로 top에 있는 원소 3이 출력될 것이고,
크기는 3개가 들어있으므로 3이 출력되며, 비어있지 않으므로 "not empty"가 출력될 것이다.
3번 pop을 하게 되면 스택이 비게 되므로 "empty"가 출력될 것임을 예상할 수 있다!

<실행결과>

3. Problem Solving (feat . BOJ)

스택 자료구조의 기본을 확인할 수 있는 필수 문항 하나를 풀이해보자.

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

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main(void)
{
	int num;
	int temp;
	stack<int> s;
	string order;
	cin >> num;
	while (num--)
	{
		cin >> order;
		if (order == "push")
		{
			cin >> temp;
			s.push(temp);
		}
		else if (order == "pop")
		{
			if (s.empty())
				cout << "-1" << endl;
			else
			{
				cout << s.top() << endl;
				s.pop();
			}
		}
		else if (order == "size")
			cout << s.size() << endl;
		else if (order == "empty")
		{
			if (s.empty())
				cout << "1" << endl;
			else
				cout << "0" << endl;
		}
		else if (order == "top")
		{
			if (s.empty())
				cout << "-1" << endl;
			else
				cout << s.top() << endl;
		}
	}
	return 0;
}