[자료구조] 스택

1. 스택이란?

- 자료의 입출력이 후입선출(LIFO : Last-In First-Out)의 형태로 일어나는 자료 구조

- 가장 먼저 입력된 데이터가 맨 아래에 쌓이고 가장 최근에 입력된 데이터가 가장 위에 쌓이는 구조를 가지고 있음.

- 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터 삽입, 삭제 불가 

 

- 스택 상단(stack top) : 입출력이 이루어지는 부분

- 스택 하단(stack bottom) : 반대쪽인 바닥 부분

- 요소 / 항목 : 스택에 저장되는 것

- 공백 상태 : 스택에 요소가 없는 경우

- 포화 상태 : 꽉 차서 요소 넣을 수 없는 상태

 

스택의 추상 자료형

스택에 기본적으로 필요한 기능

- 새로운 항목을 스택에 삽입

- 스택에서 하나의 항목을 가져옴

- 스택이 비어있는지 확인함

데이터 : 후입선출(LIFO)의 접근 방법을 유지하는 요소들의 모음
연산 :
init() : 스택을 초기화 함
is_empty() : 스택이 비어있으면 TRUE 아니면 FALSE을 반환함
is_full() : 스택이 가득 차 있으면 TRUE 아니면 FALSE을 반환함
size() : 스택 내의 모든 요소들의 개수를 반환함
push(x) : 주어진 요소 x를 스택의 맨 위에 추가함
pop() : 스택 맨 위에 있는 요소를 삭제하고 반환함
peek() : 스택 맨 위에 있는 요소를 삭제하지 않고 반환함

스택의 활용

- 자료의 출력순서가 입력순서의 역순으로 이루어져야 할 경우 매우 긴요하게 사용됨.

 

스택의 주요 활용 분야

- 문서나 그림, 수식 등의 편집기에서 되돌리기(undo) 기능을 구현할 때 스택이 사용됨. 수행된 명령어 중에서 가장 최근에 수행된 것부터 순서대로 취소해야함.

- 함수 호출에서 복귀주소를 기억하는데 스택을 사용함. 

- 문서나 소스 코드에서 괄호 닫기가 정상적으로 되었는지를 검사하는 프로그램

- 계산기 프로그램에서 입력된 수식을 계산하는 과정

- 미로에서 출구를 찾기 위해서도 스택 사용 가능함.

 

스택의 구현 방법

- 스택을 구현하기 위해선 배열을 사용할 수도 있괴, 연결 리스트를 사용할 수도 있음.

- 배열을 이용하면 스택을 가장 간단히 구현할 수 있지만 용량이 고정되는 단점이 있음. (넣을 수 있는 항목의 수가 제한됨)

- 연결리스트를 이용해 스택 구현하면 코드 복잡해지지만 크기가 제한되지 않는 유연한 연결리스트를 구현할 수 있음.

 

2. 배열을 이용한 스택

- 스택을 가장 간단히 구현할 수 있는 방법

- 정수 항목 저장할 배열 선언. Array[MAX_STACK_SIZE]

- MAX_STACK_SIZE만큼 순서대로 하나씩 저장함.

- 입력된 항목의 위치를 가리키기 위해 변수가 필요함. top

 

공백상태와 포화 상태 검사

- 배열이 비어있다면 공백 상태, 배열이 전부 차있으면 포화 상태임.

- 이것은 top 변수를 통해 알수있음. -1이면 공백 상태, top = MAX_STACK_SIZE면 포화상태

공백 상태와 포화상태를 나타낸 그림

 

is_empty()

int is_empty() {
	return (top == -1 );
}

 

is_full()

int is_full() {
    return (top == MAX_STACK_SIZE -1);
}

 

스택의 연산 (Push 연산 = 삽입연산)

1. top <- top +1; // 이거 안하면 B 위치에 덮어쓰게 됨.

- 스택 s에서 top이 마지막 자료를 가리키고 있으므로 그 위에 자료를 삽입하기 위해 top의 위치를 1 증가 시킴.

