[자료구조 with C언어] 스택 (Stack)

[자료구조 with C언어] 스택 (Stack)

---

INDEX

01. 스택이란?

02. 원리

03. 구현

 

---

01. 스택이란?

 

스택이라는 말은 들어보신 분들은

아마 게임에서 처음 들어보셨을 것 입니다. 

 

(좌) 출처: 성시훈 유튜브 / (우) 플레이스토어 게임 STACK 

 

공통적으로 게임에서 스택이 사용되는 의미는

"무언가 쌓인다" 라는 의미로 사용되곤 하는데요.

 

자료구조에서의 스택도 마찬가지입니다.

 

데이터를 순차적으로 쌓아서

필요할 때에 꺼내서 사용하는 구조가 스택입니다.

 

이때 구조 자체가 출입구가 동일한 원통형 구조라고 생각해야 합니다.

 

프X글스 아조시?

 

따라서 스택은 마지막으로 쌓였던 데이터가

먼저 빠져나가지는

후입선출(Last-in-Fist-out, LIFO) 구조입니다.

 

 

---

 

실제로 응용되고 있는 부분도 굉장히 많습니다.

 

Ctrl + Z를 누르면 undo가 되는 원리도 스택에 기반하고 있는데,

어떠한 동작을 수행할 때마다 스택에 해당 동작이 쌓이게 되고,

undo를 실행하게 되면 가장 마지막에 쌓였던 동작이 취소되는 원리입니다.

 

또한 크롬 등과 같은 웹 브라우저에서

뒤로가기도 동일한 원리입니다.

방문한 사이트가 스택에 쌓이고,

뒤로가기를 누르면 마지막으로 방문했던 사이트가 접속되는 원리입니다.

 

 

스택은 구현이 비교적 쉽고, 활용도가 높아

다양한 문제에 적용할 수 있습니다.

 

 

---

02. 원리

 

스택은 크게 두 가지의 동작으로 구분됩니다.

데이터를 넣는 것, 데이터를 빼는 것.

 

여기 원통프X글스 통과 데이터들이 있습니다.

 

여기서 9와 8을 순서대로 넣게되면

 

이런 순서로 통에 들어가게 됩니다.

 

다시 꺼내게 된다면 마지막으로 넣었던 데이터부터 꺼낼 수 있기때문에

8부터 원통에서 꺼내지게 됩니다.

 

 

 

다시 스택에 남은 데이터 2와 7을 넣으면

이러한 상태가 됩니다.

 

스택은 이렇게 데이터를 넣고 빼는 동작을 통해 작동됩니다.

 

---

03. 구현

 

스택은 기본적으로 추상 자료형으로 분류되기 때문에

정석으로 구현하려면 연결리스트로 구현되어야 합니다.

연결리스트 강의 바로가기

 

하지만 C언어에서는 구현의 편의를 위해

배열로 구현하는 것이 일반적입니다.

 

int Stack[100];
int Top = -1;

Top은 항상 Stack의 가장 맨 위 부분의 index를 가집니다.

Top을 통해 스택의 맨 위에 접근하여

데이터를 삽입하거나 제거할 수 있습니다.

 

주의할 점은 Stack에서는

Top을 통해서만 제한적으로 접근 가능한 구조라는 점입니다.

 

 

아래는 스택의 대표적인 연산입니다.

push(data)	data를 Stack의 가장 위에 추가
pop()	Stack의 가장 위에 있는 data를 제거
top()	Stack의 가장 위에 있는 data를 반환
size()	Stack에 들어있는 data 수를 반환
empty()	Stack이 비어있으면 true(1), 그렇지 않으면 false(0) 반환

 

void push(int data)
{
	Stack[++Top] = data;
}

void pop()
{
	Top--;
}

int top()
{
	return Stack[Top];
}

int size()
{
	return Top + 1;
}

int empty()
{
	return -1<Top ? 0 : 1;
}

 

 

	printf("9를 삽입\n");
	push(9);
	printf("8을 삽입\n");
	push(8);
	printf("현재 스택 사이즈 : %d\n",size());
	if(empty()) printf("스택이 비었습니다.\n");
	else printf("스택에 데이터가 존재합니다.\n");
	printf("Top 데이터 : %d\n",top());
	printf("Top 데이터 제거\n");
	pop();
	printf("현재 스택 사이즈 : %d\n",size());
	printf("Top 데이터 : %d\n",top());
	printf("Top 데이터 제거\n");
	pop();
	if(empty()) printf("스택이 비었습니다.\n");
	else printf("스택에 데이터가 존재합니다.\n");

 

9와 8을 삽입하면 스택의 상태가

아래와 같이 변하게 됩니다.

 

현재 스택의 사이즈는 Top+1 즉, 2이고,

스택의 데이터가 1개 이상 존재하는 상태입니다.

 

현재 스택의 Top 번 째는 8이고,

 pop() 연산을 수행하게 되면

스택의 상태는 이렇게 변하게 됩니다.

 

Top의 값만 1 감소 시킨 것이기 때문에

위 처럼 실제로 배열에서 8이 삭제되지는 않습니다.

 

하지만 Stack은 Top을 통해서만 제한적으로 접근 가능한 구조이기 때문에

8은 삭제된 것이나 다름 없습니다.

 

이때의 스택의 사이즈는 

 

한번 더 스택의 Top번 째 데이터를 확인하면 9이고,

pop() 연산을 수행하면 

Top은 -1이 됩니다.

 

현재 스택은 비어있는 상태가 됩니다.

 

---

스택의 구조는 다양한 문제에 적용할 수 있기 때문에

주요 자료구조입니다.

 

아래 스택 기본 구현 문제를 풀이해보면

스택의 구조에 대해 잘 이해할 수 있습니다.

 

10828번: 스택