[자료구조] C - 스택(Stack) - 배열을 이용한 구현

https://mobuk.tistory.com/21

[자료구조] C - 스택(Stack)

 

지난시간에는 스택의 기본적인 개념에 대해 알아보았다. 이번 시간에는 스택을 '배열'로 구현하는 방법에 대해 알아보겠다. 총 3가지의 방법을 소개하고 있다. 첫번째는 전역변수로 구현하는 방법, 두 번째는 함수의 데이터로 매개변수를 전달하는 방법, 마지막은 동적으로 할당한 배열로 구현하는 방법이다. 

 

전역변수로 구현하는 방법

이 방식은 스택으로 사용할 1차원 배열과 스택의 데이터 개수인 top 변수를 모두 전역변수로 구현하는 방법이다. 

1. 전역변수 선언

#define SIZE 100

typedef int element;

int top = -1;
element Stack_array[SIZE] = { 0 };

스택에 저장되는 데이터 타입의 변환 편의성을 위해 typedef를 이용해 element로 재정의 하였다. top은 가장 위에 있는 데이터의 위치를 나타내며, 공백일 때에는 -1로 정의하였다. 그 이유는 배열의 index가 0부터 시작하기 때문이다. 

 

2. 공백 상태 검사 함수

int is_empty() {
	return (top == -1);
}

top이 -1이면 즉, 공백상태이면 True를 반환하고 아니면 False를 반환한다.

 

3. 포화 상태 검사 함수

int is_full() {
	return (top == SIZE-1);
}

전체 사이즈보다 1작은 수가 top과 같다면 True, 아니면 False를 반환한다.

 

4. push

void push(element n)
{
	if (is_full == 0)
		exit(1);
	top++;
	Stack_array[top] = n;
}

포화상태이면 종료하고, 포화상태가 아니면 top을 증가시켜 그 자리에 데이터를 넣는다.

 

5. pop

void pop() {
	if (is_empty == 0)
		exit(1);
	Stack_array[top] = 0;
	top--;
}

공백상태이면 종료하고 아니면 데이터를 초기화(0으로 바꿈)하고 top을 감소시킨다.

 

6. print_stack_array

void print_stack_array() {
	for (int i = 0; i <= top; i++)
		printf("%d ", Stack_array[i]);
	printf("\n");
}

스택을 출력할 수 있는 함수이다.

 

출력테스트

#include<stdio.h>
#pragma warning(disable:4996)
#define SIZE 100

typedef int element;

int top = -1;
element Stack_array[SIZE] = { 0 };

int is_full() {
	return (top == SIZE - 1);
}

int is_empty() {
	return (top == -1);
}

void push(element n
)
{
	if (is_full == 0)
		exit(1);
	top++;
	Stack_array[top] =
		n;
}

void pop() {
	if (is_empty == 0)
		exit(1);
	Stack_array[top] = 0;
	top--;
}

void print_stack_array() {
	for
		(int i = 0; i <= top; i++)
		printf("%d ", Stack_array[i]);
	printf("\n");
}

void stack1() {
	push(1);
	push(2);
	push(3);
	print_stack_array();
	push(4);
	push(5);
	pop();
	print_stack_array();
}

int main() {
	stack1();
}

 

 

이 방식은 구현이 쉽고 직관적이다. 하지만 전역변수로 선언되기 때문에 한 프로그램 안에서 여러개의 스택을 동시에 사용하기는 어렵다는 단점이 있다. 

 

데이터를 함수의 매개변수로 전달하는 방법

한 프로그램 안에서 여러개의 스택을 동시에 사용하기 위해서는 java나 c++에서 객체 지향의 개념을 쓰면 가장 깔끔하게 처리할 수 있다. C에서도 간접적으로 구현할 수 있다. top과 stack을 구조체로 결합시키고 구조체의 포인터를 매개변수로 전달하면 된다. 필요할 때마다 구조체를 선언하여 만들면 된다. 

1. Stack 구조체 선언

#define SIZE 100

typedef int element;

typedef struct {
	int top;
	element Stack_array[SIZE];
}Stack;

 

2. isfull, isempty

int is_full(Stack*n)
{
	return(n->top == SIZE - 1);
}

int is_empty(Stack*n)
{
	return(n->top == -1);
}

top이 구조체 포인터 안의 변수이기 때문에 -> 연산자를 사용한다. 

 

3. push

void push(Stack*n, element x)
{
	if (is_full(n))
		exit(1);
	(n->top)++;
	n->Stack_array[n->top] =x;
}

Stack_array도 top과 똑같이 ->연산자로 바꿔주기만 하면 된다.

 

4. pop