- 이때 top의 위치가 MAX_STACK_SIZE보다 크다면 삽입 연산 수행하지 못함.

2. s(top) <- x;

- 오버플로우 상태가 아니라면 스택의 top 위치에 삽입함.

 

push(Element e)

void push(Element e)
{
	if (is_full())
		error("스택 포화 상태");
	else
		data[++top] = e;
}

 

스택의 연산 (Pop 연산 = 삭제 연산)

 

1. x <- s(top);

- 이때는 공백상태의 검사가 먼저 필요함. 스택이 공백 상태이면 오류 메시지만 출력함.

- 공백 상태가 아니라면 top이 가리키는 요소를 꺼내서 반환함. 

2. top <-top-1

- top이 가리키는 요소를 꺼내서 반환한 후 top을 하나 감소시킴.

 

pop()

Element pop()
{
	if (is_empty())
		error("스택 공백 상태");
	else
		return data[top--];
}

 

3. 스택의 구현 : 정수형 스택

- 코드 단순화를 위해 data[]와 top은 전역 변수로 선언함.

- 스택의 연산들은 함수로 구현함.

 

스택 항목의 자료형

- 스택 항목의 자료형을 Element라 함.

- Element는 응용에 따라 적절한 자료형으로 지정할 수 있음.

- typedef나 전처리기 지시자인 #define 사용 가능함.

typedef int Element; // Element가 int를 의미함
#define Element double // Element가 double를 의미함
#define Element Student //Element가 구조체 Student를 의미함

 

int 스택을 위한 데이터 선언

typedef int Element;
Element data[MAX_STACK_SIZE];
int top;

 

스택 초기화하는 함수 & 항목 개수 검사 함수

void init_stack() {
	top = - 1;
}

int size() {
	return top + 1;
}

 

배열을 이용한 int 스택의 구현 결과

void main() {
	init_stack();
	for (int i = 1; i < 10; i++)
		push(i);

	print_stack("스택 push 9회");
	printf("\tpop() -> %d\n", pop());
	printf("\tpop() -> %d\n", pop());
	printf("\tpop() -> %d\n", pop());
	print_stack("스택 pop 3회");
}

전체 코드 보기

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100

typedef int Element; // Element가 int를 의미함

Element data[MAX_STACK_SIZE];
int top;

void error(char str[])
{
	printf("%s\n", str);
	exit(1);
}

void init_stack() { top = - 1; }

int is_empty() { return (top == -1); }

int is_full() { return (top == MAX_STACK_SIZE - 1); }

int size() { return top + 1; }

Element peek() {
	if (is_empty())
		error("스택 공백 상태");
	else
		return data[top];
}

void push(Element e)
{
	if (is_full())
		error("스택 포화 상태");
	else
		data[++top] = e;
}

Element pop()
{
	if (is_empty())
		error("스택 공백 상태");
	else
		return data[top--];
}

void print_stack(char msg[])
{
	int i;
	printf("%s[%2d ]= ", msg, size());
	for (i = 0; i < size(); i++)
		printf("%2d ", data[i]);
	printf("\n");
}

void main() {
	init_stack();
	for (int i = 1; i < 10; i++)
		push(i);

	print_stack("스택 push 9회");
	printf("\tpop() -> %d\n", pop());
	printf("\tpop() -> %d\n", pop());
	printf("\tpop() -> %d\n", pop());
	print_stack("스택 pop 3회");
}

 

4. 스택의 구현 : 구조체를 저장하는 스택

- 구조체 스택을 만들기 위해선 구조체가 필요함.

 

ex) 연락처 구조체 스택

1. 연락처 구조체 정의

typedef struct Phone {
	char name[32];
	char number[32];
}Phone;

 

2. 스택에 구조체를 저장함

typedef Phone p;
#define Phone p

3. 변경 및 추가된 함수 ( 연락처 출력함수, 구조체 생성함수)

