Ch 6 - 1 스택의 개념과 배열 기반 스택 구현

1. 스택의 개념

먼저 들어간 것이 나중에 나오는 구조가 스택

스택의 기본 연산

1.push - 넣고
2.pop - 꺼내기 -> 데이터 꺼내기 + 삭제
3.peek - 데이터 추출 가능, 삭제X

2. 내가 구현한 배열기반 스택의 헤더 파일과 소스 파일

1.헤더

#ifndef __STACK_H__
#define __STACK_H__

#define TRUE 1
#define FALSE 0

typedef int Data;

typedef struct
{
	Data list[10];
	int numOfData;
}Stack;

void StackInit(Stack* pstack);
int SIsEmpty(Stack* pstack);
void SPush(Stack* pstack, Data data);
Data SPop(Stack* pstack);
Data SPeek(Stack* pstack);

#endif

2.소스파일

#include <stdio.h>
#include "ArrayBaseStack.h"

void StackInit(Stack* pstack)
{
	pstack->numOfData = 0;
}

int SIsEmpty(Stack* pstack)
{
	if (pstack->numOfData == 0) return TRUE;
	else return FALSE;
}

void SPush(Stack* pstack, Data data)
{
	pstack->list[pstack->numOfData] = data;
	pstack->numOfData++;
}

Data SPop(Stack* pstack)
{
	if (pstack->numOfData == 0) return FALSE;
	else
	{
		pstack->numOfData--;
		return pstack->list[pstack->numOfData];
	}
}

Data SPeek(Stack* pstack)
{
	if (pstack->numOfData == 0) return FALSE;
	else return pstack->list[(pstack->numOfData) - 1];
}

3.강의에서 구현한 헤더파일 및 소스 파일

1.헤더 파일

#ifndef __AB_STACK_H__
#define __AB_STACK_H__

#define TRUE	1
#define FALSE	0
#define STACK_LEN	100

typedef int Data;

typedef struct _arrayStack
{
	Data stackArr[STACK_LEN];//범용성 있게 짜려면 STACK_LEN이라는 상수를 define하는게 좋겠구나.
	int topIndex;
} ArrayStack;

typedef ArrayStack Stack;

void StackInit(Stack * pstack);
int SIsEmpty(Stack * pstack);

void SPush(Stack * pstack, Data data);
Data SPop(Stack * pstack);
Data SPeek(Stack * pstack);

#endif

2. 소스 파일

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

void StackInit(Stack * pstack)
{
	pstack->topIndex = -1;
}

int SIsEmpty(Stack * pstack)
{
	if(pstack->topIndex == -1)
		return TRUE;
	else
		return FALSE;
}

void SPush(Stack * pstack, Data data)
{
	pstack->topIndex += 1;
	pstack->stackArr[pstack->topIndex] = data;
}

Data SPop(Stack * pstack)
{
	int rIdx;

	if(SIsEmpty(pstack))
	{
		printf("Stack Memory Error!");
		exit(-1);
	}

	rIdx = pstack->topIndex;
	pstack->topIndex -= 1;

	return pstack->stackArr[rIdx];
}

Data SPeek(Stack * pstack)
{
	if(SIsEmpty(pstack))
	{
		printf("Stack Memory Error!");
		exit(-1);
	}

	return pstack->stackArr[pstack->topIndex];
}

//차이점은 top index를 numOfData대신 사용하는 것

백준 10828번 스택

https://www.acmicpc.net/problem/10828

스택을 구현하는 문제

empty와 size는 함수 구현으로 당연히 풀 수 있지만 그냥 numOfData를 이용하는게 편할 것 같아서 함수를 구현하지 않았다.

내 코드

#include <stdio.h>
#include <string.h>

typedef struct
{
	int list[10000];
	int numOfData;
}Stack;

void Init(Stack* pstack)
{
	pstack->numOfData = 0;
}

void Insert(Stack* pstack, int data)
{
	pstack->list[pstack->numOfData++] = data;
}

int pop(Stack* pstack)
{
	if (pstack->numOfData == 0) return -1;
	pstack->numOfData--;
	return pstack->list[pstack->numOfData];
}

int peek(Stack* pstack)
{
	if (pstack->numOfData == 0) return -1;
	else return pstack->list[(pstack->numOfData) - 1];
}



int main()
{
	Stack stack;
	int i, T, x;
	char array[10];
	Init(&stack);
	scanf("%d", &T);
	for (i = 0; i < T; i++)
	{
		scanf("%s", array);
		if (strcmp(array, "push") == 0)
		{
			scanf("%d", &x);
			Insert(&stack, x);
		}
		else if (strcmp(array, "pop") == 0)
		{
			printf("%d\n", pop(&stack));
		}
		else if (strcmp(array, "size") == 0)
		{
			printf("%d\n", stack.numOfData);
		}
		else if (strcmp(array, "empty") == 0)
		{
			if (stack.numOfData) printf("0\n");
			else printf("1\n");
		}
		else
		{
			printf("%d\n", peek(&stack));
		}
	}
	return 0;
}