void pop(Stack*n)
{
	if (is_empty(n))
		exit(1);
	n->Stack_array[n->top] = 0;
	(n->top)--;
}

 

5. print_stack_array

void print_stack_array(Stack * n)
{
	for(int i = 0; i <= (n->top); i++)
		printf("%d ",n->Stack_array[i]);
	printf("\n");
}

 

출력테스트

#include<stdio.h>
#pragma warning(disable:4996)
#define SIZE 100

typedef int element;

typedef struct {
	int top;
	element Stack_array[SIZE];
}Stack;

int is_full(Stack*n)
{
	return(n->top == SIZE - 1);
}

int is_empty(Stack*n)
{
	return(n->top == -1);
}

void push(Stack*n, element x)
{
	if (is_full(n))
		exit(1);
	(n->top)++;
	n->Stack_array[n->top] =x;
}

void pop(Stack*n)
{
	if (is_empty(n))
		exit(1);
	n->Stack_array[n->top] = 0;
	(n->top)--;
}

void print_stack_array(Stack * n)
{
	for(int i = 0; i <= (n->top); i++)
		printf("%d ",n->Stack_array[i]);
	printf("\n");
}

void stack1() {
	Stack a;
	a.top = -1;
	push(&a, 1);
	push(&a, 2);
	push(&a, 3);
	print_stack_array(&a);
	push(&a, 4);
	push(&a, 5);
	pop(&a);
	print_stack_array(&a);
}

int main() {
	stack1();
}

 

 

동적 배열 스택 구현하는 방법

이때까지 위의 방식은 배열의 크기가 고정적이었다. 즉, 스택이 가득차면 사용할 수 없고 가끔은 불필요한 메모리를 차지할 수 있다. 그래서 동적할당으로 배열을 선언한다면 문제점을 해결할 수 있다. 

 

1. Stacktype 구조체 선언

typedef int element;
typedef struct
{
	element* data;
	int capacity;
	int top;
}StackType;

capacity는 각 배열의 수용량을 의미하며, 가득찰 때 마다 늘려주고 값을 바꿔주면 된다.

 

2. init_stack

void init_stack(StackType* n)
{
	n->top = -1;
	n->capacity = 1;
	n->data = (element*)calloc(sizeof(element), n->capacity);
}

malloc과 다르게 calloc은 동적할당된 곳을 0으로 초기화해준다는 장점이 있다. 

 

3. delete

void delete(StackType* n)
{
	free(n);
}

 

4. isfull, isempty

int isfull(StackType* n)
{
	return (n->top == n->capacity - 1);
}

int isempty(StackType* n)
{
	return (n->top == -1);
}

 

5. push

void push(StackType* n, element x)
{
	if (isfull(n))
	{
		n->capacity *= 2;
		n->data = (element*)realloc(n->data, n->capacity * sizeof(element));
	}
	n->top++;
	n->data[n->top] = x;
}

 

6. pop

element pop(StackType* n)
{
	if (isempty(n))
	{
		fprintf(stderr, "ERROR: stack is empty");
		exit(1);
	}
	return n->data[(n->top)--];
}

 

7. print_stack

void print_stack(StackType * n)
{
	for(int i = 0; i <= n->top; i++)
		printf("%d ", n->data[i]);
	printf("\n");
}

 

출력테스트

#include <stdio.h>
#pragma warning(disable:4996)
#include <stdlib.h>
typedef int element;
typedef struct
{
	element* data;
	int capacity;
	int top;
}StackType;

void init_stack(StackType* n)
{
	n->top = -1;
	n->capacity = 1;
	n->data = (element*)calloc(sizeof(element), n->capacity);
}

void delete(StackType* n)
{
	free(n);
}

int isfull(StackType* n)
{
	return (n->top == n->capacity - 1);
}

int isempty(StackType* n)
{
	return (n->top == -1);
}

void push(StackType* n, element x)
{
	if (isfull(n))
	{
		n->capacity *= 2;
		n->data = (element*)realloc(n->data, n->capacity * sizeof(element));
	}
	n->top++;
	n->data[n->top] = x;
}

element pop(StackType* n)
{
	if (isempty(n))
	{
		fprintf(stderr, "ERROR: stack is empty");
		exit(1);
	}
	return n->data[(n->top)--];
}

void print_stack(StackType * n)
{
	for(int i = 0; i <= n->top; i++)
		printf("%d ", n->data[i]);
	printf("\n");
}

void stack2() {
	StackType s;
	init_stack(&s);
	push(&s, 1);
	push(&s, 2);
	push(&s, 3);
	print_stack(&s);
	pop(&s);
	print_stack(&s);
}

void main() {
	stack2();
}