4-1 스택이란?

1. 스택 알아보기 

 

스택(stack)

- 데이터를 일시적으로 저장하기 위해 사용하는 자료구조

 

- LIFO(Last In First Out) 

 : 가장 나중에 넣은 데이터를 가장 먼저 꺼냄 

 

- 푸시(Push)

 : 스택에 데이터를 넣는 작업

 

- 팝(Pop)

 : 스택에서 데이터를 꺼내는 작업

 

- 꼭대기(Top)

 : 푸시, 팝을 하는 위치 

 

- 바닥(bottom)

 : 스택에 가장 밑바닥 부분 

 

 

2. 스택 만들기 

 

2-1 스택 구조체 IntStack 

 - 스택을 관리하는 구조체 

//스택을 구현하는 구조체 
typedef struct {
	int max; //스택 용량
	int ptr; //스택 포인터 
	int *stk; //스택 첫 요소에 대한 포인터  
}IntStack;

 1) 스택으로 사용할 배열을 가리키는 stk

 

  - 스택으로 푸시된 데이터를 저장할 용도의 배열을 가리키는 포인터 

  - 배열의 메모리 공간 할당은 Initialize 함수로 생성

 

 2) 스택의 최대 용량 max

 

  - 스택의 최대용량을 나타내는 int형 멤버 

  - 배열 stk의 요소 개수와 같음 

 

 3) 스택 포인터 ptr

 

 - 스택에 쌓여 있는 데이터의 개수를 나타내는 멤버 

 - 스택이 비어 있으면 ptr 은 0

 - 스택이 가득 차 있으면 max

 

2-2 초기화 함수 Initialize

 

 - 스택의 메모리 공간(배열)을 확보하는 등의 준비 작업 

//스택 초기화 
int Initialize(IntStack *s, int max) 
{
	s->ptr=0;
	if((s->stk=(int*)calloc(max,sizeof(int)))== NULL) {
		s->stk =0; //배열 생성에 실패 
		return -1; 
	}
	s->max = max;
	return 0;
}

 

- 배열을 위한 메모리 공간을 만들 때 스택은 비어있어야 함 

 -> 스택 포인터 ptr값을 0으로 함

s->ptr=0;

 

- 요소의 개수가 max인 배열 stk 생성

 -> 스택의 개별 요소에 접근하는 인덱스 식은 바닥(bottom)부터 stk[0], stk[1],...stk[max-1]

if((s->stk=calloc(max,sizeof(int)))==NULL) {
	s->max =0; //배열의 생성에 실패 
    return -1;
}

 

- 매개 변수 max로 받은 값을 스택 최대 용량을 나타내는 구조체의 멤버 max에 저장

s->max =max;

 

2-3 푸시 함수 Push

 

- 스택에 데이터를 추가하는 함수 

- 새로 추가할 데이터 (x)를 배열의 요소 stk[ptr]에 저장 

- 스택 포인터 ptr 증가 

//스택에 데이터 Push
int Push(IntStack *s, int x) 
{
	if(s->ptr >= s->max) //스택이 가득참
		return -1;
	s->stk[s->ptr++] = x; 
	return 0;
}

 

2-4 팝 함수 Pop

 

- 스택의 꼭대기에서 데이터를 제거하는 함수 

- 스택 포인터 ptr의 값을 감소

- stk[ptr]에 저장된 값을 포인터 x가 가리키는 변수에 저장 

//스택에서 데이터를 제거 
int Pop(IntStack *s, int *x) 
{
	if(s->ptr <=0) //스택이 비어있음
	   return -1;
	*x = s->stk[--s->ptr];
	return 0;
}

 

2-5 피크 함수 Peek

 

- 스택 꼭대기의 데이터를 '몰래 엿보는' 함수 

- 스택이 비어 있지 않으면 꼭대기 요소 stk[ptr-1]의 값을 포인터 x가 가리키는 변수에 저장

//스택에서 데이터 엿보기 
int Peek(const IntStack *s, int *x) 
{
	if(s->ptr<=0) //스택이 비어있음 
		return -1; 
	*x = s->stk[s->ptr-1];
		return 0;
}

 

2-6 스택의 모든 요소를 삭제하는 함수 Clear

 

