#19 [C 자료구조] 스택: 자료 더미

스택(Stack)은 자료 저장 형태의 한 방식으로 큐와 정 반대되는 성질을 지닌다.

스택은 LIFO(Last In First Out) 방식으로 도시락 통에 차례로 도시락을 담고 다시 맨 위에서부터 꺼내는 경우를 생각해보면 된다.

석탄 또한 스택 형식

큐(Queue)는 스택과는 반대로 FIFO(First In First Out), 즉 먼저 온사람이 먼저 빠지는 경우의 수이다. 일반적으로 놀이공원 줄을 기다리는 것이 FIFO 방식이라 볼 수 있다.

 

스택의 개념

스택은 선형 자료구조의 하나로써, 저장된 자료들 사이의 선후관계가 모두 1:1인 경우를 말한다.

#3 자료구조의 분류 강의에서 썼던 자료구조 분류표이다.

자료구조	단순구조 (Simple)	정수(int)
		실수(float, double)
		문자열(char)
	선형구조 (Linear)	리스트(List)	선형리스트
			연결리스트
		스택(Stack)
		큐(Queue)
		데크(DeQue)
	비선형구조 (Non-Linear)	트리(Tree)	일반 트리
			이진 트리
		그래프(Graph)	방향 그래프
			무방향 그래프
	파일구조 (File Organization)	순차파일
		색인파일
		직접파일

다음과 같이 스택은 선형구조 안에 속한다!!

스택은 자료의 삽입과 삭제가 top에 해당하는 스택의 한 쪽 끝에서만 일어난다.

스택의 형태는 소괄호로 표현한다.

s = (a0,a1,a2,a3,a4)

여기서 top원소는 a4, bottom원소는 a0이며 그림으로 표현해보자면 다음과 같다.

스택의 모습

스택 함수 호출 시엔 다음과 같은 특성이 발현된다.

 

- 스택에서는 함수가 호출될 때마다 스택프레임(Stack Frame)과 활성레코드(Activation Record) 구조가 생성된다.

이들은 시스템 스택의 top에 배치된다.

- fp(frame pointer)는 이전 스택 프레임에 대한 포인터(복귀 주소)이다.

- sp(stack pointer)는 따로 다음에 쓸 스택 메모리의 주소를 저장하며 따로 저장된다.

즉 스택은 이전과 이후 값에 대한 정보를 같이 저장한다.

 

---

 

 

스택의 연산

스택의 가장 기본적인 연산은 '푸쉬'와 '팝'이다.

푸쉬(push)는 새로운 값을 기존의 top 위에 저장하는 것이다.

- 그러나 스택의 저장공간이 넉넉한지 추가 가능 여부를 사전에 판단해야한다.

 

팝(top)은 탑에 있는 자료를 제거한 뒤 출력, 전달하는 것이다.

- 그러나 bottom원소까지 이미 전부 출력했다면 부족현상(Underflow) 현상이 발생 가능하다.

- 따라서 공백 스택인지 여부를 판단해야한다.

 

이외의 stack의 연산자들을 살펴보자.

Stack CreateS(max_stack_size) //스택 생성
Boolean IsFull(stack, max_stack_size) // 스택 꽉 차있는지 검사
Stack Push(stack, item) // 스택 top에 값 대입
Boolean IsEmpty(stack) // 스택 비었는지 검사
Element Pop(stack) // 스택 top값 pop하고 제거

---

 

 

 

 

스택의 구현

스택의 구현은 배열 혹은 연결리스트 두 가지를 통해 이루어진다.

 

* 배열을 이용한 구현

 

*스택을 연결리스트 입장에서 봐도 간단하다.

---

 

 

 

배열로 구현한 스택

- push

void push(element item){
	if (top >= MAX_STACK_SIZE-1){
    	stackFull();
        return;
    }
    stack[++top] = item;
    
void stackFull(){
	fprintf(stderr, "스택이 꽉 찼습니다. 요소 추가가 불가능합니다");
    exit(EXIT_FAILURE);
}

위 Push 코드는 스택 사이즈에 여분이 있다면 ++top에 새로운 아이템을 집어 넣는 코드다.

아래 stackFull 코드는 꽉 찼을 때의 스택 오류를 출력해내는 코드다.

 

- pop

element pop() {
	if (top == -1 )
    	return stackEmpty();
    return stack[top--];
}

void stackEmpty(){
	fprintf(stderr, "스택이 비었습니다. 더 이상 자료가 없습니다.");
    exit(EXIT_FAILURE);
}

위 pop 코드로 top이 -1이 아니라면 꺼내는 코드다. 말그대로 이 코드는 배열에서 기인했기 때문에 bottom 인자는 [0]의 주소값을 가지고 있다. 따라서 -1이 아니라면 top을 꺼내고 지운다.

동적 배열로 구현한 스택

정적 배열로 구현한  스택의 단점

정적 배열은 다음과 같은 단점이 있기에 동적 배열로 스택을 구현하는 것이 훨씬 효율적이다.

1) 스택에 저장할 수 있는 노드의 개수가 제한된다.

