자료구조 - 스택(Stack)

 

 

스택(Stack) 이란?

 

 

스택(Stack)은 데이터 구조 중 하나로, 후입선출(LIFO, Last In First Out)의 원리를 따릅니다. 이 말은 가장 최근에 추가된 항목이 가장 먼저 제거되는 구조를 의미합니다. 새로운 데이터는 스택의 맨 위에 추가되며, 마지막에 추가된 데이터가 먼저 제거됩니다. 주로 함수 호출, 재귀 알고리즘, 괄호 검사, 미로 탐색 등과 같은 다양한 응용 프로그램에서 사용됩니다. 스택은 데이터를 저장하고 접근하는데 유용하며, 특히 데이터의 순서가 중요한 경우에 많이 활용됩니다.

 

스택 코드 예시 (C#)

아래 코드는 C#에서 stack 활용의 예시입니다.

using System;
using System.Collections.Generic;

public class StackExample
{
    public static void Main(string[] args)
    {
        Stack<int> stack = new Stack<int>();

        // 스택에 데이터 추가
        stack.Push(1);
        PrintStack(stack);
        stack.Push(2);
        PrintStack(stack);
        stack.Push(3);
        PrintStack(stack);

        // 스택에서 데이터 제거
        int poppedElement = stack.Pop();
        Console.WriteLine("Popped element: " + poppedElement);
        PrintStack(stack);

        // 스택의 맨 위 데이터 확인
        int topElement = stack.Peek();
        Console.WriteLine("Top element: " + topElement);
        PrintStack(stack);
    }

    public static void PrintStack(Stack<int> stack)
    {
        Console.Write("Stack elements: ");
        foreach (int item in stack)
        {
            Console.Write(item + " ");
        }
        Console.WriteLine();
    }
}

 

위 코드를 실행한 결과는 다음과 같습니다.

 

Stack elements: 1 
Stack elements: 2 1 
Stack elements: 3 2 1 
Popped element: 3
Stack elements: 2 1 
Top element: 2
Stack elements: 2 1

 

 

스택 활용 알고리즘 문제 (C#)

주어진 문자열이 올바른 괄호 짝을 가지고 있는지 확인하는 프로그램을 작성하십시오. 입력으로는 '(', ') 문자로만 이루어진 문자열이 주어집니다.

 

using System;
using System.Collections.Generic;

public class ValidParentheses
{
    public static bool IsValid(string s)
    {
        Stack<char> stack = new Stack<char>();
        foreach (char c in s)
        {
            if (c == '(')
            {
                stack.Push(c);
            }
            else if (c == ')')
            {
                if (stack.Count == 0 || stack.Pop() != '(')
                    return false;
            }
        }
        return stack.Count == 0;
    }

    public static void Main(string[] args)
    {
        string input1 = "((())";
        Console.WriteLine(input1 + " : " + IsValid(input1));

        string input2 = "()()";
        Console.WriteLine(input2 + " : " + IsValid(input2));

        string input3 = "((()))";
        Console.WriteLine(input3 + " : " + IsValid(input3));
    }
}

 

위 코드는 주어진 문자열이 올바른 괄호 짝을 가지고 있는지 확인하는 문제를 해결하기 위한 코드입니다. 입력 문자열을 반복하여 여는 괄호 '(' 를 만날 때마다 스택에 추가하고, 닫는 괄호 ')' 를 만날 때마다 스택에서 해당하는 여는 괄호를 제거합니다. 만약 닫는 괄호를 만났을 때 스택이 비어있거나 스택의 맨 위에 있는 괄호와 매칭되지 않는 경우에는 괄호가 올바르게 짝을 이루지 않으므로 false를 반환합니다. 모든 문자열을 순회한 뒤에는 스택이 비어있어야 올바른 괄호 짝을 가진 것으로 판별됩니다.

 

출력결과 입니다.

 

((()) : False
()() : True
((())) : True

 

 

 

스택의 장단점

 

- 장점

• 스택은 간단한 자료구조로 구현되어 있어서 구현이 쉽습니다.
• 항목 추가 및 제거가 맨 위에서만 이루어지기 때문에 상수 시간(O(1))에 접근할 수 있습니다.
• 스택은 동적 메모리 할당이 필요 없기 때문에 메모리 관리가 용이합니다.

- 단점

• 스택은 사전에 정해진 크기의 공간만 사용할 수 있기 때문에 크기 제한이 있을 수 있습니다.
• 스택은 후입선출의 특성 때문에 특정 유형의 문제에만 유용하며, 다른 문제에는 적합하지 않을 수 있습니다.

 

스택 사용 사례

 

• 함수 호출: 함수가 호출될 때마다 스택에 호출 정보를 저장하고, 함수가 반환될 때 스택에서 해당 정보를 제거합니다.
• 재귀 알고리즘: 재귀적으로 호출되는 함수의 호출 정보를 스택에 저장하여 재귀 알고리즘을 구현할 수 있습니다.
• 괄호 검사: 괄호의 짝이 맞는지 검사하기 위해 스택을 사용할 수 있습니다.
• 미로 찾기: 미로를 탐색하면서 각 위치를 스택에 저장하여 경로를 찾을 수 있습니다.

 

스택은 간단하면서도 유용한 자료구조로, 다양한 알고리즘 및 응용 프로그램에서 활용됩니다. 따라서 스택의 개념과 활용법을 잘 이해하면 프로그래밍 역량을 향상시키는 데 도움이 될 것입니다.