- 스택에 쌓여 있는 모든 데이터를 삭제 

- 스택 포인터 ptr값을 0으로 함

//스택의 모든 요소 삭제 
void Clear(IntStack *s) 
{
	s->ptr=0;
}

 

2-7 용량을 확인하는 함수 Capacity

 

- 스택의 용량 (멤버 max의 값)을 반환

//스택 용량
int Capacity(const IntStack *s) 
{
	return s->max;
}

 

2-8 데이터 개수를 확인하는 함수 Size

 

- 현재 스택에 쌓여 있는 데이터의 개수 (멤버 ptr의 값)을 반환

//스택에 쌓여 있는 데이터 수 
int Size(const IntStack *s) 
{
	return s->ptr;
}

 

2-9 스택에 비어 있는지 검사하는 함수 IsEmpty

 

- 스택이 비어 있는지 검사 

- 비어 있으면 1, 그렇지 않으면 0 반환

//스택이 비어 있는가?
int IsEmpty(const IntStack *s) 
{
	return s->ptr<=0;
}

 

2-10 스택이 가득 찼는지 검사하는 함수 IsFull

 

- 스택이 가득 찼는지 검사하는 함수 

- 가득 찼으면 1, 그렇지 않으면 0 반환

//스택이 가득 찼는가?
int IsFull(const IntStack *s) 
{
	return s->ptr >= s->max;
}

 

2-11 임의의 값을 검사하는 함수 Search

 

- 임의의 값 x의 데이터가 스택의 어느 위치에 쌓여 있는지 검사 

- 꼭대기에서 바닥으로 선형 검색

- 배열 인덱스가 큰쪽에서 작은쪽으로 선형 검색

- 검색 성공시 찾은 요소의 인덱스 반환, 실패시 -1 반환

//스택에서 검색
int Search(const IntStack *s, int x) 
{
	for(int i=s->ptr-1; i>=0; i--) //꼭대기(top)->바닥(bottom)으로 선형 검색
		if(s->stk[i]==x) 
			return i; //검색 성공
	return -1; //검색 실패  
}

 

2-12 모든 데이터를 출력하는 함수 Print

 

- 스택의 모든 데이터 출력

- 스택에 쌓여 있는 ptr개의 모든 데이터를 바닥부터 순서대로 출력 (인덱스 0부터)

//모든 데이터 출력
void Print(const IntStack *s) 
{
	int i;
	for(int i=0; i<s->ptr; i++) //바닥(bottom)-> 꼭대기(top)으로 스캔
		printf("%d",s->stk[i]);
	putchar('\n');
}

 

2-13 종료 함수 Terminate

 

- Initialize 함수로 확보한 스택을 해제 

- 용량 max, 스택 포인터 ptr의 값을 0으로

//스택 종료 
void Terminate(IntStack *s) 
{
	if(s->stk != NULL)
		free(s->stk); //배열을 삭제 
	s->max = s->ptr =0; 
}

 

3. 스택을 사용하는 프로그램

 

- 스택의 용량이 64이며 푸시, 팝, 스택 데이터 출력은 대화식으로 실행

#include <stdio.h>
#include <stdlib.h>


//스택을 구현하는 구조체 
typedef struct {
	int max; //스택 용량
	int ptr; //스택 포인터 
	int *stk; //스택 첫 요소에 대한 포인터  
}IntStack;

//스택 초기화 
int Initialize(IntStack *s, int max);

//스택에 데이터를 푸시 
int Push(IntStack *s, int x);

//스택에 데이터를 팝
int Poo(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 IsEmtpy(const IntStack *s);

//스택이 가득 찼나요?
int IsFull(const IntStack *s);

//스택에서 검색
int Search(const IntStack *s, int x);

//모든 데이터 출력
void Print(const IntStack *s);

//스택 종료 
void Terminate(IntStack *s);



//스택 초기화 
int Initialize(IntStack *s, int max) 
{
	s->ptr=0;
	if((s->stk=(int*)calloc(max,sizeof(int)))== NULL) {
		s->stk =0; //배열 생성에 실패 
		return -1; 
	}
	s->max = max;
	return 0;
}

//스택에 데이터 Push
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) 
{
	for(int 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(int 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; 
}

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)출력 (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;
}