Algorithm/Do it

4장 스택 실습과 연습 문제 풀이

Bonita SY 2020. 12. 21. 22:00
728x90
반응형

C

IntStack.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

 

IntStack.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;
}

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 Termiante(IntStack *s)
{
	if(s->stk != NULL)
		free(s->stk);
	s->max = s->ptr = 0;
}

 

IntStackTest.c

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

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)출력 (5)종료 : ");
		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;
}

 

 

p.142 연습문제 풀이

Q1. 실습 4-3의 프로그램은 IntStack.c에서 제공하는 함수를 모두 사용하지 않습니다. 모든 함수를 사용하는 프로그램을 만드세요.

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

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)출력 (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:
				Print(&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:
				if(Search(&s, &x) == -1)
					puts("\a오류 : 검색에 실패하였습니다.");
				else
					printf("%d의 index는 %d입니다.\n", x, Search(&s, x));
				break;
			
			case 10:
				Print(&s);
				break;
		}
	}
	Terminate(&s);
	return 0;
}

 

Q2. 하나의 배열을 공유하여 2개의 스택을 구현하는 스택 프로그램을 만드세요. 스택에 저장하는 데이터는 int형 값으로 아래 그림처럼 배열의 처음과 끝을 사용하세요.

 

C를 너무 오랜만에 했더니 포인터가 헷갈린다...

IntStack2.h

#ifndef ___IntStack2
#define ___IntStack2

typedef struct {
	int max;
	int left_ptr;
	int right_ptr;
	int *stk;
} IntStack2;

int Initialize(IntStack2 *s, int max);

int LeftPush(IntStack2 *s, int x);

int RightPush(IntStack2 *s, int x);

int LeftPop(IntStack2 *s, int *x);

int RightPop(IntStack2 *s, int *x);

int LeftPeek(const IntStack2 *s, int *x);

int RightPeek(const IntStack2 *s, int *x);

void Clear(IntStack2 *s);

int Capacity(const IntStack2 *s);

int LeftSize(const IntStack2 *s);

int RightSize(const IntStack2 *s);

int ReftIsEmpty(const IntStack2 *s);

int RightIsEmpty(const IntStack2 *s);

int ReftIsFull(const IntStack2 *s);

int RightIsFull(const IntStack2 *s);

int SearchLeft(const IntStack2 *s, int x);

int SearchRight(const IntStack2 *s, int x);

void LeftPrint(const IntStack2 *s);

void RightPrint(const IntStack2 *s);

void Terminate(IntStack2 *s);
#endif

 

IntStack2.c

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

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

int LeftPush(IntStack2 *s, int x)
{
	if(s->left_ptr >= s->right_ptr)
		return -1;
	s->stk[s->left_ptr++] = x;
		return 0;
}

int RightPush(IntStack2 *s, int x)
{
	if(s->right_ptr <= s->left_ptr)
		return -1;
	s->stk[s->right_ptr--] = x;
		return 0;
}

int LeftPop(IntStack2 *s, int *x)
{
	if(s->left_ptr <= 0)
		return -1;
	*x = s->stk[s->left_ptr--];
		return 0;
}

int RightPop(IntStack2 *s, int *x)
{
	if(s->right_ptr >= s->max)
		return -1;
	*x = s->stk[s->right_ptr++];
		return 0;
}

int LeftPeek(const IntStack2 *s, int *x)
{
	if(s->left_ptr <= 0)
		return -1;
	*x = s->stk[s->left_ptr - 1];
		return 0;
}

int RightPeek(const IntStack2 *s, int *x)
{
	if(s->right_ptr >= s->max)
		return -1;
	*x = s->stk[s->right_ptr + 1];
		return 0;
}

void Clear(IntStack2 *s)
{
	s->left_ptr = 0;
	s->right_ptr = 0;
}

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

int LeftSize(const IntStack2 *s)
{
	return s->left_ptr;
}

int RightSize(const IntStack2 *s)
{
	return s->max - s->right_ptr;
}

int ReftIsEmpty(const IntStack2 *s)
{
	return s->left_ptr <= 0;
}

int RightIsEmpty(const IntStack2 *s)
{
	return s->right_ptr >= s->max;
}

int ReftIsFull(const IntStack2 *s)
{
	return s->left_ptr >= s->right_ptr;
}

int RightIsFull(const IntStack2 *s)
{
	return s->right_ptr <= s->left_ptr;
}

int SearchLeft(const IntStack2 *s, int x)
{
	int i;
	for(i=s->left_ptr-1; i>=0; i--)
		if(s->stk[i] == x)
			return i;
	return -1;
}

int SearchRight(const IntStack2 *s, int x)
{
	int i;
	for(i=s->right_ptr; i<s->max; i++)
		if(s->stk[i] == x)
			return i;
	return -1;
}

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

void RightPrint(const IntStack2 *s)
{
	int i;
	for(i=s->max-1; i<=s->right_ptr; i++)
		printf("%d", s->stk[i]);
	putchar('\n');
}

void Termiante(IntStack2 *s)
{
	if(s->stk != NULL)
		free(s->stk);
	s->max = s->left_ptr = s->right_ptr = 0;
}
728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Do it' 카테고리의 다른 글

[자료구조와 함께 배우는 알고리즘 입문 - C언어 편] 3장 검색 연습문제 Q6 답안 p.128  (0) 2019.11.04
[자료구조와 함께 배우는 알고리즘 입문 - C언어 편] 3장 검색 연습문제 Q5 답안 p.115  (0) 2019.10.16
[자료구조와 함께 배우는 알고리즘 입문 - C언어 편] 3장 검색 연습문제 Q3 답안 p.115  (0) 2019.10.16
[자료구조와 함께 배우는 알고리즘 입문 - C언어 편] 3장 검색 연습문제 Q1 답안 p.113  (0) 2019.10.16
[자료구조와 함께 배우는 알고리즘 입문 - C언어 편] 2장 기본 자료구조 연습문제 Q12 답안 p.93  (0) 2019.10.12

'Algorithm/Do it'의 다른글

  • 현재글4장 스택 실습과 연습 문제 풀이

관련글

티스토리툴바