반응형
배열로 구현 예시 (요소는 int형)
[ IntStack.h ]
//
// Intstack.h
// helloC
//
// Created by Hevton on 2020/10/14.
//
/* int형 스택 IntStack 헤더 */
#ifndef Intstack_h
#define Intstack_h
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);
// 스택에서 데이터를 피크(top에 위치하는 요소 확인)
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_h */
[ IntStack.c ]
//
// IntStack.c
// helloC
//
// Created by Hevton on 2020/10/14.
//
#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;
}
// 스택에 데이터를 푸시
// 스택이 가득 차서 푸시할 수 없는 경우 -1 반환, 스택에 푸시 성공하면 0을 반환
int Push(IntStack *s, int x)
{
// == 연산자를 사용해도 되나, 프로그램의 오류나 사용자의 의도적인 잘못된 값 입력 등의 이유로 ptr 값이 잘못 입력되어 max값을 초과하는 경우가 생길 우려를 으레 막아놓음으로써, 프로그램의 안정성을 높일 수 있다.
if(s->ptr >= s->max) // 스택이 가득 참
return -1;
s->stk[s->ptr++] = x;
return 0;
}
// 스택에서 데이터를 팝
// 스택이 비어 있어 팝 할수 없는 경우 -1 반환, 팝에 성공할 경우 0을 반환
int Pop(IntStack *s, int *x)
{
if(s->ptr <=0) // 스택이 비어 있음
return -1;
*x = s->stk[--s->ptr];
return 0;
}
// 스택에서 데이터를 피크(top에 위치하고 있는 데이터를 열람)
// 스택이 비어 있으면 -1 반환, 피크에 성공하면 0을 반환
int Peek(const IntStack *s, int *x)
{
if(s->ptr<=0) // 스택이 비어있음
return -1;
*x = s->stk[s->ptr-1];
return 0;
}
// 스택 비우기
// 배열 요소들을 변경할 필요 없음. ptr을 0으로.
void Clear(IntStack *s)
{
s->ptr = 0;
}
// 스택 용량
// max의 값 반환
int Capacity(const IntStack *s)
{
return s->max;
}
// 스택에 쌓여 있는 데이터의 수
// ptr의 값 반환
int Size(const IntStack *s)
{
return s->ptr;
}
// 스택이 비어 있는가?
// 스택이 비어 있으면 1, 그렇지 않으면 0 반환
int IsEmpty(const IntStack *s)
{
return s->ptr <= 0;
}
// 스택이 가득 찼는가?
// 스택이 가득 찼으면 1, 그렇지 않으면 0 반환
int IsFull(const IntStack *s)
{
return s->ptr >= s->max;
}
// 스택에서 검색
// 검색에 성공하면 찾은 요소의 인덱스를 반환, 실패하면 -1을 반환
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;
}
[ main.c ]
#include <stdio.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)푸시 (2)팝 (3)피크 (4)클리어 (5)최대 용량 (6)데이터 개수 (7)스택이 비어있는지 (8)스택이 가득 찼는지 (9)검색 (10)출력 (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: // 클리어
Clear(&s);
break;
case 5: // 최대 용량
printf("스택의 최대 용량은 %d입니다.\n", Capacity(&s));
break;
case 6: // 데이터 개수
printf("현재 스택의 데이터 개수는 %d개 입니다.\n", Size(&s));
break;
case 7: // 스택이 비어있는지
if(IsEmpty(&s))
puts("스택이 비어있습니다.");
else
puts("스택이 비어있지 않습니다.");
break;
case 8: // 스택이 가득 찼는지
if(IsFull(&s))
puts("스택이 가득 차 있습니다.");
else
puts("스택이 가득 차 있지 않습니다.");
break;
case 9: // 검색
printf("검색할 데이터 : ");
scanf("%d", &x);
int data = Search(&s, x);
if(data!= -1)
printf("검색한 데이터는 s[%d]에 있습니다.\n", data);
else
puts("데이터가 존재하지 않습니다.");
break;
case 10: // 출력
Print(&s);
break;
}
}
Terminate(&s);
return 0;
}
반응형
'[알고리즘 + 자료구조]' 카테고리의 다른 글
[자료구조] Queue (0) | 2020.10.15 |
---|---|
[자료구조] 다중 STACK (0) | 2020.10.14 |
[알고리즘] 이진 검색 (0) | 2020.10.11 |
[알고리즘] 선형 검색 (0) | 2020.10.11 |
[알고리즘] Insert sort (0) | 2020.10.05 |