자료구조 - 동적 배열 스택

[동적 배열 스택]

동적 배열 스택은 배열을 기반으로 한 스택 구조로, 필요에 따라 크기가 동적으로 조절되는 특징을 가지고 있습니다.

C++에서는 동적 배열을 사용하여 스택을 구현할 수 있습니다.

동적 배열 스택의 예제와 설명을 살펴보겠습니다.

#include <iostream>

class DynamicArrayStack 
{
    private:
        int *arr;       // 동적 배열
        int capacity;   // 배열의 최대 크기
        int top;        // 스택의 가장 위 인덱스    

    public:
        DynamicArrayStack(int initialCapacity = 10) 
        {
            capacity = initialCapacity;
            arr = new int[capacity];
            top = -1;
        }

        ~DynamicArrayStack() 
        {
            delete[] arr;
        }

        bool isEmpty()
        {
            return (top == -1);
        }

        bool isFull() 
        {
            return (top == capacity - 1);
        }

        void push(int value)
        {
            if (isFull())
            {
                // 배열 크기가 부족할 경우 두 배로 확장
                int *tempArr = new int[2 * capacity];
                for (int i = 0; i < capacity; ++i) 
                {
                    tempArr[i] = arr[i];
                }    
                delete[] arr;
                arr = tempArr;
                capacity *= 2;
            }
            arr[++top] = value;
        }

        void pop() 
        {
            if (isEmpty()) 
            {
                std::cout << "Stack underflow!" << std::endl;
                return;
            }
            --top;
        }        

        int peek() 
        {
            if (isEmpty()) 
            {
            std::cout << "Stack is empty!" << std::endl;
                return -1;
            }
            return arr[top];
            }
};

int main() 
{
    DynamicArrayStack myStack;

    // 스택에 데이터 삽입
    myStack.push(10);
    myStack.push(20);
    myStack.push(30);

    // 스택의 가장 위(top) 요소 확인
    std::cout << "Top element of the stack: " << myStack.peek() << std::endl;

    // 스택에서 데이터 삭제
    myStack.pop();

    // 스택이 비어있는지 확인
    if (myStack.isEmpty()) 
    {
        std::cout << "Stack is empty." << std::endl;
    } 
    else
    {
        std::cout << "Stack is not empty." << std::endl;
    }

    return 0;
}

 

 

[동적 배열 스택의 장단점]

 

장점

 

• 유연한 크기 조절: 동적 배열을 사용하므로 스택의 크기를 동적으로 조절할 수 있습니다.
• 메모리 효율성: 필요한 만큼의 메모리만 사용하여 메모리를 효율적으로 관리할 수 있습니다.

 

단점

 

• 메모리 재할당 비용: 배열이 가득 찰 때마다 크기를 두 배로 확장하는 작업은 추가적인 메모리 재할당과 복사를 필요로 합니다.
• 메모리 낭비: 스택이 사용되지 않는 상태에서도 크기가 동적으로 유지되므로 메모리를 낭비할 수 있습니다.

 

 

 

[스택의 응용]

스택으로 괄호를 검사하는 문제나 후위 표기 수식의 계산, 미로 탐색을 해결할 수 있습니다.

여기서는 괄호를 검사하는 예제만 살펴보겠습니다.

 

괄호 검사 알고리즘

check_matching(expr):
    
whlie(입력 expr의 끝이 아니면)
ch <- expr의 다음 글자
switch(ch)
    case '(' : case '[' : case '{' :
        ch를 스택에 삽입
        break

	case ')' : case ']' : case'}' :
        if(스택이 비어있으면)
            then 오류
            else 스택에서 open_ch를 꺼낸다
                if(ch와 open_ch가 같은 짝이 아니면)
                    then 오류보고
        break

if(스택이 비어있지 않으면)
    then 오류

 

 

 

알고리즘을 토대로 코드를 작성해보겠습니다.

#include <iostream>
#include <stack>
#include <string>

bool isBalanced(const std::string& expression) 
{
    std::stack<char> brackets;

    for (char bracket : expression)
    {
        if (bracket == '(' || bracket == '[' || bracket == '{') 
        {
            brackets.push(bracket);
        } 
        else if (bracket == ')' || bracket == ']' || bracket == '}') 
        {
            if (brackets.empty()) 
            {
                return false; // 여는 괄호 없이 닫는 괄호가 나온 경우
            }
            else if ((bracket == ')' && brackets.top() != '(') ||
                       (bracket == ']' && brackets.top() != '[') ||
                       (bracket == '}' && brackets.top() != '{')) 
            {
                return false; // 괄호의 짝이 맞지 않는 경우
            }
            
            brackets.pop(); // 짝이 맞는 괄호를 제거
        }
    }

    return brackets.empty(); // 모든 괄호에 대한 검사가 끝나고 스택이 비어있는지 확인
}

int main() 
{
    std::string expression1 = "(a * (b + c))"; // 올바른 괄호 사용
    std::string expression2 = "[(a + b) * (c - d)]"; // 올바른 괄호 사용
    std::string expression3 = "{(a + b) * c]"; // 잘못된 괄호 사용

    std::cout << "Expression 1 is " << (isBalanced(expression1) ? "balanced" : "not balanced") << std::endl;
    std::cout << "Expression 2 is " << (isBalanced(expression2) ? "balanced" : "not balanced") << std::endl;
    std::cout << "Expression 3 is " << (isBalanced(expression3) ? "balanced" : "not balanced") << std::endl;

    return 0;
}



/*
[실행 결과]
Expression 1 is balanced
Expression 2 is balanced
Expression 3 is not balanced
*/