C++ [자료구조] / #Stack 구조와 클래스 사용법

Stack

---

Stack 정의 및 특징

- 스택은 대표적인 LIFO(Last In First Out) / 제일 마지막에 넣은 데이터가 처음으로 빠져나오는 구조.

- stack은 후입선출의 대표적인 자료구조이다.

- STL(Standard Template Library) 속 stack은 stack 자료구조를 사용자가 편하게 쓸 수 있도록 해당 자료구조를 클래스로 구현해놓았다.

- stack의 가장 큰 특징은 후입 선출이다. 따라서 stack에 접근할 수 있는 원소는 top에 위치한 원소가 유일하다. 만약 가장 아래에 위치한 원소에 접근하고자 한다면 상위의 모든 원소를 제거하는 과정이 필요하다.

 

이해를 위한 예시

- stack의 구조는 마치 프링글스와 같다. 과자 생산공장에서 용기에 과자를 담을 때 가장 아래부터 차곡차곡 쌓아올린다. 그리고 그 과자를 구매한 우리는 가장 위에서부터 하나씩 꺼내서 먹어야한다. 가장 아래의 과자는 가장 마지막에 먹을 수 밖에 없다.(처음부터 가장 아래의 과자를 먹을 순 없다.)

 

멤버 함수

---

#include <stack>

stack<int> stack;

stack.push(element)	// 데이터를 추가
stack.pop()	// top 데이터를 삭제
stack.top()	// 최상위 데이터 반환
stack.size()	// 스택의 현재 사이즈를 반환
stack.empty()	// 스택이 비어있는지 확인

intellisense 더보기

1. sta.push(x);

- x 요소를 스택에 삽입

- void 반환

---

2. sta.pop();

- 스택의 top()요소를 제거

- void 반환

---

3. sta.top();

- 스택의 가장 위에 위치한 요소를 반환

---

4. sta.size();

- 스택에 담긴 요소의 개수를 size_t (unsigned int)형으로 반환

---

5. sta.empty();

- 스택이 비어있으면 true, 아니면 false를 bool형으로 반환

 

클래스 사용 예시

---

 

코드 더보기

#include <iostream>
#include <stack>

using namespace std;

int main()
{
	stack<int> sta;
	cout << "stack size : " << sta.size() << '\n';
	cout << "stack empty : " << sta.empty() << '\n';
	cout << '\n';
	for (int i = 1; i <= 10; i++)
	{
		sta.push(i);
	}

	cout << "stack size : " << sta.size() << '\n';
	cout << "stack empty : " << sta.empty() << '\n';
	cout << "stack element : ";
	for (int i = 0; i < 10; i++)
	{
		cout << sta.top() << ' ';
		sta.pop();
	}

	return 0;
}

- stack 객체 생성 직후는 size = 0, empty = true가 출력되는 것을 볼 수 있다.

- 이후에 1~10까지 차례로 추가한 후에는 size = 10 , emtpy = false인 것을 볼 수 있다.
- 또한 원소를 확인할 때 top에 위치한 원소만 확인할 수 있기 때문에 top을 출력할 때마다 pop으로 top에 위치한 원소를 제거하여 마지막 원소까지 출력하였다.
- 마지막 원소까지 출력하였기 때문에 마지막의 stack은 비어있는 상태가 된다.