2) 스택 생성 시 스택 크기를 미리 지정해야한다.

3) 최대 저장 가능 개수를 늘리지 못한다.

4) 따라서 메모리 낭비가 심할 수 있다.

--> 동적 배열 최고

 

정적 배열과 동적 배열의 메모리할당 비교

먼저 정적 배열이 메모리를 부여받는 방법을 살펴보자.

 

- 정적 배열

#include <stdio.h>

int main(void) { 
	int i, size = 5;
    int arr[5]
    for (i=0; i<size; i++) {
    	arr[i] = i;
    }
    for (i=0; i<size; i++) {
    	printf("%d\n", arr[i]);
	}
    return 0;
}

0~4까지의 숫자가 들어있는 배열의 모습이다. 그러나 6개 이상의 인자가 들어가기 위해선 정적 배열을 또 다르게 만들어줘야 한다는 단점이 존재한다. 따라서 우리는 조금 복잡하지만 효율적인 동적 배열을 쓴다.

 

-동적 배열

#include <stdio.h>
#include <malloc.h> // 동적 배열에 필요한 malloc 헤더를 불러온다.

int main(void) { 
	int i;
    int *arr;
    
    arr= (int*) malloc (sizeoff(int)*5); //int 5개를 가지는 arr 주소를 만들어준다.
    printf("%d\n", arr); //arr의 주소값을 출력해준다.
    
    for (i=0; i<size; i++) {
    	*(arr+i) = i;
        printf("%d\n", *(arr+i));
    }

	arr = (int*) realloc(arr, sizeof(int)*7); //새롭게 배열 크기를 정해준다.
    printf("%d\n", arr); //arr의 주소값을 출력해준다.

    for (i=0; i<size; i++) {
    	printf("%d\n", arr[i]);
	}
    free(arr);
    return 0;
}

malloc 과 realloc 두 함수를 이용해 arr의 배열을 5개에서 7개로 늘려주는 작업을 진행했다. 필요시 capacity를 증가시킬 수 있다는 큰 장점이 있다. 대부분의 배열 코딩은 이 동적 배열을 이용한다.

---

 

 

다중 스택(Multiple Stack)

스택이 단일하게 존재하지 않게 여러 개가 있거나 하나의 스택을 여러 개의 스택으로 쪼갠 것을 다중 스택이라 말한다.

 

하나의 스택을 동일한 크기로 쪼갰을 때 그 경계값은 다음과 같이 표기한다.

top과 boundary에 대한 개념을 알고 다중 스택을 만드는 법을 살펴보자.

#define MEMORY_SIZE 100
#define MAX_STACK_SIZE 100 //메모리와 스택사이즈를 미리 설정해준다. 맥스 스택넘버 + 1의 값을 넣어주면됨.

element memory[MEMORY_SIZE];

int top[MAX_STACKS];
int boundary[MAX_STACKS];
int n;

top[0] = boundary[0] = -1 //stack의 처음은 -1이다
for (i=1, i<n; i++)
	top[i] = boundary[i] = (MEMORY_SIZE/n)*i; //for문을 이용해 n개의 스택으로 쪼개준다.
boundary[n] = MEMORY_SIZE-1;// 99가 될것이다.

이렇게 하면 n개로 쪼개지는 스택을 만들 수 있다.

다중 스택에 값을 넣고 빼는 방법은 기존 스택과 크게 다르지 않다.다만 boundary 개념만 신경써서 봐주면 된다.

 

- push

memory 스택안의 i번째 스택에 값을 넣어주는 방법이다.

void push(int i, element item){
	if ( top[i] == boundary[i+1]) // 이 부분이 단일 스택과의 차이점이다.
    	stackFull(i); //i를 안에 넣어줌으로써 해당 부분을 가리켜준다.
    momory[++top[i]] = item; //memory라는 이름의 스택안의 i의 탑에 값을 넣어준다.
}

 

-pop

memory 스택안의 i번째 스택의 top값을 빼오는 방법이다.

element pop(int i) {
	if (top[i] == boundary[i] )
    	return stackEmpty(i);
    return memory[top[i]--];
}

---

 

 

 

 

여기 까지 스택의 기본에 대해서 알아보았다. 다음 번엔 스택의 응용과 이를 통해 풀 수 있는 알고리즘에 대해서 알아보도록 하즈앗!