[Data Structures & Algorithms] 스택(Stack)의 이해와 응용

🧿 스택(Stack) 이란?

스택(Stack)이란 한쪽 끝에서만 데이터를 삽입하고 삭제할 수 있는 선형 자료구조를 의미하며, 마지막으로 삽입된 원소가 가장 먼저 삭제되는 "후입선출(LIFO, Last-In-First-Out)"의 특징을 가진다.

스택(Stack) 자료구조는 데이터를 저장하고 관리하는데 사용되며 주로 함수 호출, 재귀 알고리즘, 뒤로가기 기능 등에서 활용된다.

 

---

 

💙 스택(Stack)에서의 연산 알고리즘

삭제 연산	삽입 연산
pop	push

 

① 스택의 push() 알고리즘

push(S,x)
    
    top <- top + 1; //마지막 자료 top 위에 자료를 삽입하기 위해 top의 위치를 1증가시킴
    
    //top의 위치키 스택 크기보다 크다면 오버플로우 발생
    if (top > stack_SIZE) then overflow;
    else //오버플로우 상태가 아닌 경우 아래 코드 실행
    {
        S(top) <- x; //스택의 top이 가리키는 위치에 x 삽입
    }

end push()

 

 

② 스택의 pop() 알고리즘

pop(S)

    if (top == 0)
    {
        overflow;
    }
    else //스택이 공백 상태가 아닐 경우 삭제 연산 수행
    {
        return S(top); //top 에 있는 원소 삭제 후 반환
        top <- top -1; //스택의 원소 1개가 삭제되었으니 top 위치를 1 감소시킴
    }
    
end pop()

 

---

 

💙 스택(Stack)의 추상 자료형

ADT Stack

    createStack(S) ::= create an empty Stack S; //공백 스택 S 생성
    
    //스택의 공백 여부 확인
    isEmpty(S) ::= if (S is empty) then return true
                   else return false;
                   
//스택의 top에 item(원소) 삽입
push(S, item) ::= insert item onto the top of Stack S;

 //스택의 top에 있는 원소 반환
pop(S) ::= if (isEmpty(S)) then return error
           else return the top item of the Stack S;
           
End Stack

 

---

 

💙 순차 자료구조와 스택(Stack)의 구현

: 스택은 순차 자료구조인 1차원 배열을 이용하여 구현할 수 있다.

 

• 스택의 크기  ==  배열의 크기
• 스택 원소의 순서  ==  배열 원소의 인덱스
• 변수 top  ==  스택에 저장된 마지막 원소에 대한 인덱스

 

인덱스 0	스택의 첫 번째 원소
인덱스 n-1	스택의 n 번째 원소
공백 상태	top = - 1
포화 상태	top = n - 1

 

※ 순차 자료구조로 구현한 스택의 장단점

장점  :  순차 자료구조인 1차원 배열을 사용하여 쉽게 구현이 가능함

단점  :  물리적으로 크기가 고정되어 스택 크기를 변경하기 어려움

 

---

 

💙 연결 자료구조와 스택(Stack)의 구현

 

• 스택의 원소  ==  단순 연결 리스트의 노드
• 스택 원소의 순서  ==  노드의 링크 포인터로 연결
• 변수 top  ==  단순 연결 리스트이 마지막 노드를 가리키는 포인터 변수
• 초기의 top 상태  ==  null

 

---

 

💙 스택(Stack)의 응용_1) 시스템 스택 (System Stack)

: 프로그램에서의 호출 및 복귀에 따른 수행 순서 관리

① 함수 호출 발생 시 함수 수행에 필요한 정보를 스택 프레임에 저장
② 스택 프레임에 저장한 값을 시스템 스택에 삽입
③ 함수의 실행이 끝나면 시스템 스택의 top 원소를 삭제
④ 프레임에 저장되었는 복귀 주소 확인 후 복귀

 

-->  위 과정을 반복하여 전체 프로그램 수행이 종료되면 시스템 스택은 공백 상태가 된다.

 

---

 

💙 스택(Stack)의 응용_2) 수식의 괄호 검사

: 수식에 포함된 괄호들의 경우 가장 마지막에 열린 괄호를 가장 먼저 닫아주어야 함

-->  후입 선출 구조인 Stack을 이용하여 괄호 검사 가능

 

