[알고리즘/C++] - Stack쌓고 나서스가 되.

오늘은 스택에 대해서 알아보도록 하겠습니다.

스택하면 그가 빠질 수 없습니다..

 

 

스택이란. 후입선출(Last In First Out—LIFO) 특성을 가지는 자료구조(Data Structure)를 일컫는다. 

나무위키를 가져와보았습니다.

 

간단하게 말해서 스택이란, 나중에 들어온 녀석이 먼저나간다! 라는 개념입니다. 박힌 돌보다 굴러온 돌이 더 먼저 빛을 보다니 버릇이 없네요

스택이라는 데이터 공간 속에 계속해서 데이터를 쌓아두었다가, 데이터들을 사용하고자 한다면, 가장 나중에 넣은 데이터를 꺼내게 됩니다. 

그 전에 넣어둔 데이터들은 가장 위 데이터들이 나갈 때까지 꺼내지 못합니다..

데이터를 넣거나 빼는 데에 걸리는 시간 복잡도도 O(1), 가장 나중에 넣은 데이터를 한 번 확인하는 데에도 O(1)의 시간복잡도를 가집니다!. 굉장히 빠른 속도죰

이러한 구조는 항상 유리한 것만은 아니지만 시간복잡도가 빠른만 특정 상황들에서 유리하게 작용합니다

조금이라도 이해가 되시길 바라며 저의 발그림을 첨부합니다.

스택은 C++에서 <stack> 라이브러리를 통해 제공됩니다.

stack에 자주 사용되는 함수는 다음과 같습니다.

stack<int> st;	스택을 선언합니다.
st.pop();	가장 나중에 들어온 데이터를 삭제합니다.
st.push(n);	데이터를 추가합니다.
st.top();	가장 나중에 들어온 데이터를 조회합니다.
st.size();	원소의 개수를 확인합니다.
st.empty();	데이터가 비어있는지 체크합니다/

 

이제 이 개념을 활용해서 직접 Stack를 만들어봅시다!

제가 만든 스택은 좌표를 받아주며, 

정해진 공간 안에서만 데이터를 담아주고, 삭제 등의 작업 또한 실제 삭제가 아닌 인덱스를 통한 이동으로 진행됩니다.

떄문에 간단한 알고리즘에 대한 이해로만 사용하고, 

만약 실제로 활용할 스택을 만들고 싶다면 동적 데이터배열, 데이터의 삭제 등을 실제로 구현하는 것을 추천드립니다.

 

struct Position //스택에 넣어줄 데이터타입(좌표)
{
	int x, y;
};

struct MyStack {
	Position Array[1000]; //데이터를 담을 공간
	int nTopIndex = -1; //데이터 최상단을 가리키는 방향표
	void push(Position data) { //데이터의 삽입
		nTopIndex++;
		Array[nTopIndex] = data;
	}
	void pop() { nTopIndex--; } //데이터의 삭제
	bool empty() { return nTopIndex < -1; } //데이터 존재 여부
	Position top() { return Array[nTopIndex]; } //최상단 데이터 반환
};

 

스택은 C++에서<Stack> 라이브러리를 제공하고 있습니다.

저의 코드로는 스택을 이해하고 공부하는 용도로만 참고한 후, 이해가 완전히 되었다면 안정적이고 유익한 라이브러리 사용을 지향합니다!

 

https://solved.ac/problems/tags/stack

solved.ac

스택과 관련한 문제들은 solved.ac에서 stack태그를 통해 확인할 수 있습니다.

 

간단한 개념이기 때문에 간략하게 작성해보았습니다.

궁금한 점이나 잘못된 사항이 있다면 댓글로 문의 부탁드립니다 감사합니당!

반응형