+) stack 구조와 사용법, 재귀함수

🐱‍💻stack 구조와 사용법

Stack은 LIFO(Last In First Out) 구조를 가지고 있다.

간단한 사용법은 아래와 같다.

#include <iostream>
#include <stack>

using namespace std;

int main(){

	//stack 생성
	stack<int> s;

	//push()
	s.push(3);
	s.push(2);
	s.push(1);

	//top()
	cout << "top element: " << s.top() << endl;

	//pop()
	s.pop(); // 1이 삭제
	s.pop(); // 2가 삭제

	//size()
	cout << "stack size: " << s.size() << endl;

	//empty()
	cout << "Is it empty?: " << (s.empty() ? "Yes" : "No") << endl;

	return 0;

}

🐱‍🐉stack을 이용하는 재귀함수(recursion)

stack의 맨 상단에 있는 함수가 지금 실행되고 있는 함수다.

1. void recur(int x) {
2.	if(x==0) return;
3.	else{
4.		recur(x-1);
5.		printf("%d ", x);
6.	}
7. }

x = 3을 넣으면 1 2 3이 출력된다.

1) x에 3이 들어오면, 빈 스택 가장 아래칸에 recur(3), 4번째 줄까지 처리했다고 기록한다.

2) x에 2가 들어오면, 1) 칸의 위 칸에 recur(2), 4번째 줄까지 처리했다고 기록한다.

3) x에 1이 들어오면, 2) 칸에 위 칸에 recur(1), 4번째 줄까지 처리했다고 기록한다.

4) x에 0이 들어오면, return 되어 7. 줄로 간다.

이제, LIFO 구조로 인해 스택 위부터 처리된다.

결국, 1 2 3이 출력된다.