※ 수식을 왼쪽에서 오른쪽으로 읽어가며 검사 진행

① 왼쪽 괄호를 만나면 Stack에 push

② 오른쪽 괄호를 만나면 스택을 pop 하여 마지막에 저장된 괄호와 같은 종류인지 여부 확인
-->  같은 종류가 아니라면 수식에 오류가 있는 것

③ 검사 완료 후 스택의 상태는 공백
-->  공백 상태가 아닌 경우 오류가 있는 수식

 

testPair()
    exp <- Expression;
    Stack <- null;
    
    while (true) do
    {
        symbol <- getSymbol(exp);
        
        case
        {
            symbol = "(" or "[" of "{" :
                        push(Stack, symbol);
            symbol = ")" :
                        open_pair != "(") then return false;
            symbol = "]" :
                        open_pair <- pop(Stack);
                        if (open_pair != "[") then return false;
            symbol = "}" :
                        open_pair <- pop(Stack);
                        if (open_pair != "{") then return false;
            symbol = null :
                        if (isEmpty(Stack)) then return true;
                        else return false;
            else :
        }
    }
end testPair()

 

---

 

💙 스택(Stack)의 응용_3) 수식의 표기법 변환

수식 표기법
전위 표기법 (Prefix Notation)	중위 표기법 (Infix Notation)	후위 표기법 (Postfix Notation)
연산자를 피연산자 앞에 표기	연산자를 피연산자 가운데에 표기	연산자를 피연산자 뒤에 표기
+ A B	A + B	A B +

 

A) 중위 표기식  -->  전위표기식

① 수식의 각 연산자에 대해 우선순위를 반영하여 괄호를 사용하여 표현
A * B + C / D  -->  ( (A * B) + (C / D) )

② 각 연산자를 그에 대응하는 좌측 괄호 앞으로 이동
( ( A * B ) + ( C / D ) )  -->  + ( * ( A B ) / ( C D ) )

③ 2번 결과에서 괄호만 제거
+ * A B / C D

 

 

B) 중위 표기식  -->  후위표기식

① 수식의 각 연산자에 대해 우선순위를 반영하여 괄호를 사용하여 표현
A * B + C / D  -->  ( ( A * B ) + ( C / D ) )

② 각 연산자를 그에 대응하는 우측 괄호의 뒤로 이동
( ( A * B ) + ( C / D ) )  -->  ( ( A B ) * ( C D ) / ) +

③ 2번 결과에서 괄호만 제거
A B * C D / +

 

※ 컴퓨터 내부에서의 표기법 변환

① 왼쪽 괄호를 만나면 무시하고 다음 문자 읽어들임
② 피연산자를 만나면 출력
③ 연산자를 만나면 스택에 삽입
④ 우측 괄호를 만나면 스택을 pop하여 출력
⑤ 수식이 끝나면 스택이 공백이 될 때까지 pop 하여 출력

 

infix_to_postfix(exp)

    while (true) do
    {
        symbol <- getSymbol(exp);
        
        case
        {
            symbol = operand : //피연산자 만나면 출력
                        print(symbol);
            symbol = operator : //연산자 만나면 스택에 push
                        push(stack, symbol);
            symbol = ")" : //우측 괄호 만나면 스택을 pop하여 출력
                        print(pop(stack));
            symbol = null : //수식의 끝 처리
                        while (top > - 1) do //스택이 공백 상태가 될 때까지 pop하여 출력
                        {
                            print(pop(stack));
                        }
        else :
        }
    }
    
end infix_to_postfix()

 

 

C) 후위 표기법 수식 연산

① 피연산자 만나면 스택에 push
② 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산
③ 연산 결과를 다시 스택에 push
④ 수식이 끝나면 스택을 pop하여 출력

 

evalPostfix(exp)

    while (true) do
    {
        symbol <- getSymbol(exp);
        
        case
        {
            symbol = operand :
                        push(Stack, symbol);
            symbol = operator :
                        opr2 <- pop(Stack);
                        opr1 <- pop(Stack);
                        
                        //스택에서 꺼낸 피연산자들을 연산자 형태로 연산함
                        result <- opr1 op(symbol) opr2;
                        push(Stack, result);
            symbol = null :
                        print(pop(stack));
        else :
        }
    }
    
end evalPostfix()