Stack(배열)

1. Stack 자료구조

지금까지는 연결리스트와 배열과 같은 구조만 배웠습니다. 이제 이것을 응용한 여러가지 자료구조들을 소개해볼까 합니다. 먼저 자료구조에는 크게 선형 자료구조와 비선형 자료구조가 있습니다. 선형 자료구조에는 Stack, Queue등이 있고, 비선형 자료구조에는 Tree, Graph등이 있습니다. 선형과 비선형은 가장 논리적인 그림으로 옮겨놨을 때 구조가 선형을 이루냐 안이루냐 차이입니다.

Stack은 선형중에서도 기본적인 자료구조입니다. LIFO(Last In First Out, 후입선출)을 사용합니다. 후입선출은 말 그대로 나중에 들어온 데이터가 제일 빨리 나옵니다.

좀 더 쉽게 말하면, 제가 좋아하는 호올스같이 저런 통에 넣다 뺀다고 생각하면 됩니다. 그러면 제일 늦게 들어간 호올스가 맨 위에 있기 때문에, 제일 먼저 꺼내게 됩니다.

좀 더 구체적인 그림은 아래 그림같은 느낌입니다.

여기서 Push는 데이터를 추가하는 함수이고 Pop은 데이터를 꺼내는 함수입니다. Top은 맨위에 데이터를 확인하는 함수입니다. Stack에서 쓰는 대표적인 세 함수이므로 알아두셔야 합니다.

2. Stack을 배열로 구현

그럼 바로 Stack을 배열로 구현해서 알아보겠습니다. 참고로 Stack이나 Queue같은 자료구조들을 보여드릴 때 배열로 한 번, 연결리스트로 한 번 보여드릴겁니다.

헤더파일

먼저 헤더파일 코드 부터 보겠습니다.

ArrayStack.h

#ifndef ARRAYSTACK_H
#define ARRAYSTACK_H

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

typedef int ElementType;

typedef struct tagNode {
	ElementType Data;
}Node;

typedef struct tagArrayStack {
	int Capacity;
	int Top;
	Node* Nodes;
}ArrayStack;

void AS_CreateStack(ArrayStack** Stack, int Capacity);
void AS_DestroyStack(ArrayStack* Stack);
void AS_Push(ArrayStack* Stack, ElementType Data);
ElementType AS_Pop(ArrayStack* Stack);
ElementType AS_Top(ArrayStack* Stack);
int AS_GetSize(ArrayStack* Stack);
int AS_IsEmpty(ArrayStack* Stack);
int AS_IsFull(ArrayStack* Stack);


#endif

원래는 Node구조체만 있었는데, Node구조체를 또 멤버변수로 하는 ArrayStack을 선언했습니다. 함수도 Push Pop Top빼고는 다 똑같습니다.

void AS_CreateStack(ArrayStack** Stack, int Capacity); ->스택 생성하는 함수
void AS_DestroyStack(ArrayStack* Stack); ->스택을 제거하는 함수
void AS_Push(ArrayStack* Stack, ElementType Data); ->Push(노드를 추가)하는 함수
ElementType AS_Pop(ArrayStack* Stack); ->Pop(노드를 꺼내는)하는 함수
ElementType AS_Top(ArrayStack* Stack); ->Top(노드를 꺼내 보고 다시 넣는)하는 함수
int AS_GetSize(ArrayStack* Stack); ->스택에 저장되어있는 노드의 개수를 반환하는 함수
int AS_IsEmpty(ArrayStack* Stack); ->스택이 비어있는지 알려주는 함수
int AS_IsFull(ArrayStack* Stack); ->스택이 가득 찼는지 알려주는 함수

소스파일

ArrayStack.c

#include "ArrayStack.h"

void AS_CreateStack(ArrayStack** Stack, int Capacity) {
	//스택을 자유 저장소에 생성
	(*Stack) = (ArrayStack*)malloc(sizeof(ArrayStack));

	//입력된 Capacity만큼의 노드를 자유 저장소에 생성
	(*Stack)->Nodes = (Node*)malloc(sizeof(Node) * Capacity);

	//Capacity 및 Top 초기화
	(*Stack)->Capacity = Capacity;
	(*Stack)->Top = -1;
}

void AS_DestroyStack(ArrayStack* Stack) {
	//노드를 자유 저장소에서 해제
	free(Stack->Nodes);

	//스택을 자유 저장소에서 해제
	free(Stack);
}

void AS_Push(ArrayStack* Stack, ElementType Data) {
	Stack->Top++;
	Stack->Nodes[Stack->Top].Data = Data;
}


