6. 스택(stack)

deepTree·2024년 11월 21일

목록 보기

3/9

이 내용은 윤성우의 열혈 자료구조를 학습한 내용입니다.

1. 스택의 이해와 ADT 정의

1-1. 스택(stack)의 이해

선형 자료구조의 일종
후입선출(LIFO: Last-In, First-Out)의 자료구조

1-2. 스택 ADT의 정의

기본적으로 스택에서는 데이터를 넣고(push), 꺼내고(pop), 들여다 보는(peek) 연산을 진행한다.

void StackInit(Stack * pstack)
- 스택의 초기화 진행
- 스택 생성 후 제일 먼저 호출되어야 하는 함수
int SIsEmpty(Stack * pstack)
- 스택이 빈 경우 TRUE(1), 그렇지 않은 경우 FALSE(0)를 반환한다.
void SPush(Stack * pstack, Data data) : push
- 스택에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.
Data SPop(Stack * pstack) : pop
- 마지막에 저장된 요소를 삭제한다.
- 삭제된 데이터는 반환된다.
- 함수의 호출을 위해 데이터가 하나 이상 존재함이 보장되어야 한다.
Data SPeek(Stack * pstack) : peek
- 마지막에 저장된 요소를 반환하되 삭제하지 않는다.
- 함수의 호출을 위해 데이터가 하나 이상 존재함이 보장되어야 한다.

스택은 배열 혹은 연결리스트 기반으로 구현이 가능하다. 이들 모두 구현할 예정이다.

2. 스택의 배열 기반 구현

2-1. 구현의 논리와 헤더파일의 정리

구현의 논리
- 인덱스 0의 배열 요소가 ‘스택의 바닥’으로 정의한다.
  - 배열의 길이에 상관 없이 언제나 인덱스 0의 요소가 스택의 바닥이 된다.
- 마지막에 저장된 데이터의 위치를 기억해야 한다. → topInex
- push : Top을 위로 한 칸 올리고, Top이 가리키는 위치에 데이터 저장
- pop : Top이 가리키는 데이터를 반환하고, Top을 아래로 한 칸 내림

스택의 헤더파일

#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];
	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-2. 배열 기반 스택의 구현

스택의 구조체

typedef struct _arrayStack
{
	Data stackArr[STACK_LEN]; // typedef int Data;
	int topIndex;
} ArrayStack;

초기화 및 empty 함수

스택의 구조체를 살펴봤을 때, 초기화할 멤버는 topIndex 하나이다.

초기화

void StackInit(Stack * pstack)
{
	pstack->topIndex = -1; // topInex의 -1은 스택이 비었음을 의미한다.
}

IsEmpty

int SIsEmpty(Stack * pstack)
{
	if(pstack->topIndex == -1) // 스택이 비어있다면
		return TRUE;
	else
		return FALSE;
}

핵심 함수: push, pop, peek

push

void SPush(Stack * pstack, Data data)
{
	pstack->topIndex += 1;	// 데이터 추가를 위한 인덱스 값 증가
	pstack->stackArr[pstack->topIndex] = data;	// 데이터 저장
}

pop

Data SPop(Stack * pstack)
{
	int rIdx;

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

	rIdx = pstack->topIndex;	// 삭제할 데이터가 저장된 인덱스 값 저장
	pstack->topIndex -= 1;	// pop 연산의 결과로 topIndex 값 하나 감소

	return pstack->stackArr[rIdx];	// 삭제되는 데이터 반환
}

topInex 값을 근거로 데이터를 저장하기 때문에, 해당 값을 하나 감소시키는 것 만으로도 데이터의 소멸은 완성된다.

peek

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

	return pstack->stackArr[pstack->topIndex];	// 맨 위에 저장된 데이터 반환
}

2-3. Main 함수 활용

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

int main(void)
{
	/*** Stack의 생성 및 초기화 ***/
	Stack stack;
	StackInit(&stack);

	/*** 데이터 넣기 ***/
	SPush(&stack, 1);  SPush(&stack, 2);
	SPush(&stack, 3);  SPush(&stack, 4);
	SPush(&stack, 5);

	/*** 데이터 꺼내기 ***/
	while(!SIsEmpty(&stack))
		printf("%d ", SPop(&stack)); 

	return 0;
}