void print_stack(char msg[])
{
	int i;
	printf("%s[%2d ] \n", msg, size());
	for (i = 0; i < size(); i++)
	{
		printf("이름 : %s \n", stack[i].name);
		printf("번호 : %s\n", stack[i].number);
	}
}

Phone save_number(char name[], char number[])
{
	Phone p;
	strcpy(p.name, name);
	strcpy(p.number, number);
	return p;
}

 

배열을 이용한 연락처 구조체 스택의 구현 결과

전체 코드 보기

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100


typedef struct Phone {
	char name[32];
	char number[32];
}Phone;

typedef Phone phone;
phone stack[MAX_STACK_SIZE];
int top;

void error(char str[])
{
	printf("%s\n", str);
	exit(1);
}

void init_stack() { top = -1; }

int is_empty() { return (top == -1); }

int is_full() { return (top == MAX_STACK_SIZE - 1); }

int size() { return top + 1; }

Phone peek() {
	if (is_empty())
		error("스택 공백 상태");
	else
		return stack[top];
}

void push(Phone e)
{
	if (is_full())
		error("스택 포화 상태");
	else
		stack[++top] = e;
}

Phone pop()
{
	if (is_empty())
		error("스택 공백 상태");
	else
		return stack[top--];
}

void print_stack(char msg[])
{
	int i;
	printf("%s[%2d ] \n", msg, size());
	for (i = 0; i < size(); i++)
	{
		printf("이름 : %s \n", stack[i].name);
		printf("번호 : %s\n", stack[i].number);
	}
}

Phone save_number(char name[], char number[])
{
	Phone p;
	strcpy(p.name, name);
	strcpy(p.number, number);
	return p;
}

void main() {
	init_stack();

	push(save_number("가족", "010-1234-5678"));
	push(save_number("동생", "010-2345-6789"));
	push(save_number("친구", "010-4321-9876"));

	print_stack("스택 push 3회");
	pop();
	print_stack("스택 pop 1회");
}

 

5. 괄호 검사

- 여러 가지 유형의 괄호가 있지만 같은 유형의 괄호가 쌍을 이루어야함.

- 괄호의 조건

조건 1 : 왼쪽 괄호의 개수와 오른쪽 개수의 개수가 같아야함.
조건 2 : 같은 타입의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야함.
조건 3 : 서로 다른 타입의 괄호 쌍이 서로를 교차하면 안 됨.

 

괄호 검사 알고리즘

- 왼쪽 괄호가 나오면 스택에 삽입함.

- 오른쪽 괄호를 만나면 pop()을 통해 최근에 삽입된 괄호를 꺼냄.

- 스택이 비었으면 조건 2에 위배됨.

- 꺼낸 괄호가 짝이 맞지 않으면 조건 3에 위배됨.

- 끝까지 처리했는데 스택에 남아있으면 조건 1에 위배됨.

 

괄호 검사 프로그램 결과 및 코드

전체 코드 보기

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100

typedef int Element; // Element가 int를 의미함

Element data[MAX_STACK_SIZE];
int top;

void error(char str[])
{
	printf("%s\n", str);
	exit(1);
}

void init_stack() { top = -1; }

int is_empty() { return (top == -1); }

int is_full() { return (top == MAX_STACK_SIZE - 1); }

int size() { return top + 1; }

Element peek() {
	if (is_empty())
		error("스택 공백 상태");
	else
		return data[top];
}

void push(Element e)
{
	if (is_full())
		error("스택 포화 상태");
	else
		data[++top] = e;
}

Element pop()
{
	if (is_empty())
		error("스택 공백 상태");
	else
		return data[top--];
}

int check_matching(char expr[])
{
	char p,prep;
	init_stack();
	int i = 0;
	while (expr[i] != '\0')
	{
		p = expr[i++];
		if (p == '(' || p == '[' || p == '{')
			push(p);
		else if (p == ')' || p == ']' || p == '}')
		{
			if (is_empty())
				return 2;
			prep = pop();
			if ((p == ']' && prep != '[') || (p == ')' && prep != '(') || (p == '}' && prep != '{'))
				return 3;
		}
	}
	if (is_empty() == 0)
		return 1;

	return 0;
}

