자료구조 :: 크기가 조정되는 배열 스택
크기가 조정되는 배열 스택을 구현해봤습니다. 처음 스택을 생성하여 초기화를 하면 스택의 크기는 0인 상태입니다. 그리고 데이터를 삽입하면 스택의 크기가 확장되고 데이터를 삭제하면 스택의 크기가 축소됩니다. 그런데 매번 삽입, 삭제할 때마다 스택의 크기, 즉 배열의 크기를 조정하면 속도상 비효율적이기 때문에 스택이 가득 차면 2배로 확장하고, 스택이 1/4만 남으면 1/2로 축소되도록 했습니다.
뭐, 이 정도 구현하는 건 그렇게 어려운 게 아니지만, 매번 이걸 짜는건 딱 질색이라서 C 라이브러리로 만들었습니다. C++는 어차피 STL이 존재하니까…
컴파일해서 실행해보면, 스택의 크기가 7로, 33으로 확장되고 다시 15로 축소되는 것을 볼 수 있습니다.
realloc :: http://www.cplusplus.com/reference/clibrary/cstdlib/realloc/
뭐, 이 정도 구현하는 건 그렇게 어려운 게 아니지만, 매번 이걸 짜는건 딱 질색이라서 C 라이브러리로 만들었습니다. C++는 어차피 STL이 존재하니까…
StackType.h
View source…
/*
* =========================================================================
*
* Filename: StackType.h
*
* Description: Stack with extensionable array
*
* Version: 1.0
* Created: 2009년 12월 19일 22시 53분 10초
* Revision: none
* Compiler: gcc
*
* Author: Yeonjae Kim (https://hisjournal.net), 6l4ck3y3 (at) gmail.com
* Company: CERT-IS
*
* =========================================================================
*/
#ifndef _STACKTYPE
#define _STACKTYPE
/*-------------------------------------------------------------------------
* Stack ADT Type
*------------------------------------------------------------------------*/
// Define element type.
typedef int element;
typedef struct StackType {
element *stack;
int top;
int size;
} StackType;
/*-------------------------------------------------------------------------
* Stack ADT Function
*------------------------------------------------------------------------*/
/*
* === FUNCTION ==========================================================
* Name: error
* Description: Exit after displaying error message.
* Parameter: *mesg - error message
* Retuen:
* =========================================================================
*/
void error (const char *mesg);
/*
* === FUNCTION ==========================================================
* Name: init
* Description: Initialize stack.
* Parameter: s - stack
* Retuen:
* =========================================================================
*/
void init (StackType *s);
/*
* === FUNCTION ==========================================================
* Name: is_empty
* Description: Return that stack is empty.
* Parameter: s - stack
* Retuen: If stack is empty, this returns 1.
* Otherwise 0.
* =========================================================================
*/
int is_empty (StackType *s);
/*
* === FUNCTION ==========================================================
* Name: is_full
* Description: Return that stack is full.
* Parameter: s - stack
* Retuen: If stack is full, this returns 1.
* Otherwise 0.
* =========================================================================
*/
int is_full (StackType *s);
/*
* === FUNCTION ==========================================================
* Name: push
* Description: Insert item to end of stack.
* Parameter: s - stack
* item - new data
* Retuen:
* =========================================================================
*/
void push (StackType *s, element item);
/*
* === FUNCTION ==========================================================
* Name: pop
* Description: Return first item of stack, and delete.
* Parameter: s - stack
* Retuen: This returns first data of stack.
* =========================================================================
*/
element pop (StackType *s);
/*
* === FUNCTION ==========================================================
* Name: top
* Description: Return first item of stack.
* Parameter: s - stack
* Retuen: This returns first data of stack.
* =========================================================================
*/
element top (StackType *s);
#endifStackType.c
View Source…
/*
* =========================================================================
*
* Filename: StackType.c
*
* Description: Stack with extensionable array
*
* Version: 1.0
* Created: 2009년 11월 04일 23시 40분 31초
* Revision: none
* Compiler: gcc
*
* Author: Yeonjae Kim (https://hisjournal.net), 6l4ck3y3 (at) gmail.com
* Company: CERT-IS
*
* =========================================================================
*/
#include <stdio.h>
#include <stdlib.h>
#include "StackType.h"
/*
* === FUNCTION ==========================================================
* Name: error
* Description: Exit after displaying error message.
* Parameter: *mesg - error message
* Retuen:
* =========================================================================
*/
void error (const char *mesg)
{
fprintf (stderr, "%s\n", mesg);
exit (1);
}
/*
* === FUNCTION ==========================================================
* Name: init
* Description: Initialize stack.
* Parameter: s - stack
* Retuen:
* =========================================================================
*/
void init (StackType *s)
{
s->top = -1;
s->size = 0;
s->stack = (element *) malloc (sizeof (element) * s->size);
if (s->stack == NULL)
error ("Memory Allocation ERROR");
}
/*
* === FUNCTION ==========================================================
* Name: is_empty
* Description: Return that stack is empty.
* Parameter: s - stack
* Retuen: If stack is empty, this returns 1.
* Otherwise 0.
* =========================================================================
*/
int is_empty (StackType *s)
{
return (s->top == -1);
}
/*
* === FUNCTION ==========================================================
* Name: is_full
* Description: Return that stack is full.
* Parameter: s - stack
* Retuen: If stack is full, this returns 1.
* Otherwise 0.
* =========================================================================
*/
int is_full (StackType *s)
{
return (s->top == (s->size - 1));
}
/*
* === FUNCTION ==========================================================
* Name: push
* Description: Insert item to end of stack.
* Parameter: s - stack
* item - new data
* Retuen:
* =========================================================================
*/
void push (StackType *s, element item)
{
if (is_full (s))
{
s->size = (s->size)*2 + 1;
s->stack = (element *) realloc (s->stack, sizeof (element) * s->size);
if (s->stack == NULL)
error ("Memory Allocation ERROR");
}
s->stack[++(s->top)] = item;
}
/*
* === FUNCTION ==========================================================
* Name: pop
* Description: Return first item of stack, and delete.
* Parameter: s - stack
* Retuen: This returns first data of stack.
* =========================================================================
*/
element pop (StackType *s)
{
if (is_empty (s))
error ("Stack NULL ERROR");
if (s->top < s->size/4)
{
s->size = (s->size) / 2;
s->stack = (element *) realloc (s->stack, sizeof (element) * s->size);
if (s->stack == NULL)
error ("Memory Allocation ERROR");
}
return s->stack[(s->top)--];
}
/*
* === FUNCTION ==========================================================
* Name: top
* Description: Return first item of stack.
* Parameter: s - stack
* Retuen: This returns first data of stack.
* =========================================================================
*/
element top (StackType *s)
{
if (is_empty (s))
error ("Stack Null ERROR");
else
return s->stack[s->top];
}Test
그럼, 정말로 스택의 크기가 조정되는지 다음의 코드로 확인해보겠습니다.#include <stdio.h>
#include "StackType.h"
int main (void)
{
int i;
StackType s;
init (&s);
for (i = 0; i < 4; i++)
push (&s, i);
for (i = 0; i < s.size; i++)
printf ("%x%c", (s.stack+i), ((i+1)%8) ? ' ' : '\n');
printf ("\n\n");
for (i = 0; i < 20; i++)
push (&s, i);
for (i = 0; i < s.size; i++)
printf ("%x%c", (s.stack+i), ((i+1)%8) ? ' ' : '\n');
printf ("\n\n");
for (i = 0; i < 20; i++)
pop (&s);
for (i = 0; i < s.size; i++)
printf ("%x%c", (s.stack+i), ((i+1)%8) ? ' ' : '\n');
printf ("\n\n");
}컴파일해서 실행해보면, 스택의 크기가 7로, 33으로 확장되고 다시 15로 축소되는 것을 볼 수 있습니다.
참고 문헌
스택 :: http://www.winapi.co.kr/clec/cpp2/19-3-1.htmrealloc :: http://www.cplusplus.com/reference/clibrary/cstdlib/realloc/