실행 결과
```
5 4 3 2 1
```
- 입력된 데이터의 역순으로 데이터가 출력된다.

3. 스택의 연결 리스트 기반 구현

3-1. 연결 리스트 기반 스택의 논리와 헤더파일 정의

구현의 논리
- 스택은 저장된 순서의 역순으로 데이터(노드)를 참조(삭제)하는 연결 리스트다.
- 새로운 노드를 꼬리(tail)가 아닌 머리(head)에 추가하는 형태로 구현한 연결리스트

헤더파일 정의

#ifndef __LB_STACK_H__
#define __LB_STACK_H__

#define TRUE	1
#define FALSE	0

typedef int Data;

typedef struct _node	// 연결 리스트의 노드를 표현한 구조체
{
	Data data;
	struct _node * next;
} Node;

typedef struct _listStack	// 연결 리스트 기반 스택을 표현한 구조체
{
	Node * head;
} ListStack;

typedef ListStack Stack;

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

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

선언된 함수의 종류과 기능은 배열 기반 스택의 경우와 다르지 않다.

3-2. 연결 리스트 기반 스택의 구현

초기화 및 empty 함수

초기화

void StackInit(Stack * pstack)
{
	pstack->head = NULL;	// 포인터 변수 head는 NULL로 초기화한다.
}

empty

int SIsEmpty(Stack * pstack)
{
	if(pstack->head == NULL)	// 스택이 비면 head에는 NULL이 저장된다.
		return TRUE;
	else
		return FALSE;
}

핵심 함수: push, pop, peek

push

void SPush(Stack * pstack, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));	// 새 노드 생성

	newNode->data = data;					// 새 노드에 데이터 저장
	newNode->next = pstack->head;	// 새 노드가 최근에 추가된 노드를 가리킴

	pstack->head = newNode;				// 포인터 변수 head가 새 노드를 가리킴
}

head에 새 노드를 추가한다.

pop

Data SPop(Stack * pstack)
{
	Data rdata;
	Node * rnode;

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

	rdata = pstack->head->data;	// 삭제할 노드의 데이터를 임시로 저장
	rnode = pstack->head;				// 삭제할 노드의 주소 값을 임시로 저장

	pstack->head = pstack->head->next;	// 삭제할 노드의 다음 노드를 head가 가리킴
	free(rnode);	// 노드 삭제

	return rdata;	// 삭제된 노드의 데이터 반환
}

포인터 변수 head가 가리키는 노드를 소멸(free)시키고, 소멸된 노드의 데이터(rdata)를 반환

peek

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

	return pstack->head->data;	// head가 가리키는 노드에 저장된 데이터 반환
}

✅ 동적 메모리 할당

malloc: void *malloc(size_t size);
```
int *pi = (int *)malloc(sizeof(int)); //원하는 형식 포인터로 형변환
printf("초기: %d \n",*pi); // 초기: -842150451 (쓰레기 값)
```
- 요청한 크기의 메모리를 동적으로 할당하여 반환
- 동적 메모리의 초기 값: 쓰레기 값(Garbage Value)

free: void free(void *memblock);

free(pi); //더 이상 필요없을 때 해제

3-3. Main 함수 활용

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

int main(void)
{
	/*** Stack의 생성 및 초기화 ***/
	Stack stack;
	StackInit(&stack);

	/*** 데이터 넣기 ***/
	SPush(&stack, 1);  SPush(&stack, 2);
	SPush(&stack, 3);  SPush(&stack, 4);
	SPush(&stack, 5);

	/*** 데이터 꺼내기 ***/
	while(!SIsEmpty(&stack))
		printf("%d ", SPop(&stack)); 

	return 0;
}

실행 결과
```
5 4 3 2 1
```

4. 계산기 프로그램 구현

4-1. 수식의 표기법

수식을 이루는 피연산자는 한자리 숫자로만 이뤄진다고 가정한다.

중위 표기법(infix noation): 5 + 2 / 7
- 연산순서에 대한 정보가 담겨있지 않다. → 연산자의 우선순위와 소괄호가 필요하다.
전위 표기법(prefix notation): + 5 / 2 7
- 연산자의 배치순서에 따라서 연산순서가 결정된다.
후위 표기법(postfix notation): 5 2 7 / +
- 연산자의 배치순서에 따라서 연산순서가 결정된다.
- Ex. 5 2 4 op1 op2 : op1 연산을 하고 나서 op2 연산을 진행

