[자료구조] 스택을 C로 구현하기
in Study on Data Structure
학원에서 배운 C로 스택을 구현하는 과정을 이 포스트에다가 저장한다.
전체 소스코드
#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
typedef struct stack{
int* arr; //동적 메모리의 주소를 저장
int top; //배열 스택의 저장 위치
int capacity; //배열의 최대 용량
}stack;
void stack_init(stack* st, int size);
void push(stack* st, int data);
void pop(stack* st);
void print(stack* st);
void clear(stack* st);
int main() {
int choice;
stack st;
int size, data;
printf("스택의 크기 입력 : ");
scanf("%d", &size);
stack_init(&st, size); // 스택 초기화 함수
// st의 값을 변경할 수 있도록 주소값을 전송해야함. (Call by Address)
while (1) {
system("clear");
printf("*** Integer Stack ***\n\n");
printf("1. push\n");
printf("2. pop\n");
printf("3. print\n");
printf("4. clear\n");
printf("0. terminate\n\n");
printf("select : [ ]\b\b");
scanf("%d", &choice);
getchar();
switch (choice)
{
case 1:
printf("\n\ndata push : ");
scanf("%d", &data);
getchar();
push(&st, data);
getchar();
break;
case 2:
pop(&st);
break;
case 3:
print(&st);
break;
case 4:
clear(&st);
break;
case 0:
free(st.arr); // st.arr이 가리키는 동적메모리가 해제됨. arr 자체가 포인터 변수이므로 st.arr로 접근.
printf("종료합니다.\n");
exit(0);
}
}
return 0;
}
void stack_init(stack* st, int size) {
st->arr = (int*)malloc(sizeof(int) * size); // 배열에 저장
st->top = 0; // 저장할 위치가 0번째임을 가리킴.
st->capacity = size; // 입력 받은 용량만큼 count함.
}
void push(stack* st, int data) {
int top = st->top;
if (top >= st->capacity) {
printf("stack overflow가 발생합니다.\n");
return;
}
st->arr[top] = data;
st->top++; // 저장 후 탑의 값 증가
printf("저장완료.\n");
return;
}
void pop(stack* st) { // 코드 상으로 top의 위치를 조정하는 형식. 실제로 데이터를 꺼내는 것이 아님.
if (st->top <= 0) {
printf("stack underflow가 발생합니다.\n");
st->top = 0;
getchar();
return;
}
st->top--;
printf("데이터 값 : %d\n", st->arr[st->top]);
getchar();
return;
}
void print(stack* st) {
int cur = st->top - 1;
if (st->top == 0) {
printf("데이터가 없습니다.\n");
getchar();
return;
}
while (cur >= 0) {
printf("%d ", st->arr[cur]);
cur--;
}
getchar();
return;
}
void clear(stack* st) {
st->top = 0;
printf("초기화 완료.\n");
getchar();
return;
}
스택의 자료구조 정의
typedef struct stack{
int* arr; //동적 메모리의 주소를 저장
int top; //배열 스택의 저장 위치
int capacity; //배열의 최대 용량
}stack;
스택의 생성
void stack_init(stack* st, int size) {
st->arr = (int*)malloc(sizeof(int) * size); // 배열에 저장
st->top = 0; // 저장할 위치가 0번째임을 가리킴.
st->capacity = size; // 입력 받은 용량만큼 count함.
}
생성 코드를 통해서 동적 메모리를 할당하고, 자료를 저장할 포인터 st->top을 0으로 설정해준다.
그리고 스택의 용량을 미리 지정해준다.
스택의 자료 푸시(push)
void push(stack* st, int data) {
int top = st->top;
if (top >= st->capacity) {
printf("stack overflow가 발생합니다.\n");
return;
}
st->arr[top] = data;
st->top++; // 저장 후 탑의 값 증가
printf("저장완료.\n");
return;
}
값의 변경을 위해서 주소를 호출하며 데이터를 푸시한 후 top의 위치를 변경시켜준다.
스택의 용량 늘리기 (Vector)
만일 stack overflow가 발생할 시 저장을 계속하고 싶다면 realloc을 사용하여 용량을 늘리면 된다.
void push(stack* st, int data) {
int top = st->top;
if (top >= st->capacity) {
/*
printf("stack overflow가 발생합니다.\n");
*/
st->capacity *= 2; // 용량을 2배로 늘림.
// realloc(원래 데이터가 있던 주소, 재할당 크기)
st->arr = (int*)realloc(st->arr, sizeof(int) * st->capacity); // 데이터의 재할당
printf("스택의 크기가 2배로 증가되었습니다.\n");
printf("용량 : %d", st->capacity);
return;
}
st->arr[top] = data;
st->top++; // 저장 후 탑의 값 증가
printf("저장완료.\n");
return;
}
realloc은 이미 할당된 메모리를 재할당 시켜주는 함수이다.
이렇게 용량을 늘려가는 스택의 자료구조를 벡터(Vector)라고한다.
스택의 자료 팝(pop)
void pop(stack* st) { // 코드 상으로 top의 위치를 조정하는 형식. 실제로 데이터를 꺼내는 것이 아님.
if (st->top <= 0) {
printf("stack underflow가 발생합니다.\n");
st->top = 0;
getchar();
return;
}
st->top--;
printf("데이터 값 : %d\n", st->arr[st->top]);
getchar();
return;
}
여기서 핵심은 자료를 실제로 꺼내고 제거하는 것이 아니라
top의 위치를 변경시켜서 자료가 제거된 것 처럼 보이게 하는 것이다.
메모리 상에는 자료가 남아있지만, 새로운 자료를 push한다면 같은 자리에 덮어씌워지게 되므로
자연스럽게 이전 데이터는 삭제된다.
스택의 초기화
void clear(stack* st) {
st->top = 0;
printf("초기화 완료.\n");
getchar();
return;
}
따라서 top의 위치를 0으로 조정하면 자동으로 초기화 된 것으로 생각할 수 있다.
