[자료구조] 스택 응용

1. 역순 문자열 만들기

• 스택의 후입선출(LIFO) 성질을 이용
• 문자열을 순서대로 스택에 PUSH

1) 순서

(1) 스택 삽입

String

A

B

C

 

3		A 삽입 (push A)		B 삽입 (push B)		C 삽입 (push C)	C
2					B		B
1			A		A		A
	Empty						Full

 

(2) pop 하여 문자열로 저장

String

C

B

A

 

3	C	C 삭제 (pop c)		B 삭제 (pop B)		A 삭제 (pop A)
2	B		B
1	A		A		A
	Full						Empty

 

2) C언어 실습

 

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

// int를 스택 element의 자료형으로 정의

typedef struct STACKNODE {	// 스택의 노드 구조 정의
	char data;	// 문자형 타입 데이터(데이터 필드)
	struct STACKNODE *link;
}SNODE;

// 스택의 top 노드를 지정하기 위한 포인터 top 선언
SNODE *top;

void push(int item) { // 스택 삽입 연산
	
	// 메모리 할당 (할당한 주소 temp에 넣음)
	SNODE *temp = (SNODE *)malloc(sizeof(SNODE));
	
	// 데이터를 temp의 데이터 필드에 넣음
	temp -> data = item;

	// temp의 주소를 top에 넣어줌
	temp -> link = top;
	top = temp;
}

int pop() { // 스택의 삭제 후 반환 연산
	int item;
	SNODE *temp = top;

	if (top == NULL) { // 현재 스택이 공백 리스트인 경우
		printf("\n\n Stack is empty.\n");
		return 0;
	}
	else {	// 현재 스택이 공백 리스트가 아닌 경우
		item = temp -> data;	// item에 temp의 데이터를 줌
		top = temp -> link;	// top에 temp의 링크를 줌(밑의 원소를 가리키게 됨)
		free(temp);	// 메모리에서 삭제
		return item;	// 자룟값 리턴
	}
}

int peek() {	// 스택의 top 원소 검색 연산
	int item;
	if (top == NULL) {	// 현재 스택이 공백 리스트인 경우
		printf("\n\n Stack is empty.\n");
		return 0;
	}
	else {	// 현재 스택이 공백 리스트가 아닌 경우
		item = top -> data;	// top의 값을 item에 넣어줌
		return item;	// top의 값 리턴
	}
}

void del() {
	SNODE *temp;
	if (top == NULL) {	// 현재 스택이 공백 리스트인 경우
		printf("\n\n Stack is empty.\n");
	}
	else {	// 현재 스택이 공백 리스트가 아닌 경우
		temp = top;
		top = top -> link;
		free(temp);	// 메모리 삭제
	}
}

void printStack() {	// 스택의 내용 출력 연산
	SNODE *p = top;	// p는 top이랑 같음
	printf("\n 스택 ");
	while (p) {	// NULL이 아닐 때까지
		printf("%c ", p -> data);
		p = p -> link; // 다음 주소로
	}
	printf(" ");
}

void main(void) {
	int item;	// 초깃값 item 선언, top은 NULL로 초기화
	top = NULL;

	printStack();
	push('A');
	printStack();
	push('B');
	printStack();
	push('C');
	printStack();

	puts("\n");
	item = pop();

	printf(" %c ", item);

	item = pop();
	printf(" %c ", item);

	item = pop();
	printf(" %c", item);
	puts("\n");
}

 

역순 문자열 실행

 

2. 재귀 호출(Recursive Call)

함수는 혼자서는 실행되지 못하고 다른 함수에 의해 호출(call)되어야만 실행된다. 그렇지만 함수는 항상 다른 함수에 의해서만 호출되는 것이 아니다. 자신이 자신을 호출할 수도 있다. 이렇게 자신이 자신을 호출하는 함수를 재귀 함수라고 하며 이러한 호출방식을 재귀 호출이라고 한다.

 

재귀 호출은 자료구조에서 스택의 형태로 메모리에 할당되며 가장 마지막에 입력된 값을 가장 처음 처리하고자 할 때 사용되는 구조다.

재귀 호출의 단계별 복사본 함수들은 가장 나중에 들어온 자료가 가장 먼저 수행되는(LIFO) 스택의 구조와 같이 동작한다.

 

1) C언어 실습

 

#include <stdio.h>

int Recur1(int a) {	// 재귀 함수 Recur1()을 정의
	int gop;
	printf(" a = %d\n", a);
	if (a == 1) return(1);
	else gop = a * Recur1(a - 1);
	
	return (gop);
}

void main() {
	int res, x = 3;
	puts(" 여기는 main() 함수입니다.");
	res = Recur1(x);	// 재귀함수 호출
	printf(" 1 ~ 3 수의 곱 => %d\n", res);
	puts(" main() 함수로 다시 왔습니다.");
}

 

재귀함수 실행

 

2) 구조

A, B, C는 같은 함수다. 

 

A	B	C
int Recur1(int a) {  // a가 3일 때   if (a == 1) return(1);   else gop = a * Recur1(a - 1);    // 3 * Recur1(3 -1) = 3 * Recur1(2)   // 여기서 Recur1(2)가 다시 호출된다   // Recur1(2) = 2   // 즉, 3 * 2   return (gop);  // 6 반환 }	int Recur1(int a) { // Recur1(2) 호출    if (a == 1) return(1);     else gop = a * Recur1(a - 1);     // 2 * Recur1(1)    // Recur1(1) = 1    // 즉, 2 * 1    return (gop); // 2 반환 }	int Recur1(int a) { // Recur1(1) 호출    if (a == 1) return(1); // 1 반환    else gop = a * Recur1(a - 1);     return (gop);  }

 

Recur1(a -1) 이 부분이 자기 자신을 호출하므로 재귀호출이 되는 것이다. 결국, gop는 6이 된다.

재귀 함수의 기본적인 예제로는 팩토리얼 연산을 예제로 한다.