🔻 연산

중위 표기법의 수식을 후위 표기법의 수식으로 바꾼다.
후위 표기법으로 바뀐 수식을 계산하여 그 결과를 얻는다.

위 두 과정을 기준으로 각각의 알고리즘을 작성해 보도록 하자.

4-2. 중위 표기법을 후위 표기법으로 바꾸는 방법(1): 소괄호 고려 X

후위 표기법에서 우선순위가 높은 연산자가 변환된 수식의 앞부분에 위치해야 한다.

🔻 과정

피연산자는 그냥 옮긴다.
연산자는 스택으로 옮긴다.
- 스택의 마지막 연산자의 우선순위가 높다면
  - 스택의 마지막 연산자의 우선순위가 높을 때까지 마지막 연산자를 꺼내서 수식으로 옮기고, 새 연산자를 스택에 쌓는다.
- 스택의 마지막 연산자의 우선순위가 낮다면
  - 스택에 새 연산자를 쌓는다.
- 스택의 마지막 연산자의 우선순위가 같다면
  - 스택에 있는 마지막 연산자가 우선순위가 더 높다.(먼저 등장한 연산자를 먼저 진행한다.)
마지막까지 스택에 남아있는 연산자들은 하나씩 꺼내서 옮긴다.

transform

4-3. 중위 표기법을 후위 표기법으로 바꾸는 방법(2): 소괄호 고려

🔻 과정

피연산자는 그냥 옮긴다.
연산자는 스택으로 옮긴다.
마지막까지 스택에 남아있는 연산자들은 하나씩 꺼내서 옮긴다.

기본 과정은 소괄호가 없을 경우와 같다. 다만, ( 와 ) 연산자의 수행은 다르게 진행된다.

( 연산자
- 사칙 연산자들보다 연산의 우선순위가 낮다고 간주한다.
) 연산자
- ( 이후에 스택에 쌓인 연산자들을 변환된 수식의 자리로 옮긴다.
- ) 연산자는 메시지만 취하고 버린다.

trans2

4-4. 중위 표기법을 후위 표기법으로 바꾸는 프로그램의 구현

연산자의 연산 우선순위 정보를 반환

int GetOpPrec(char op) // 연산자의 연산 우선순위 정보를 반환
{
	switch(op)
	{
	case '*':
	case '/':
		return 5;	// 가장 높은 연산 우선순위
	case '+':
	case '-':
		return 3;	// 중간 순위
	case '(':
		return 1;	// 가장 낮은 연산의 우선순위
	}

	return -1;   // ')': 등록되지 않은 연산자임을 알림
}

연산자의 우선순위를 비교하여, 그 결과를 반환

int WhoPrecOp(char op1, char op2)
{
	int op1Prec = GetOpPrec(op1);
	int op2Prec = GetOpPrec(op2);

	if(op1Prec > op2Prec)	// op1의 우선순위가 더 높다면
		return 1;
	else if(op1Prec < op2Prec)	// op2의 우선순위가 더 높다면
		return -1;
	else
		return 0;	// op1, op2의 우선순위가 같다면
}

후위 표기법으로의 변환을 처리하는 함수

void ConvToRPNExp(char exp[]) // 후위 표기법의 수식으로 변환
{
	Stack stack;
	int expLen = strlen(exp);
	char * convExp = (char*)malloc(expLen+1);	// 변환된 수식을 담을 공간 마련

	int i, idx=0;
	char tok, popOp;
	
	memset(convExp, 0, sizeof(char)*expLen+1);	// 할당된 배열을 0으로 초기화
	StackInit(&stack);

	for(i=0; i<expLen; i++)
	{
		tok = exp[i];	// exp로 전달된 수식을 한 문자씩 tok에 저장
		if(isdigit(tok))	// tok에 저장된 문자가 숫자인지 확인
		{
			convExp[idx++] = tok;
		}
		else	// 연산자라면
		{
			switch(tok)
			{
			case '(':
				SPush(&stack, tok);	// 스택에 쌓는다.
				break;

			case ')':
				while(1)
				{
					popOp = SPop(&stack);
					if(popOp == '(')	// 스택에서 연산자를 꺼내어 '('를 만날 때까지
						break;
					convExp[idx++] = popOp;	// 변환 배열에 저장
				}
				break;

			case '+': case '-': 
			case '*': case '/':
				while(!SIsEmpty(&stack) && 
						WhoPrecOp(SPeek(&stack), tok) >= 0) // 스택의 마지막 원소와 우선순위 비교
					convExp[idx++] = SPop(&stack);

				SPush(&stack, tok);
				break;
			}
		}
	}
	/*** 스택에 남아 있는 모든 연산자를 변환 배열로 이동시킨다. ***/
	while(!SIsEmpty(&stack))
		convExp[idx++] = SPop(&stack);

	strcpy(exp, convExp);	// 변환된 수식을 exp에 복사
	free(convExp);	// convExp 소멸
}

