[C][강의요약] 스택의 개념과 구현 (1)

https://youtu.be/MaLRjxoaowA

 

스택은 일종의 리스트

리스트는 일렬로 데이터가 있을 때, 데이터 리스트

검색, 삽입, 삭제 연산 가능

데이터가 맨 앞, 중간, 마지막 어디든 삽입 가능

 

스택, 일종의 리스트, 데이터의 삽입과 삭제가 한쪽에서만 이루어지는 것을 말함

물건을 쌓아 놓을 때 맨 위에 올려 놓고, 맨 위의 자료를 빼내는 것 떠올리면 됨.

Last-In, First-Out

삽입과 삭제가 일어나는 쪽을 top이라고 부름.

 

어떤 데이터들을 저장해둘 수 있는 리스트인데, 그 맨 위에서 데이터를 추가하고 삭제하는 방식이다.

 

 

스택이 지원하는 연산

필수 연산

push: 스택에 새로운 원소를 삽입하는 연산

pop: 스택의 top에 있는 원소를 스택에서 제거하고 반환

보조 연산

peek: 스택 top의 원소를 제거하지 않고 반환

empty: 스택이 비었는지 검사

 

 

 

스택의 연산의 예

 

push("Rich");
push("Debbie");
push("Robin");
push("Dustin");
push("Jonathan");

Jonathan

Dustin

Robin

Debbie

Rich

 

 

 

char *str1 = peek();

Jonathan

Dustin

Robin

Debbie

Rich

str1은 "Jonathan"이 됨

 

 

 

char *str2 = pop();

Dustin

Robin

Debbie

Rich

str2는 "Jonathan"이 되고 스택의 상태는 위와 같이 바뀜.

 

 

 

push("Philip");

Philip

Dustin

Robin

Debbie

Rich

 

 

스택 응용 예: 괄호 검사 문제

 

입력 수식의 괄호가 올바른지 검사

예: [ a + b * { c / ( d - e ) } ] + ( d / e )

어떻게 검사할 것인가?

여는 괄호, 닫는 괄호 갯수가 같아야한다.

갯수만 같다고 올바른 것은 아님, 순서가 맞아야 함.

스택을 이용하여 검사

* 여는 괄호가 나오면 푸시.

* 닫힌 괄호가 나오면 탑에 있는 괄호를 팝해서 동일한 타입의 괄호인지를 판단.

* 마지막에 스택에 남는 괄호가 없어야 함.

 

 

// paren_checker.c
#include <stdio.h>
#include <string.h>
#include "stack.h" // 문자(char)들을 저장하는 스택이 stack.c파일에 구현되어 있다고 가정한다.

#define MAX_LENGTH 100

char OPEN[] = "([{";
char CLOSE[] = ")]}";

int is_balanced(char *expr);
int is_open(char ch);
int is_close(char ch);

int main()
{
	char expr[MAX_LENGTH];
    scanf("%s", expr);
    if (is_balanced(expr))
    	printf("%s: balanced.\n", expr);
    else
    	printf("%s: unbalanced.\n", expr);
}

int is_balanced(char *expr)
{
	int balanced = 1;
    int index = 0;
    while (balanced && index < strlen(expr))
    {
    	char ch = expr[index];
        if (is_open(ch) > -1)
        	push(ch);
        else if (is_close(ch) > -1)
        {
        	if (is_empty())
            {
            	balanced = 0;
                break;
            }
            char top_ch = pop();
            if (is_open(top_ch) != is_close(ch))
            {
            	balanced = 0;
            }
        }
        index++;
    }
    return (balanced == 1 && is_empty() == 1);
}

int is_close(char ch)
{
	for (int i = 0; i < strlen(CLOSE); i++)
    {
    	if (CLOSE[i] == ch)
        	return i;
    }
    return -1;
}

int is_open(char ch)
{
	for (int i = 0; i < strlen(OPEN); i++)
    {
    	if (OPEN[i] == ch)
        	return i;
    }
    return -1;
}