int main()
{
	char s[4][80] = { "{A[(i+1)] = 0;}","if((i==0) && (j==0)",")dde(","B(e+e]" };

	for (int i = 0; i < 4; i++)
	{
		int errCode = check_matching(s[i]);
		if (errCode == 0)
			printf("정상 : %s \n", s[i]);
		else
			printf("오류 (조건식 %d 위반) : %s \n",errCode,s[i]);

	}
	return 0;
}

 

6. 후위 표기 수식의 계산

여러 가지 수식의 표기법

1. 전위 표기법 : 연산자를 피연산자 앞에 표기함.
ex) +AB, +6/AB
2. 중위 표기법 : 연산자를 피연산자 사이에 표기함.(일반적으로 우리가 사용함)
ex) A+B, 6+A/B
3. 후위 표기법 : 연산자를 피연산자 뒤에 표기함. (컴파일러가 사용함)
ex) AB+, 6AB/+

- 후위 표기법의 장점

1. 괄호를 사용하지 않고도 계산해야 할 순서를 알 수 있고 연산자의 우선순위를 생각할 필요가 없음.

2. 수식을 읽으면서 바로 계산할 수 있음. 중위 표기법은 수식을 끝까지 읽어야 계산 가능함.

 

후위 표기 수식의 계산 알고리즘

- 피연산자가 나오면 스택에 저장함.

- 연산자가 나오면 스택에서 피연산자 두 개를 꺼내 연산을 실행한 후 그 결과를 다시 스택에 저장함.

- 수식이 모두 처리될 때 까지 반복되고, 스택에 최종 계산 결과만 하나 남으면 반환함.

 

후위 표기 수식 계산 프로그램 구현 결과

- 수식에 사용되는 사칙연산은 +,-,*,/로 제한함.

- 스택에는 피연산자나 연산의 중간 결과 값이 저장됨.

- 계산 하다보면 실수가 될 수 있으므로 double형을 저장하는 것이 좋음.

전체 코드 보기

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
typedef double element;

element data[MAX_STACK_SIZE];
int top;

void error(char str[])
{
	printf("%s\n", str);
	exit(1);
}

void init_stack() { top = -1; }

int is_empty() { return (top == -1); }

int is_full() { return (top == MAX_STACK_SIZE - 1); }

int size() { return top + 1; }

element peek() {
	if (is_empty())
		error("스택 공백 상태");
	else
		return data[top];
}

void push(element e)
{
	if (is_full())
		error("스택 포화 상태");
	else
		data[++top] = e;
}

element pop()
{
	if (is_empty())
		error("스택 공백 상태");
	else
		return data[top--];
}

double calc(char expr[])
{
	char c;
	double num1, num2, num3;

	int i = 0;
	while (expr[i] != '\0')
	{
		c = expr[i++];
		if (c >= '0' && c <= '9')
		{
			num1 = c - '0';
			push(num1);
		}
		else if (c == '+' || c == '-' || c == '*' || c == '/') {
			num3 = pop();
			num2 = pop();
			switch (c)
			{
			case '+': push(num2 + num3); break;
			case '-': push(num2 - num3); break;
			case '*': push(num2 * num3); break;
			case '/': push(num2 / num3); break;

			}
		}
	}
	return pop();
}

int main()
{
	char expr[2][80] = { "2 4 * 5 -","8 3 / 2 +" };
	printf("수식 %s = %lf\n", expr[0], calc(expr[0]));
	printf("수식 %s = %lf\n", expr[1], calc(expr[1]));
	return 0;
}

 

7. 중위 표기 수식의 후위 표기 변환

- 사칙연산은 가능하지만 인간은 익숙하지 않아 사용하는데 불편함.

- 계산기 프로그램을 구현하려면 중위 표기 수식을 후위 표기식으로 변환하는 과정이 반드시 필요함.

 

