3. 스택

스택은 데이터를 일시적으로 저장하기 위한 자료구조이다.

 

LIFO(Last In, Fisrt Out) , 후입선출의 구조를 가지는데, 이는 가장 나중에 넣은 데이터를 가장 먼저 끝낸다는 의미이다.

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

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

 

참조 : https://github.com/fairesy/plenty-study/wiki/%EC%8A%A4%ED%83%9D-Stack

 

스택을 구현해보자. 먼저 헤더 선언을 해서 스택의 기능에 대해 간략하게 알아보자.

#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

1. 스택 구조체

- 스택으로 사용할 배열을 가리키는 포인터 stk

: 스택으로 푸시된 데이터를 저장할 용도의 배열을 가리킴

- 스택의 최대용량 max

: 스택의 최대 용량을 나타낸다. 배열 stk의 요소 개수와 동일

- 스택의 포인터 ptr

: 스택에 쌓여있는 데이터의 개수를 나타낸다. 가득 차있으면 max 값과 동일

 

2. 초기화 함수 Initialize

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

int Initialize(intStack* s, int max)
{
	s->ptr = 0;
	if ((s->stk = (int*)calloc(max, sizeof(int))) == NULL)
	{
		s->max = 0;
		return -1;
	}
	s->max = max;
	return 0;

}

스택의 메모리공간을 확보하는 함수로써, 배열을 위한 메모리 공간 만들 때 empty 상태여야한다.

즉, 스택 포인터 ptr은 0, 스택의 최대용량 max는 요소의 개수가 max인 만큼의 배열을 생성해야한다.

그래서 s.ptr = 0, s.max = max로 선언하였다.

 

3. push 함수

int Push(intStack* s, int x)
{	
	// 스택이 가득 찬 경우 푸쉬 불가
	if (s->ptr >= s->max)
	{
		return -1;
	}
	// 새로 추가할 데이터 요소 x를 배열의 요소 stk[ptr]에 저장, ptr 증가
	s->stk[s->ptr++] = x;
	return 0;

}

스택에 요소를 넣는 기능을 하는 함수로써, 스택이 가득 찬 경우에는 -1을 반환,

스택으로 사용할 배열 stk에서 스택 포인터가 가리키는 곳에 x를 넣고 그 다음으로 가기 위해 포인트 증가를 해준다.

 

 

4. pop 함수

int Pop(intStack* s, int* x)
{
	if (s->ptr = 0)
	{
		return -1;
	}
	*x = s->stk[--s->ptr];
	return 0;

}

스택의 꼭대기에서 데이터를 제거하는 함수로서, 포인터 값을 감소시키고, stk[ptr]에 저장된 값을 포인터 x가 가리키는 변수에 저장한다.

 

5. peek 함수

int Peek(const intStack* s, int* x)
{
	if (s->ptr <= 0)
	{
		return -1;
	}
	*x = s->stk[s->ptr - 1];
	return 0;
}

꼭대기 요소의 값을 포인터 x에 반환한다.

 

6. clear 함수

void Clear(intStack* s)
{
	s->ptr = 0;
}

모든 데이터를 삭제한다.

 

7. 나머지 함수들

int Capacity(const intStack* s)
{
	return s->max;
}

int isEmpty(const intStack* s)
{
	return s->ptr <= 0;
}
int Size(const intStack* s)
{
	return s->ptr;
}

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--)
	{
		if (s->stk[i] == x)
			return i;
		return -1;
	}
}

void Print(const intStack* s)
{
	int i;
	for (i = 0; i < s->ptr; i++)
	{
		printf("%d", s->stk[i]);
	}
	putchar("\n");
}

void Terminate(intStack* s)
{
	if (s->stk != NULL)
		free(s->stk);
	s->max = s->ptr = 0; //배열 삭제
}

 

스택 구현

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include "intStack.h"

int Initialize(intStack* s, int max)
{
	s->ptr = 0;
	if ((s->stk = (int*)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;
	}
	// 새로 추가할 데이터 요소 x를 배열의 요소 stk[ptr]에 저장, ptr 증가
	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 isEmpty(const intStack* s)
{
	return s->ptr <= 0;
}
int Size(const intStack* s)
{
	return s->ptr;
}

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--)
	{
		if (s->stk[i] == x)
			return i;
		return -1;
	}
}

void Print(const intStack* s)
{
	int i;
	for (i = 0; i < s->ptr; i++)
	{
		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(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);

		case 3:
			if (Peek(&s, &x) == -1)
			{
				puts("\a오류 : 피크에 실패하였습니다.");
			}
			else {
				printf("피크 데이터는 %d입니다.\n", x);
			}
			break;

		case 4:
			Print(&s);
			break;
		}
		
	}
	Terminate(&s);
	return 0;
}