ElementType AS_Pop(ArrayStack* Stack) {
	int Position = Stack->Top--;
	return Stack->Nodes[Position].Data;
}


ElementType AS_Top(ArrayStack* Stack) {
	return Stack->Nodes[Stack->Top].Data;
}

int AS_GetSize(ArrayStack* Stack) {
	return Stack->Top + 1;
}

int AS_IsEmpty(ArrayStack* Stack) {
	return (Stack->Top == -1);
}

int AS_IsFull(ArrayStack* Stack) {
	return (Stack->Capacity == AS_GetSize(Stack));
}

함수들이 전체적으로 짧고 이해하기 쉽습니다. 따라서 Push Pop Top만 보도록하겠습니다.

void AS_Push(ArrayStack* Stack, ElementType Data) {
	Stack->Top++; //함수의 Top을 1높여서 저장할 수 있는 공간을 확보합니다.
	Stack->Nodes[Stack->Top].Data = Data; //그 공간에 데이터 삽입.
}

ElementType AS_Pop(ArrayStack* Stack) {
	int Position = Stack->Top--; //맨 위칸의 Index값을 Position에 저장 후, Top하나 줄여서 공간을 한칸 없앱니다.
	return Stack->Nodes[Position].Data; //Position 요소에 Data 반환
}

ElementType AS_Top(ArrayStack* Stack) {
	return Stack->Nodes[Stack->Top].Data; //맨 위칸 Data만 반환
}

실행예시

그럼 바로 main함수에 구현해보겠습니다.
ArrayStackMain.c

#include "ArrayStack.h"

int main() {
	int i = 0;
	ArrayStack* Stack = NULL;

	AS_CreateStack(&Stack, 10);

	AS_Push(Stack, 3);
	AS_Push(Stack, 37);
	AS_Push(Stack, 11);
	AS_Push(Stack, 12);

	printf("Capacity: %d, Size: %d, Top: %d\n\n", Stack->Capacity, AS_GetSize(Stack), AS_Top(Stack));

	for (i = 0; i < 4; i++) {
		if (AS_IsEmpty(Stack)) {
			break;
		}

		printf("Popped: %d, ", AS_Pop(Stack));

		if (!AS_IsEmpty(Stack)) {
			printf("Current Top: %d\n", AS_Top(Stack));
		}
		else {
			printf("Stack Is Empty.\n");
		}

	}

	AS_DestroyStack(Stack);

	return 0;
}

결과

Capacity: 10, Size: 4, Top: 12

Popped: 12, Current Top: 11
Popped: 11, Current Top: 37
Popped: 37, Current Top: 3
Popped: 3, Stack Is Empty.

문제풀이

스택의 Capacity를 난수(0~100) 50개로 만들고, while문으로 스택을 값으로 가득 채우고, 가득찬 스택의 값을 스택이 빌 때까지 Pop하시오.

코드

#include "ArrayStack.h"
#include <time.h>

int main() {
	srand(time);

	ArrayStack* Stack = NULL;

	AS_CreateStack(&Stack, 50);

	while (!AS_IsFull(Stack)) {
		AS_Push(Stack, rand() % 100);
	}

	if (AS_IsFull(Stack)) {
		printf("Stack Is Full.\n");
	}

	printf("Capacity: %d, Size: %d, Top: %d\n\n", Stack->Capacity, AS_GetSize(Stack), AS_Top(Stack));

	while (!AS_IsEmpty(Stack)) {
		printf("Popped: %d\n", AS_Pop(Stack));
	}
	printf("Stack Is Empty.\n");

	AS_DestroyStack(Stack);

	return 0;
}

결과

Stack Is Full.
Capacity: 50, Size: 50, Top: 25

Popped: 25
Popped: 87
Popped: 11
Popped: 70
Popped: 96
Popped: 18
Popped: 44
Popped: 45
Popped: 54
Popped: 79
Popped: 50
Popped: 33
Popped: 75
Popped: 77
Popped: 65
Popped: 19
Popped: 76
Popped: 12
Popped: 31
Popped: 51
Popped: 98
Popped: 19
Popped: 80
Popped: 20
Popped: 19
Popped: 76
Popped: 28
Popped: 38
Popped: 46
Popped: 99
Popped: 76
Popped: 43
Popped: 34
Popped: 39
Popped: 24
Popped: 98
Popped: 73
Popped: 68
Popped: 55
Popped: 57
Popped: 34
Popped: 22
Popped: 43
Popped: 37
Popped: 91
Popped: 8
Popped: 22
Popped: 47
Popped: 71
Popped: 68
Stack Is Empty.