Stack
이 글은 기존에 다룬 Dynamic Array에 대한 개념과 소스 코드를 포함하고 있습니다.
이에 대한 정보가 필요하다면 아래를 참고해주세요. 아래 링크에서 Ctrl+F로 필요한 함수만 찾아볼 수 있습니다.
[Data Structure] 동적 배열(Dynamic Array) 구현하기 (새 창)
Stack이란?
스택은 나중에 들어온 데이터가 가장 먼저 나가는 후입선출(LIFO: Last-In First-Out) 형태의 자료 구조이다.
스택은 시스템의 활성 레코드, 웹 브라우저의 뒤로 가기, 그림판 등의 프로그램에서 작업 취소 (Ctrl+Z) 등에 활용된다.
구현 방법
스택을 구현하는 방법에는 ①배열을 활용하는 방법과 ②연결 리스트를 활용하는 방법이 대표적이다. 연결 리스트를 활용하는 방법은 나중에 알아보고, 이 글에서는 배열을 활용하여 스택을 구현할 것이다.
다만 정적인 배열을 사용하지 않고, 지난번에 구현한 동적 배열(Dynamic Array)를 활용하여 구현하여 메모리가 허락하는 한도에서 원하는 만큼의 데이터를 저장할 수 있게끔 하였다.
따라서 본 프로젝트는 Dynamic Array에 대한 소스 파일 4개와 스택의 헤더 파일, 스택의 C파일 총 6개의 소스 파일로 구성된다.
Dynamic Array에 대한 코드는 지난번 글에서 공개했으므로 Stack.h와 Stack.c, 그리고 main.c에 대한 내용만 언급할 것이다.
Stack.h
Stack.h는 Stack의 추상 자료형(ADT)으로 구성된 헤더 파일이다.
#pragma once
#include "DynamicArray.h"
typedef struct {
DynamicArray* darr;
int top;
} Stack;스택을 구조체로 선언하고 키워드 typedef을 사용하여 정의했다.
스택은 동적 배열과 top이라는 int형 변수로 구성되어 있다. top은 가장 나중에 저장된 데이터를 가리키는 인덱스로, 배열의 요소에 접근할 때 사용된다.
Stack* StkCreate(); // Stack 생성
int StkIsEmpty(Stack* stack); // Stack이 현재 비어있는지 검사
int StkStore(Stack* stack, Element* e); // Stack에 새로운 요소 저장
Element* StkPop(Stack* stack); // Stack에서 요소 꺼내오기 (배열에서 삭제됨)
Element* StkPeek(Stack* stack); // Stack에서 요소 조회하기 (StkPop과 유사하나 값을 읽기만 함)
void StkPrint(const Stack* stack);
void StkDestroy(Stack* stack); // Stack의 동적 할당 해제함수의 프로토 타입이 나열되어 있다.
Dynamic Array의 함수 이름을 정할 때와 같이 자료 구조의 이름을 함수 앞에 써서 관련된 함수를 사용할 때 알기 쉽게 하였다. (이를테면 DAGet()이나 StkPop() 함수)
StkPop() 함수와 StkPeek() 함수는 매우 유사하지만 전자의 경우 배열에서 데이터를 삭제하고 후자는 그렇지 않는다. 백준 문제를 풀다보면 가장 위의 데이터를 삭제하지 않으면서 조회하는 기능이 필요할 때가 있었기 떄문에 이 함수를 추가하게 되었다.
Dynamic Array의 함수들과 마찬가지로 함수가 제 기능을 정상적으로 수행하지 못하면 0(FALSE)이나 NULL 값을 반환하도록 설계하였다.
Stack.c
Stack.c는 함수가 실제로 정의되는 소스 파일이다. 함수 별로 살펴본다.
#include "Stack.h"
#include <stdlib.h>
#include <stdio.h>구현에 필요한 기본적인 라이브러리와 Stack.h를 include해주었다.
Stack* StkCreate()
StkCreate() 함수는 Stack을 생성하여 주소 값을 반환하는 함수이다.
Stack* StkCreate()
{
Stack* stack = (Stack*)malloc(sizeof(Stack));
if (stack != NULL) {
stack->darr = createDA();
if (stack->darr == NULL) {// DynamicArray의 메모리를 확보하지 못했다면
free(stack); // 동적할당에 성공했던 Stack의 메모리를 반환하고
return NULL; // NULL 값을 반환
}
stack->top = -1;// top은 가장 마지막에 저장된 요소를 가리키는 인덱스
return stack; // 이 값이 -1이면 stack은 비어있는 것으로 간주합니다.
}
return NULL;
}스택만 동적 할당이 성공할 것이 아니라, 스택 내부의 Dynamic Array도 동적 할당에 성공해야 한다. 이에 실패할 경우 앞서 동적 할당에 성공한 Stack은 무의미하므로 NULL 값을 반환하기 전에 이를 다시 free()로 반환하는 것을 잊지 말아야 한다.
int StkIsEmpty(Stack* stack)
스택이 비어 있는지 확인하는 함수이다. 스택의 자료에 접근하기 전에 활용된다.
int StkIsEmpty(Stack* stack)
{
if (stack->top == -1)
return TRUE;
else return FALSE;
}int StkStore(Stack* stack, Element* e)
스택에 자료를 저장하는 함수이다. 성공한다면 TRUE를 반환한다.
int StkStore(Stack* stack, Element* e) // 반환값 = 저장 성공 여부
{
if (stack != NULL && DAAdd(stack->darr, e)) {
stack->top++;
return TRUE;
}
return FALSE;
}스택의 배열이 Dynamic Array이기 때문에 데이터를 추가할 때에도 미리 구현해놓은 DAAdd() 함수를 사용하는게 좋다.
스택의 가장 나중에 저장된 데이터를 가리키는 변수 top을 증가시키는 것도 잊지 말자.
Element* StkPop(Stack* stack)
Element* StkPop(Stack* stack)
{
if (StkIsEmpty(stack) != TRUE) { // Stack이 비어있지 않다면,
Element* tmp = DAGet(stack->darr, stack->top);
if (tmp != NULL) {
stack->top--;
stack->darr->index--;
return tmp;
}
}
return NULL;
}스택에서 데이터를 꺼내오는 함수이다. 앞서 설명한 것처럼 가장 나중에 저장된 데이터를 꺼내오고, 그 데이터는 배열에서 삭제한다.
사실은 실제로 데이터가 배열에서 사라지진 않고, 끝을 가리키는 인덱스가 감소하면서 그 뒤의 데이터는 저장된 것으로 취급하지 않는 방식이다.
Element* StkPeek(Stack* stack)
바로 위의 StkPop() 함수와 매우 유사하지만 이 함수는 배열에서 데이터를 삭제하지 않고 열람이 가능하게 한다. 상황에 따라 유용하게 쓰일 수 있는 함수이다.
Element* StkPeek(Stack* stack)
{
Element* tmp = StkPop(stack); // StkPop 함수를 재활용합니다.
stack->top++; // StkPeek 함수는 Stack의 자료를 실제로 삭제하지 않고 열람만 하므로 다시 top을 증가시켜줍니다
return tmp;
}StkPop() 함수와 거의 같은 코드일 것이기 때문에 StkPop() 함수를 재사용하여 코드의 반복을 줄였다.
void StkPrint(const Stack* stack)
스택의 자료를 모두 출력하는 함수이다.
자료 구조가 스택인 만큼 최근에 저장된 데이터부터 출력하게 구현하였다. 스택이 정상적으로 구현되었는지 확인할 때 사용했다.
void StkPrint(const Stack* stack)
{
if (stack != NULL) {
for (int i = stack->top; i >= 0; i--) {
Element* tmp = DAGet(stack->darr, i);
printf("Name: %s\tAge: %d\n", tmp->name, tmp->age);
}
}
}Dynamic Array의 함수 DAGet()을 활용하여 구현하였다.
void StkDestroy(Stack* stack)
본 프로젝트에서 스택은 동적 할당으로 구현되기 때문에 할당 받은 스택을 메모리에서 해제하는 함수도 만들어주었다.
스택 내부의 배열 Dynamic Array는 메모리를 해제시켜주는 함수가 이미 존재하기 때문에 이를 재사용하였다.
void StkDestroy(Stack* stack)
{
if (stack != NULL) {
DADestroy(stack->darr);
free(stack);
}
}main.c
main.c는 구현한 스택을 테스트하기 위한 소스 파일이다. 목적이 테스트인 만큼 구현한 모든 함수를 최소 한 번씩 사용하였다.
#include <stdio.h>
#include "Stack.h"
#include "vld.h"필요한 도구를 불러온다. DynamicArray.h 파일은 Stack.h에서 불러오기 때문에 따로 포함할 필요는 없다.
int main(void)
{
Stack* stack = StkCreate();
if (stack == NULL) return;
Element e1 = { 24, "김철수" };
Element e2 = { 23, "박영희" };
Element e3 = { 21, "이진우" };StkCreate() 함수로 스택을 동적 할당 받아 생성한다.
만약 변수 stack에 NULL 값이 저장되어 있다면 프로그램을 종료한다. 그렇지 않다면 스택에 저장할 요소 세 개를 정의한다.
printf("\n*** Stack에 요소 세개 추가 ***\n");
StkStore(stack, &e1);
StkStore(stack, &e2);
StkStore(stack, &e3);
StkStore() 함수로 스택에 세 개의 데이터를 저장한다.
e1(김철수), e2(박영희), e3(이진우) 순서로 데이터를 저장했으므로 스택에서 데이터를 꺼내는 순서는 그 역순인 e3, e2, e1이다.
DAPrint(stack->darr);
printf("\n*** 현재 Stack 현황 ***\n");
StkPrint(stack);단순히 배열의 0번째부터 출력하는 DAPrint() 함수와 StkPrint() 함수로 스택의 데이터를 출력해보았다.
printf("\n*** Stack이 빌 때까지 요소 출력 ***\n");
while (StkIsEmpty(stack) != TRUE) {
Element* tmp = StkPop(stack);
printf("Name: %s\tAge: %d\n", tmp->name, tmp->age);
}이번엔 while문을 사용하여 스택이 빌 때까지 데이터를 계속해서 꺼내보았다. StkPop() 함수가 정상적으로 동작하는지 확인하기 위함이다.
StkIsEmpty()는 스택이 비어 있으면 TRUE를 반환한다.
printf("\n*** Stack에 새로운 요소 추가 ***\n");
Element e4 = { 42, "홍길동" };
Element e5 = { 52, "이순신" };
StkStore(stack, &e4);
StkStore(stack, &e5);이번엔 스택에 새로운 데이터를 저장한다.
e4, e5 순으로 저장하였으므로 스택에는 그 역순인 e5, e4로 저장된다.
DAPrint(stack->darr);
printf("\n*** 현재 Stack 현황 ***\n");
StkPrint(stack);데이터가 정상적으로 저장되었는지 확인해준다.
printf("\n*** Stack의 요소 조회***\n");
Element* tmp = StkPeek(stack);
printf("tmp = {%s, %d}\n\n", tmp->name, tmp->age);이번엔 StkPeek() 함수에 대한 테스트로 가장 나중에 저장된 데이터 e5를 변수 tmp에 저장하여 출력해본다.
StkDestroy(stack);
return 0;
}스택에 사용된 메모리를 반환해주는 함수 StkDestroy()를 끝으로 프로그램을 종료한다. 이 함수에 문제가 있다면 메모리 누수를 감지해주는 "vld.h"가 오류를 출력할 것이다.
실행 결과
Visual Leak Detector read settings from: C:\Program Files (x86)\Visual Leak Detector\vld.ini
Visual Leak Detector Version 2.5.1 installed.
*** Stack에 요소 세개 추가 ***
Name: 김철수 Age: 24
Name: 박영희 Age: 23
Name: 이진우 Age: 21
*** 현재 Stack 현황 ***
Name: 이진우 Age: 21
Name: 박영희 Age: 23
Name: 김철수 Age: 24
*** Stack이 빌 때까지 요소 출력 ***
Name: 이진우 Age: 21
Name: 박영희 Age: 23
Name: 김철수 Age: 24
*** Stack에 새로운 요소 추가 ***
Name: 홍길동 Age: 42
Name: 이순신 Age: 52
*** 현재 Stack 현황 ***
Name: 이순신 Age: 52
Name: 홍길동 Age: 42
*** Stack의 요소 조회***
tmp = {이순신, 52}
No memory leaks detected.
Visual Leak Detector is now exiting.
C:\Users\Hotaek\Desktop\2학년 여름\DS_Review\Stack\Stack\Debug\Stack.exe(프로세스 2344개)이(가) 종료되었습니다(코드: 0개).
이 창을 닫으려면 아무 키나 누르세요...
모든 출력이 예상과 같고 메모리 누수도 감지되지 않았다.