중위 표기의 후위 표기 변환 알고리즘

- 피연산자의 순서가 동일함.

-연산자의 출력 순위는 연산자들의 우선순위 관계와 괄호에 의해 결정됨.

- 피연산자를 만나면 바록 출력하고 연산자를 만나면 스택에 저장함.

- 현재 연산자 보다 우선순위가 높거나 같은 연산자는 모두 출력한 후 현재 연산자를 스택에 넣음.

- 입력 수식이 끝나면 스택의 남은 연산자 모두 pop()함.

 

중위 표기의 후위 표기 변환 프로그램 구현

연산자의 우선순위를 비교하는 함수

int precedence(char op)
{
	switch (op)
	{
	case ( '(' ): case( ')' ): return 0;
	case ( '+' ): case( '-' ): return 1;
	case ( '*' ) : case( '/' ): return 2;
	}
	return -1;
}

 

연산자에 따른 변환 처리 함수

double change(char expr[])
{
	char c,op;

	init_stack();

	int i = 0;
	while (expr[i] != '\0')
	{
		c = expr[i++];
		if ((c >= '0' && c <= '9')) {
			printf("%c", c);
		}
		else if (c == '(')
			push(c);
		else if (c == ')')
		{
			while (is_empty() == 0)
			{
				op = pop();
				if (op == '(') break;
				else printf("%c", op);
			}
		}
		else if (c == '+' || c == '-' || c == '*' || c == '/')
		{
			while (is_empty() == 0 )
			{
				op = peek();
				if (precedence(c) <= precedence(op))
				{
					printf("%c", op);
					pop();
				}
				else break;
			}
			push(c);
		}
	}
	while (is_empty() == 0)
	{
		c = pop();
		printf("%c", c);
	}
	printf("\n");
}

 

후위 표기 변환 프로그램 구현 결과

전체 코드 보기

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
typedef double element;

element data[MAX_STACK_SIZE];
int top;

void error(char str[])
{
	printf("%s\n", str);
	exit(1);
}

void init_stack() { top = -1; }

int is_empty() { return (top == -1); }

int is_full() { return (top == MAX_STACK_SIZE - 1); }

int size() { return top + 1; }

element peek() {
	if (is_empty())
		error("스택 공백 상태");
	else
		return data[top];
}

void push(element e)
{
	if (is_full())
		error("스택 포화 상태");
	else
		data[++top] = e;
}

element pop()
{
	if (is_empty())
		error("스택 공백 상태");
	else
		return data[top--];
}

int precedence(char op)
{
	switch (op)
	{
	case ( '(' ): case( ')' ): return 0;
	case ( '+' ): case( '-' ): return 1;
	case ( '*' ) : case( '/' ): return 2;
	}
	return -1;
}

double change(char expr[])
{
	char c,op;

	init_stack();

	int i = 0;
	while (expr[i] != '\0')
	{
		c = expr[i++];
		if ((c >= '0' && c <= '9')) {
			printf("%c", c);
		}
		else if (c == '(')
			push(c);
		else if (c == ')')
		{
			while (is_empty() == 0)
			{
				op = pop();
				if (op == '(') break;
				else printf("%c", op);
			}
		}
		else if (c == '+' || c == '-' || c == '*' || c == '/')
		{
			while (is_empty() == 0 )
			{
				op = peek();
				if (precedence(c) <= precedence(op))
				{
					printf("%c", op);
					pop();
				}
				else break;
			}
			push(c);
		}
	}
	while (is_empty() == 0)
	{
		c = pop();
		printf("%c", c);
	}
	printf("\n");
}

int main()
{
	char expr[2][80] = { "2 * 4 -  5", "1 / 2 * 4 * ( 1 / 4 ) " };

	printf("중위 수식 : %s => 후위 수식 : ", expr[0]);
	change(expr[0]);
	printf("중위 수식 : %s => 후위 수식 : ", expr[1]);
	change(expr[1]);
}