[자료구조] (Stack)스택이 뭐여 먹는겨?

 

안녕하세요 이번 포스팅은 자료구조 스택에 대하여 알아보겠습니다.

 

스택은 일단 쌓다라는 뜻인데요. 탑처럼 데이터를 쌓는 것을 상상하시면 좋습니다.

출처 위키백과

스택은 가장 먼저 입력된 데이터가 맨 아래 쌓이고 가장 최근에 입력된 데이터는 가장 위에 쌓이는 구조를 가지고 있어요. 이 구조를 LIFO(Last In, Final Out) 이라고 합니다.

그래서 항상 스택의 입출력은 맨 위에서만 일어납니다. 이 부분 즉 스택의 맨 위를 스택 상단(stack top) 이라고 합니다.

반대로 스택의 맨 밑바닥 부분은 스택 하단(stack bottom) 이라고 합니다.

이 각각의 스택에 저장되는 데이터를 요소(elements)라고 합니다.

여기서 삽인 연산(push) 와 삭제 연산(pop)이 일어납니다.

삽입 연산(push)는 스택의 맨 위에 요소를 추가 하는 것입니다. 이때 스택 상단이 1 커집니다.

반대로 삭제 연산(pop)은 스택 맨 위에 요소를 삭제하고 반환합니다.

만약 스택에 요소가 하나도 없으면 공백(empty)라고 하며, 스택이 스택의 크기만큼 가득 차 있다면 포화(full) 이라고 합니다.

---

스택의 과정을 추상화 해보는것도 꽤나 중요하다고 생각합니다.

스택의 연산들을 생각해보면

init(): 스택을 초기화한다.
is_empty(): 스택이 비어있으면 TRUE, 아니면 FASLE를 반환한다.
is_full(): 스택이 가득 차 있으면 TRUE, 아니면 FASLE를 반환한다.
size(): 스택 내의 모든 요소들의 개수를 반환한다.
push(a): 주어진 요소를 스택의 맨 위에 추가한다.
pop(): 스택 맨 위에 있는 요소를 삭제하고 반환한다.
peek(): 스택 맨 위에 있는 요소를 삭제하지 않고 반환한다.

요 종도 쓸 수 있어요.

만약 스택이 요소로 가득 차 있으면 더 이상 채울 수 없겠죠. 이미 꽉 찼는데 push 하면 overflow 가 발생합니다. 넘쳐요 넘쳐.

반대로 스택에 요소가 없는데 여기서 pop를 한다면 이미 아무것도 없는데, 가져갈게 없는데 가져가려고 하면 underflow가 발생해요.

스택에서는 push와 pop이 가장 중요합니다.

push의 일련 과정을 설명해본다면
1. 스택이 가득 차 있는지 먼저 확인한다.
2. 가득 차 있다면 오류가 발생하고 과정을 종료한다. ( 만약 여러분들이 프로그램 자체를 종료하고 싶으면 그래도 되고 종료까진 하고싶지 않다면 코딩 할때 하고 싶으신대로 하시면 됩니다.)
3. 스택이 가득 차 있지않다면 top를 1증가 시킵니다. (top은 스택의 상단입니다.)
4. top에 요소를 넣습니다.

이제 pop의 과정을 보겠습니다.
1. 스택이 비어있는지 확인한다.
2. 비어있다면 오류가 발생하고 과정을 종료한다. ( 만약 여러분들이 프로그램 자체를 종료하고 싶으면 그래도 되고 종료까진 하고싶지 않다면 코딩 할때 하고 싶으신대로 하시면 됩니다.)
3. 스택이 비어있지 않다면 top이 가르키는 요소를 삭제합니다.
4. top을 1 감소 시킵니다.
5. 삭제된 요소를 반환합니다.

여기서 의아하실수도 있는 점이 하나 있습니다 과정 3,4,5가 약간 의심스러울 수 있습니다.
구체적으로 설명하면 top의 요소를 삭제하는데 이건 실제로 삭제하는게 아닙니다. (이게 뭔 개똥같은 소리냐)
그냥 해당 요소를 쓰레기값 취급하는것 입니다. 나중에 우리가 다시 push 한다면 새로운 값이 들어가 재구실을 하는것이기 때문에 굳이 굳이 안지우고 그냥 쓰레기값 취급하면서 top을 1감소 시키는거죠.
반환은 초반에 말해드린대로 삭제된 값을 반환합니다.

 

내가 직접 만듦

과정을 그림으로 표현한다면 이렇게 표현할 수 있어요.

