스택이란?
- 스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조입니다.
- 데이터의 입력과 출력 순서는 후입선출(LIFO:Last In First Out)입니다.
- C언어 프로그램에서 함수를 호출하고 실행할 때 프로그램 내부에서는 스택을 사용합니다.
- push : 데이터를 넣는 작업
- pop : 데이터를 꺼내는 작업
- top : push, pop 하는 위치
- botoom : stack의 가장 밑바닥 부분
void a() {/*...*/}
void b() {/*...*/}
void c() {
a();
b();
}
int main() {
c();
}위 코드의 실행순서를 아래의 그림으로 표현했습니다.
- 이와 같이 원통에 탁구공을 집어 넣는 것처럼 넣어주고 나중에 넣어준 것 부터 뺴내는 방식입니다.
- 여기서 눈여겨 볼 점은 E시점입니다. a 함수가 종료되는 시점에 pop을 하여 데이터를 제거합니다. 그리고는 z 함수로 돌아옵니다.
스택을 구현하는 프로그램
스택을 구현하는 실습을 해봅시다.
아래는 IntStack.h 소스파일 입니다.
/* int형 스택 IntStack(헤더) */
#ifndef ___IntStack
#define ___IntStack
/*--- 스택을 구현하는 구조체 ---*/
typedef struct {
int max; /* 스택 용량 */
int ptr; /* 스택 포인터 */
int* stk; /* 스택의 첫 요소에 대한 포인터 */
} IntStack;
/*--- 스택 초기화 ---*/
int Initialize(IntStack* s, int max);
/*--- 스택에 데이터를 푸시---*/
int Push(IntStack* s, int x);
/*--- 스택에서 데이터를 팝 ---*/
int Pop(IntStack* s, int* x);
/*--- 스택에서 데이터를 피크 ---*/
int Peek(const IntStack* s, int* x);
/*--- 스택 비우기 ---*/
void Clear(IntStack* s);
/*--- 스택의 최대 용량 ---*/
int Capacity(const IntStack* s);
/*--- 스택의 데이터 개수 ---*/
int Size(const IntStack* s);
/*--- 스택이 비어 있나요? ---*/
int IsEmpty(const IntStack* s);
/*--- 스택이 가득 찼나요? ---*/
int IsFull(const IntStack* s);
/*--- 스택에서 검색 ---*/
int Search(const IntStack* s, int x);
/*--- 모든 데이터 출력 ---*/
void Print(const IntStack* s);
/*--- 스택 종료 ---*/
void Terminate(IntStack* s);
#endif스택 구조체 IntStack : 스택을 관리하는 구조체
-
스택으로 사용할 배열을 가르키는 포인터 stk
스택으로 푸시된 데이터를 저장할 용도의 배열을 가르키는 포인터이며, 배열의 메모리 공간 할당은 Initialize 함수로 생성됩니다. -
스택의 최대용량 max
스택의 최대용량을 나타내는 멤버이며, 이 값은 배열 stk 배열의 요소 개수와 같습니다. -
스택 포인터 ptr
스택에 쌓여있는 데이터 개수를 나타내는 포인터입니다. 비어 있으면 ptr의 값은 0이 되고, 가득 차 있으면 max의 값과 같습니다. 가장 먼저 푸시된 바닥(bottom)의 데이터는 str[0], 가장 나중에 푸시된 꼭대기(top) 데이터는 stk[ptr - 1] 입니다.
아래는 IntStack.c 소스파일입니다.
/* int형 스택 IntStack (소스) */
#include <stdio.h>
#include <stdlib.h>
#include "IntStack.h"
/*--- 스택 초기화 ---*/
int Initialize(IntStack* s, int max)
{
s->ptr = 0;
if ((s->stk = calloc(max, sizeof(int))) == NULL) {
s->max = 0; /* 배열의 생성에 실패 */
return -1;
}
s->max = max;
return 0;
}
/*--- 스택에 데이터를 푸시---*/
int Push(IntStack* s, int x)
{
if (s->ptr >= s->max) /* 스택이 가득 참 */
return -1;
s->stk[s->ptr++] = x;
return 0;
}
/*--- 스택에서 데이터를 팝 ---*/
int Pop(IntStack* s, int* x)
{
if (s->ptr <= 0) /* 스택이 비어 있음 */
return -1;
*x = s->stk[--s->ptr];
return 0;
}
/*--- 스택에서 데이터를 피크 ---*/
int Peek(const IntStack* s, int* x)
{
if (s->ptr <= 0) /* 스택이 비어 있음 */
return -1;
*x = s->stk[s->ptr - 1];
return 0;
}
/*--- 스택 비우기 ---*/
void Clear(IntStack* s)
{
s->ptr = 0;
}
/*--- 스택 용량 ---*/
int Capacity(const IntStack* s)
{
return s->max;
}
/*--- 스택에 쌓여 있는 데이터 수 ---*/
int Size(const IntStack* s)
{
return s->ptr;
}
/*--- 스택이 비어 있는가? ---*/
int IsEmpty(const IntStack* s)
{
return s->ptr <= 0;
}
/*--- 스택은 가득 찼는가? ---*/
int IsFull(const IntStack* s)
{
return s->ptr >= s->max;
}
/*--- 스택에서 검색 ---*/
int Search(const IntStack* s, int x)
{
int i;
for (i = s->ptr - 1; i >= 0; i--) /* 꼭대기(top) → 바닥(bottom)으로 선형 검색 */
if (s->stk[i] == x)
return i; /* 검색 성공 */
return -1; /* 검색 실패 */
}
/*--- 모든 데이터 표시 ---*/
void Print(const IntStack* s)
{
int i;
for (i = 0; i < s->ptr; i++) /* 바닥(bottom) → 꼭대기(top)로 스캔 */
printf("%d ", s->stk[i]);
putchar('\n');
}
/*--- 스택 종료 ---*/
void Terminate(IntStack* s)
{
if (s->stk != NULL)
free(s->stk); /* 배열을 삭제 */
s->max = s->ptr = 0;
}
스택 관련 함수 만들기
-
Initialize : 초기화 함수
스택의 메모리 공간을 확보하며, 배열의 위한 메모리 공간을 만들 떄 스택은 비어 있어야 합니다. 따라서 ptr 값은 0, 요소의 개수는 max값을 받아 배열 str를 생성합니다. 스택의 개별요소는 stk[0] ~ str[max - 1]이 됩니다. -
Push 함수 : 스택에 데이터를 추가하는 함수
스택이 가득 차서 푸시할 수 없는 경우 -1를 반환하며, 그렇지 않다면 새로 추가할 데이터(x)를 배열의 요소 str[ptr]에 저장하고 스택포인터 ptr을 증가시킵니다. 성공하면 0을 반환합니다. -
Pop 함수 : 스택의 꼭대기(top)에서 데이터를 제거하는 함수
먼저 스택 포인터를 감소시킨고 str[ptr]의 값을 변수 x에 저장합니다.
팝에 성공할 경우에는 0을 반환하고 스택이 비어 있어 팝을 할 수 없는 경우에 -1를 반환합니다. -
Peek 함수 : 스택 꼭대기(top)를 몰래 엿보는 함수
스택이 비어있지 않으면 꼭대기 요소 str[ptr - 1]를 x에 저장합니다. -
Clear 함수 : 스택의 모든 요소를 삭제하는 함수
스택에 대한 푸시와 팝 등 모든 작업은 스택 포인터(ptr)를 바탕으로 이루어집니다. 따라서 스택의 배열 요솟값을 번경할 필요가 없습니다. 모든 요소의 삭제는 스택 포인터 ptr 값을 0으로 하면 끝납니다. -
Capacity : 용량을 확인하는 함수
스택의 용량 멤버 변수 max값을 반환하는 함수입니다. -
Size : 데이터 개수를 확인하는 함수
스택에 쌓여있는 데이터 개수 ptr 값을 반화하는 함수입니다. -
IsEmpty : 스택이 비어있는지 검사하는 함수
ptr에 저장된 값이 0 이하면 1, 그렇지 않으면 0을 반환합니다. -
Isfull : 스택이 가득 찼는지 검사하는 함수
ptr에 저장된 값이 max의 값 이상이면 1, 그렇지 않으면 0을 반환합니다. -
Search : 임의으 값을 검색하는 함수
임의의 데이터가 스택의 어디 위체에 있는지 검사하는 합수입니다. 검색은 꼭대기(top)에서 바닥(bottom)으로 진행되는데 그 이유는, 먼저 팝(pop)되는 데이터를 찾기 위해서입니다. 검색에 성공하면 요소의 인덱스를 반환하고 실패하면 -1를 반환합니다. -
Print : 모든 데이터를 출력하는 함수
스택에 쌓여있는 데이터를 bottom부터 top까지 출력합니다. -
Terminate : 종료 함수
Initialize 함수로 확보한 스택을 해제하고 용량 max와 ptr 값을 0으로 합니다.
스택의 장점
- 구조가 단순하여 구현이 쉬움
- 데이터 접근 속도가 빠름(스택 포인터 ptr을 이용하여 데이터에 저장, 삭제, 읽기가 빠름)
스택의 단점
- 데이터 메모리 크기를 미리 지정해야함
- 저장 공간의 낭비 발생할 수 있음
스택을 사용하는 프로그램
이 프로그램을 컴파일하기 위해서 위의 IntStack.h와 IntStack.c가 필요합니다.
아래는 IntStackTest.c 소스파일입니다.
/* int형 스택 IntStack의 사용 */
#pragma warning (disable:4996)
#include <stdio.h>
#include "IntStack.h"
int main(void)
{
IntStack s;
if (Initialize(&s, 64) == -1) {
puts("스택 생성에 실패하였습니다.");
return 1;
}
while (1) {
int menu, x;
printf("현재 데이터 수 : %d / %d\n", Size(&s), Capacity(&s));
printf("(1) 푸시 (2) 팝 (3) 피크 (4) 출력 (0) 종료 : ");
scanf("%d", &menu);
if (menu == 0) break;
switch (menu) {
case 1: /*--- 푸시---*/
printf("데이터 : ");
scanf("%d", &x);
if (Push(&s, x) == -1)
puts("\a오류 : 푸시에 실패하였습니다.");
break;
case 2: /*--- 팝 ---*/
if (Pop(&s, &x) == -1)
puts("\a오류 : 팝에 실패하였습니다.");
else
printf("팝 데이터는 %d입니다.\n", x);
break;
case 3: /*--- 피크 ---*/
if (Peek(&s, &x) == -1)
puts("\a오류 : 피크에 실패하였습니다.");
else
printf("피크 데이터는 %d입니다.\n", x);
break;
case 4: /*--- 출력 ---*/
Print(&s);
break;
}
}
Terminate(&s);
return 0;
}
