스택 (STACK)
데이터를 일시적으로 저장하기 위해 사용하는 자료구조
•
LIFO (Last In First Out)
•
Push
◦
스택에 데이터를 넣는 작업
•
Pop
◦
스택에서 데이터를 꺼내는 작업
•
Top
◦
Push, Pop 을 하는 위치
•
Bottom
◦
스택의 가장 밑바닥 부분
스택 만들기
InStack.h
#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
C
복사
스택 구조체 IntStack
•
스택을 관리하는 구조체, 3개의 멤버로 구성된다.
1.
스택으로 사용할 배열을 가리키는 포인터 stk
멤버 stk는 배열의 첫 요소를 가리키는 포인터이다.
•
스택으로 푸시된 데이터를 저장할 용도의 배열을 가리키는 포인터이다.
•
인덱스가 0인 요소 → 스택의 바닥(Bottom)
•
가장 먼저 푸시된 데이터를 저장하는 곳 → stk[0]
•
배열의 메모리 공간 할당 → Initialize 함수로 생성
2.
스택의 최대 용량 max
•
스택의 최대 용량을 나타내는 멤버
•
이 값은 배열 stk의 요소 개수와 같다.
3.
스택 포인터 ptr
•
스택에 쌓여 있는 데이터의 개수를 나타내는 멤버 → 스택 포인터 (Stack Pointer)
•
스택 비어있으면 → ptr의 값은 0
•
스택 가득차있으면 → ptr의 값은 max의 값
•
가장 먼저 푸시된 바닥(bottom) 의 데이터는 stk[0]
•
가장 나중에 푸시된 꼭대기(top) 의 데이터는 stk[ptr-1]
초기화 함수 Initialize
•
Initialize 함수는 스택의 메모리 공간(배열)을 확보하는 등의 준비 작업을 수행하는 함수이다.
•
배열을 위한 메모리 공간을 만들 때 스택은 비어 있어야한다.
•
따라서 스택 포인터 ptr값을 0, 요소의 개수는 max인 배열 stk를 생성한다.
•
또 매개변수 max로 받은 값을 스택 최대 용량을 나타내는 구조체의 멤버 max에 저장한다.
•
따라서 스택의 개별 요소는 바닥(bottom)부터 stk[0], stk[1] ~ stk[max - 1] 이 된다.
배열을 위한 메모리 공간을 확보하는데 실패하면 max의 값을 0으로 해야하는데, 이는 존재하지 않는 배열 stk에 다른 함수의 접근을 막기 위해서이다.
#include <stdio.j>
#include <stdlib.h>
#include "IntStack.h"
// 스택 초기화
int Initialize(IntStack *s, int max) {
s -> ptr = 0; // 스택 포인터 ptr의 값을 0으로
if ((s -> stk = calloc(max, sizeof(int))) == NULL) {
s -> max = 0; // 배열의 생성에 실패
// 요소의 개수는 max인 배열 stk 생성
return -1;
}
s -> max = max; // 매개변수 max로 받은 값을 스택 최대 용량을 나타내는 구조체의 멤버 max에 저장
return 0;
}
C
복사
푸시 함수 Push
•
Push 함수는 스택에 데이터를 추가하는 함수이다
•
스택이 가득차서 푸시할 수 없는 경우에는 -1을 반환한다
•
스택이 가득차지 않았다면 새로 추가할 데이터(x)를 배열의 요소 stk[ptr]에 저장하고 스택 포인터 ptr을 증가시킨다
•
마지막으로 푸시에 성공하면 0을 반환한다
// 스택 푸시
int Push(IntStack *s, int x) {
if (s->ptr >= s->max) // 스택이 가득참
return -1; // -1을 반환
s->stk[s->ptr++] = x; // 가득차지 않았다면 새로추가할 데이터(x)를 배열의 요소 stk[ptr]에
// 저장하고 스택 포인터 ptr을 증가시킨다.
return 0;
}
C
복사
IntStack.c에서 제공하는 함수만 사용하여 스택 작업을 수행하면 스택 포인터 ptr 값은 반드시 0이상 max 이하가 된다. 따라서 아래처럼 스택이 가득찼는지에 대한 검사는 관계연산자( ≥ ) 가 아니라 등가 연산자 (==)를 사용해도 된다.
if (s->ptr == s->max)
C
복사
팝 함수 Pop
•
Pop 함수는 스택의 꼭대기에서 데이터를 제거하는 함수이다
•
팝에 성공할 경우에는 0을 반환하고, 스택이 비어 있어 팝을 할 수 없는 경우에는 -1을 반환한다
•
먼저 스택 포인터 ptr의 값을 감소시키고, stk[ptr] 에 저장된 값을 포인터 x가 가리키는 변수에 저장한다
// 스택 팝
int Pop(IntStack *s, int *x) {
if (s->ptr <= 0) // 스택이 비어있다면 -> 팝 못한다
return -1; // -1을 반환
*x = s->stk[s->ptr--]; // 먼저 스택 포인터 ptr의 값을 감소시키고,
// stk[ptr]에 저장된 값을 포인터 x가 가리키는 변수에 저장한다.
return 0 //팝에 성공할 경우에는 0을 반환
}
C
복사
피크 함수 Peek
•
Peek 함수는 스택 꼭대기의 데이터를 ‘몰래 엿보는’ 함수이다
•
피크에 성공하면 0을 반환하고, 스택이 비어 있으면 -1을 반환한다
•
스택이 비어 있지 않으면, 꼭대기 요소 stk[ptr - 1] 의 값을 포인터 x가 가리키는 변수에 저장한다
•
데이터의 입력과 출력이 없으므로 스택 포인터는 변화하지 않는다
int Peek(const IntStack *s, int *x) {
if (s->ptr <= 0) // 스택이 비어 있으면
return -1; // -1을 반환
*x = s->stk[ptr - 1]; // 비어 있지 않으면, 꼭대기 요소 stk[ptr - 1] 의 값을 포인터 x가
// 가리키는 변수에 저장한다.
return 0; // 피크에 성공하면 0을 반환한다.
}
C
복사
스택의 모든 요소를 삭제하는 함수 Clear
•
Clear 함수는 스택에 쌓여있는 모든 데이터를 삭제하는 함수이다
스택에 대한 푸시와 팝 등 모든 작업은 스택 포인터를 바탕으로 이루어진다. 따라서 스택의 배열 요소값을 변경할 필요가 없다. 모든 요소의 삭제는 스택 포인터 ptr 값을 0으로 하면 끝난다.
void Clear(IntStack *s) {
s->ptr = 0;
}
C
복사
용량을 확인하는 함수 Capacity
•
Capacity 함수는 스택의 용량(멤버 max의 값)을 반환하는 함수이다
int Capacity(const IntStack *s) {
return s->max; // 스택의 용량(max)을 반환하여 확인
}
C
복사
데이터의 개수를 확인하는 함수 Size
•
Size 함수는 현재 스택에 쌓여있는 데이터의 개수(멤버 ptr의 값) 를 반환하는 함수이다
int Size(const IntStack *s) {
return s->ptr; // 현재 스택에 쌓여있는 데이터의 개수 확인
}
C
복사
스택이 비어있는지 검사하는 함수 IsEmpty
•
IsEmpty 함수는 스택이 비어있는지 검사하는 함수이다
•
스택이 비어 있으면 1, 그렇지않으면 0을 반환한다
int IsEmpty(const InStack *s) {
return s->ptr <= 0;
}
C
복사
스택이 가득찼는지 검사하는 함수 IsFull
•
IsFull 함수는 스택이 가득 찼는지 검사하는 함수이다
•
스택이 가득 찼으면 1, 그렇지 않으면 0을 반환한다
// 스택이 가득찼는가
int IsFull(const InStack *s) {
return s->ptr >= s->max;
}
C
복사
임의의 값을 검색하는 함수 Search
•
Search 함수는 임의의 값의 데이터가 스택의 어느 위치에 쌓여 있는지 검사하는 함수이다
•
검색은 꼭대기에서 바닥으로 선형 검색을 수행한다 (하향)
•
검색에 성공하면 찾은 요소의 인덱스를 반환하고 실패하면 -1을 반환한다
꼭대기(top)에서부터 검색하는 이유는 ‘먼저 팝되는 데이터'를 찾기 위해서이다
int Search(const IntStack *s, int x) {
for (int i = s->ptr - 1; i <= 0; i--) // 꼭대기 -> 바닥으로 선형 검색
if (s->stk[i] == x)
return i; // 검색 성공
return -1; // 검색 실패
}
C
복사
모든 데이터를 출력하는 함수 Print
•
Print 함수는 스택의 모든 데이터를 출력하는 함수이다
•
스택에 쌓여있는 ptr개의 모든 데이터를 바닥부터 순서대로 출력한다
void Print(const IntStack *s) {
for (int i = 0; i <= s->ptr - 1; i++) // 바닥 -> 꼭대기로 출력
printf("%d ", s->stk[i]);
printf("\n");
}
C
복사
종료 함수 Terminate
•
Terminate 함수는 뒤처리를 담당하는 함수이다
•
Initialize 함수로 확보한 스택을 해제하고, 용량 max와 스택 포인터 ptr의 값을 0으로 한다
void Terminate(IntStack *s) {
if (s->stk != NULL)
free(s->stk); // 배열 삭제
s->max = s->ptr = 0;
}
C
복사
InStack.c
#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;
}
// 스택에서 검색(Search)
int Search(const IntStack *s, int x) {
for (int i = s->ptr - 1; i >= 0; i--)
if (s->stk[i] == x)
return i;
return -1;
}
// 모든 데이터를 출력 (Print)
void Print(const IntStack *s) {
for (int i = 0; i < s->ptr; i++)
printf("%d ", s->stk[i]);
printf("\n");
}
// 스택 종료
void Terminate(IntStack *s) {
if (s->stk != NULL)
free(s->stk); // 배열을 삭제
s->max = s->ptr = 0;
}
C
복사
간단한 예제
#include <stdio.h>
#include <stdlib.h>
#include "IntStack.h"
int main() {
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)Push (2)Pop (3)Peek (4)Print (0)Terminate : ");
scanf("%d", &menu);
if (menu == 0) break;
switch(menu) {
case 1 :
printf("Data : ");
scanf("%d", &x);
if (Push(&s, x) == -1)
puts("\aError : Fail to Push");
break;
case 2 :
if (Pop(&s, &x) == -1)
puts("\aError : Fail to Pop");
else
printf("Pop data is %d.\n", x);
break;
case 3 :
if (Peek(&s, &x) == -1)
puts("\aError : Fail to Peek");
else
printf("Peek data is %d.\n", x);
case 4 :
Print(&s);
break;
}
}
Terminate(&s);
return 0;
}
C
복사
예제 확장
#include <stdio.h>
#include <stdlib.h>
#include "IntStack.h"
int main() {
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)Push (2)Pop (3)Peek (4)Print (5)Search (6)Clear (7)Capacity (0)Terminate : ");
scanf("%d", &menu);
if (menu == 0) break;
switch(menu) {
case 1 :
printf("Data : ");
scanf("%d", &x);
if (Push(&s, x) == -1)
puts("\aError : Fail to Push");
break;
case 2 :
if (Pop(&s, &x) == -1)
puts("\aError : Fail to Pop");
else
printf("Pop data is %d.\n", x);
break;
case 3 :
if (Peek(&s, &x) == -1)
puts("\aError : Fail to Peek");
else
printf("Peek data is %d.\n", x);
case 4 :
Print(&s);
break;
case 5 :
printf("Data : ");
scanf("%d", &x);
printf("%d번째 위치하고 있습니다.\n", Search(&s, x));
if (Search(&s, x) == -1)
puts("\aError : Fail to Search");
case 6 :
Clear(&s);
printf("Clear Complete!\n");
break;
case 7 :
printf("Current Capacity : %d\n", Capacity(&s));
break;
}
}
Terminate(&s);
return 0;
}
C
복사