✅ memset, isdigit 표준함수

void * memset(void *ptr, int val, size_t len);
- ptr 로 전달된 주소의 메모리서부터 len 바이트를 val 의 값으로 채운다.
int isdigit(int ch);
- ch로 전달된 문자의 내용이 10진수라면 1을 반환한다.

4-5. 후위 표기법으로 표현된 수식의 계산방법과 프로그램의 구현

🔻 계산방법

먼저 연산되어야 하는 연산자가 수식의 앞쪽에 배치된다.
후위 표기법의 수식에서는 연산자의 앞에 등장하는 두 개의 숫자가 피연산자다.

✔️ 구현

피연산자는 무조건 스택으로 옮긴다.
연산자를 만나면 스택에서 두 개의 피연산자를 꺼내서 계산한다.
계산결과는 다시 스택에 넣는다.

int EvalRPNExp(char exp[])
{
	Stack stack;
	int expLen = strlen(exp);
	int i;
	char tok, op1, op2;

	StackInit(&stack);

	for(i=0; i<expLen; i++)	// 수식을 구성하는 문자 각각을 대상으로 반복
	{
		tok = exp[i];

		if(isdigit(tok))
		{
			SPush(&stack, tok - '0');     // 정수면 숫자로 변환 후 스택에 push
		}
		else
		{
			op2 = SPop(&stack);     // 두 번째 피연산자
			op1 = SPop(&stack);			// 첫 번째 피연산자

			switch(tok)	// 연산결과를 다시 스택에 push
			{
			case '+':
				SPush(&stack, op1+op2);
				break;
			case '-':
				SPush(&stack, op1-op2);
				break;
			case '*':
				SPush(&stack, op1*op2);
				break;
			case '/':
				SPush(&stack, op1/op2);
				break;
			}
		}
	}
	return SPop(&stack);	// 마지막 연산결과를 스택에서 꺼내어 반환
}

✅ char → int

문자는 ASCII 코드 규칙에 의해 정수로 저장되므로 정수처럼 연산할 수 있다.
숫자의 아스키 값은 48번부터 0 ~ 9를 할당한다.
tok - '0' 으로 정수 값을 알 수 있다.

참고: 윤성우의 열혈 자료구조

deepTree

매일 노력하는 초보 개발자입니다.

이전 포스트

2. 재귀(Recursion)

다음 포스트

6. 스택(stack)

자료구조

1. 스택의 이해와 ADT 정의

1-1. 스택(stack)의 이해

1-2. 스택 ADT의 정의

2. 스택의 배열 기반 구현

2-1. 구현의 논리와 헤더파일의 정리

2-2. 배열 기반 스택의 구현

2-3. Main 함수 활용

3. 스택의 연결 리스트 기반 구현

3-1. 연결 리스트 기반 스택의 논리와 헤더파일 정의

3-2. 연결 리스트 기반 스택의 구현

✅ 동적 메모리 할당

3-3. Main 함수 활용

4. 계산기 프로그램 구현

4-1. 수식의 표기법

🔻 연산

4-2. 중위 표기법을 후위 표기법으로 바꾸는 방법(1): 소괄호 고려 X

🔻 과정

4-3. 중위 표기법을 후위 표기법으로 바꾸는 방법(2): 소괄호 고려

🔻 과정

4-4. 중위 표기법을 후위 표기법으로 바꾸는 프로그램의 구현

✅ memset, isdigit 표준함수

4-5. 후위 표기법으로 표현된 수식의 계산방법과 프로그램의 구현

🔻 계산방법

✔️ 구현

2. 재귀(Recursion)

7. 큐(Queue)

0개의 댓글