먼저 push(A) 를 하면 A가 쌓이고 push를 할때마다 그 위에 쌓여요.

그러다가 pop()을 하면 맨 위의 요소를 삭제하고 반환합니다.

---

스택은 배열과 연결리스트(링크드 리스트)로 만들 수 있습니다.

서로 장단점이 있습니다.

배열로 스택을 만든다면
구현하기 쉽습니다. 근데? 공간이 제약되어있죠. 배열은 크기가 동적이 아니니 필요에따라서 바꾸기가 애매합니다.


하지만 연결리스트(링크드리스트)로 만든다면
크기를 동적으로 마음대로 활용할 수 있다는 점입니다. 근데? 포인터를 위한 추가적은 메모리 공간이 필요합니다.
포인터를 위한 추가적인 메모리 공간이 필요하다는 말은 즉 연결리스트는 노드들이 연결된 형태인데 이 노드들은 자신의 데이터와 다음 노드의 주소를 가지고있는데 이 다음 노드의 주소를 추가적으로 저장할 공간이 필요한것은 의미합니다. (주소의 크기는 4바이트입니다.) 노드 하나마다 4바이트씩 더 차지하는것입니다. 히익!

---

스택 코드도 안보면 섭하니까 한번 살펴보겠습니다.

 

#include <stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE 100 //스택 크기를 일단 100칸으로 설정했습니다

typedef int Element; //이렇게 쓰면 나중에 자료형을 바꿀때 좋습니다. int만 원하는 자료형으로 바꾸면 되요.

Element data[MAX_STACK_SIZE];  //배열 선언
int top; //전역변수 top이 지역변수라면 함수 호출때마다 귀찮아지는 수고를 덜기위해 전역변수로 했습니다.

void error(char str[]) //애러가 발생하면 종료해주는 함수
{
	printf("%s \n", str);
	exit(1);
}

void init_stack() { top = -1; } //스택의 초기화, -1로 초기화 하는 스택이 0부터 시작하기때문입니다.
int is_empty() { return top == -1; } //스택이 공백인지 확인하는 함수
int is_full() { return top == MAX_STACK_SIZE - 1; } //스택이 포화인지 확인하는 함수
int size() { return top + 1; } //스택의 사이즈를 확인하는 함수

//스택은 0부터 시작하기때문에 top의 값이 2라면 스택의 사이즈는 3입니다

void push(Element e) //push 스택의 top을 1 늘리고 그곳에 받은 요소를 넣는 함수
{
	if (is_full())
		error("스택 포화"); //스택이 포화라면 애러가 발생
	else
		data[++top] = e; //먼저 top를 1늘리고 요소을 그곳에 넣는다는 뜻입니다
}

Element pop() //pop 스택의 top의 요소를 반환하고 top을 1 줄이는 함수
{
	if (is_empty())
		error("스택 공백"); //스택이 공백이라면 애러가 발생
	else
		return data[top--]; //먼저 top에 있는 요소를 반환하고 top을 1줄입니다.
}

Element peek() //peek 스택의 top의 요소를 확인만 하는 함수, 제거 안함
{
	if (is_empty())
		error("스택 공백");
	else
		return data[top]; //스택의 top의 요소를 반환합니다.
}

void print_stack(char msg[]) //스택을 출력하는 함수, msg는 그냥 스택만 덩그라니 출력하긴 쪼메 그래서 넣었어요.
{
	int i;
	printf("%s[%d] = ", msg, size());

	for (i = 0; i < size(); i++)
		printf("%d\t", data[i]);
	printf("\n");
}

void main()
{
	int i;

	init_stack(); //일단 초기화

	for (i = 1; i < 10; i++) //그냥 아무 요소나 넣으려고 for문 돌렸어요.
		push(i); 

	print_stack("스택 push 9회"); 
	printf("\tpop() --> %d\n", pop()); 
	printf("\tpop() --> %d\n", pop());
	printf("\tpop() --> %d\n", pop());
	print_stack("스택 pop 3회");
}

실행 결과를 보면?

실행 결과

잘 나왔네요 1부터 9까지 push 했고, pop를 3번 해서 9, 8, 7 순서대로 사라지고 1부터 6까지만 남았어요.

 

---

 

스택은 일상생활에서도 자주 쓰여요.

우리가 흔히 작업하다 잘못했을때 누르는 Ctrl + Z,
웹 브라우저 뒤로가기 등등 많이 쓰입니다.



오늘은 여기까지 하겠습니다.
감삼다!