실행 가능한 C# 문서: Stack

Q: C#에서 Stack이란 무엇인가요?

System.Collections.Generic의 Stack 는 후입선출(LIFO) 컬렉션입니다. Push는 맨 위에 항목을 올리고, Pop은 맨 위 항목을 제거해 반환하며, Peek은 맨 위 항목을 제거하지 않고 반환합니다. 셋 모두 상수 시간에 실행됩니다.

Q: C#에서 빈 스택에 Pop하면 어떻게 되나요?

스택이 비어 있으면 Pop과 Peek은 InvalidOperationException을 던집니다. 먼저 stack.Count > 0을 확인하거나, 예외 대신 false를 반환하는 TryPop(out var item)과 TryPeek(out var item)을 쓰세요(.NET Core 2.0 이상).

Q: foreach는 Stack을 어떤 순서로 순회하나요?

위에서 아래로 순회합니다. 가장 최근에 넣은 항목이 먼저 나오며, Pop이 반환할 순서와 같습니다. ToArray()도 같은 순서를 씁니다. 그 결과 new Stack (otherStack)은 뒤집힌 복사본을 만듭니다. 생성자가 열거하는 순서대로 항목을 넣기 때문입니다.

Q: C#에서 Stack과 Queue의 차이는 무엇인가요?

Stack 는 가장 새로운 항목을 먼저 반환하고(후입선출), Queue 는 가장 오래된 항목을 먼저 반환합니다(선입선출). 실행 취소 기록, 중첩 구조, 깊이 우선 탐색에는 스택을, 도착 순서대로 작업을 처리하거나 너비 우선 탐색에는 큐를 쓰세요.

Q: C#에서 괄호 짝이 맞는지 어떻게 확인하나요?

문자열을 한 번 훑습니다. 여는 괄호는 모두 Stack 에 넣습니다. 닫는 괄호마다 스택이 비어 있지 않아야 하고 맨 위가 짝이 맞는 여는 괄호여야 하며, 그 괄호를 꺼냅니다. 훑기가 끝났을 때 스택이 비어 있으면 짝이 맞습니다.

Stack<T>는 더미입니다. Push로 맨 위에 항목을 올리고 Pop으로 맨 위에서 꺼내므로, 마지막에 들어간 항목이 처음 나옵니다(LIFO). 맨 위만 접근할 수 있고, 그에 대한 모든 연산은 상수 시간이 걸립니다.

Push, Pop, Peek

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var plates = new Stack<string>();
        plates.Push("blue");
        plates.Push("red");
        plates.Push("green");

        Console.WriteLine("On top: " + plates.Peek()); // look only
        Console.WriteLine("Count: " + plates.Count);

        Console.WriteLine("Took " + plates.Pop());       // remove the top
        Console.WriteLine("On top: " + plates.Peek());

        while (plates.Count > 0)
        {
            Console.WriteLine("Took " + plates.Pop());
        }
        Console.WriteLine("Count: " + plates.Count);
    }
}

출력:

On top: green
Count: 3
Took green
On top: red
Took red
Took blue
Count: 0

green이 마지막에 들어갔으므로 가장 먼저 나옵니다. Peek은 스택을 바꾸지 않고 맨 위를 반환하며, 꺼낼지 정하기 전에 Pop이 무엇을 줄지 살펴보는 방법입니다.

빈 스택 예외와 TryPop

빈 스택에서 꺼내거나 들여다보면 InvalidOperationException이 발생합니다. 닫는 항목이 여는 항목보다 많은 입력을 받는 파서와 알고리즘에서 가장 자주 나타납니다.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var history = new Stack<int>();

        try
        {
            history.Pop();
        }
        catch (InvalidOperationException e)
        {
            Console.WriteLine("Caught " + e.GetType().Name);
        }

        history.Push(10);

        int value;
        Console.WriteLine(history.TryPop(out value) + " " + value);
        Console.WriteLine(history.TryPop(out value) + " " + value); // empty now
    }
}

출력:

Caught InvalidOperationException
True 10
False 0

TryPop과 TryPeek(.NET Core 2.0 이상)은 빈 스택에서 false를 반환하고 out 변수를 기본값(여기서는 0)으로 설정합니다. .NET Framework에서는 먼저 Count > 0을 확인하세요.

순회 순서: 맨 위부터

스택을 열거해도 아무것도 제거되지 않으며, 위에서 아래로, Pop이 항목을 반환할 순서대로 진행합니다:

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        var pages = new Stack<string>();
        pages.Push("home");
        pages.Push("products");
        pages.Push("checkout");

        foreach (string page in pages)
        {
            Console.Write(page + " ");
        }
        Console.WriteLine();

        Console.WriteLine(string.Join(" > ", pages.ToArray()));
        Console.WriteLine(pages.Contains("home"));

        var copy = new Stack<string>(pages);  // pushes in enumeration order...
        Console.WriteLine(copy.Peek());        // ...so the copy is reversed

        var sameOrder = new Stack<string>(pages.Reverse());
        Console.WriteLine(sameOrder.Peek());
    }
}

출력:

checkout products home 
checkout > products > home
True
home
checkout

뒤집힌 복사본에 사람들이 자주 걸립니다. 생성자는 어떤 IEnumerable<T>든 받아 그 항목을 순서대로 넣는데, 스택은 맨 위부터 열거되므로 예전의 맨 위가 복사본의 맨 아래에 놓입니다. 시퀀스를 먼저 뒤집으면(LINQ의 Reverse()는 항목을 맨 아래부터 반환합니다) 맨 위가 같은 복사본이 됩니다.

항목 목록을 새 스택에 넣으면 순서가 뒤집히므로, 시퀀스를 빠르게 뒤집는 방법이기도 합니다. new Stack<char>("hello")는 o, l, l, e, h를 꺼내 줍니다.

예제: 실행 취소 기록

편집기는 모든 변경을 스택에 보관합니다. 실행 취소는 가장 최근 변경을 꺼내 되돌리고, 다시 실행은 취소한 변경을 두 번째 스택에 보관합니다.

using System;
using System.Collections.Generic;

class Editor
{
    private string text = "";
    private readonly Stack<string> undo = new Stack<string>();
    private readonly Stack<string> redo = new Stack<string>();

    public void Type(string s)
    {
        undo.Push(text);   // remember the state before the change
        redo.Clear();      // a new change invalidates the redo history
        text += s;
    }

    public void Undo()
    {
        if (undo.Count == 0) return;
        redo.Push(text);
        text = undo.Pop();
    }

    public void Redo()
    {
        if (redo.Count == 0) return;
        undo.Push(text);
        text = redo.Pop();
    }

    public string Text { get { return text; } }
}

class Program
{
    static void Main()
    {
        var ed = new Editor();
        ed.Type("Hello");
        ed.Type(", world");
        ed.Type("!");
        Console.WriteLine(ed.Text);

        ed.Undo();
        Console.WriteLine(ed.Text);
        ed.Undo();
        Console.WriteLine(ed.Text);

        ed.Redo();
        Console.WriteLine(ed.Text);
    }
}

출력:

Hello, world!
Hello, world
Hello
Hello, world

전체 스냅샷을 저장하는 것이 가장 단순한 버전입니다. 실제 편집기는 대신 작은 명령 객체(무엇을 어디에 삽입했는지)를 넣고 각 객체가 자신을 되돌리는 메서드를 갖지만, 두 스택은 같은 방식으로 동작합니다.

예제: 괄호 짝 검사

(, [, {가 올바른 순서로 닫히는지 확인하는 것은 표준적인 스택 연습 문제이며, 같은 로직이 모든 컴파일러와 JSON 파서 안에 들어 있습니다.

using System;
using System.Collections.Generic;

class Program
{
    static bool IsBalanced(string s)
    {
        var open = new Stack<char>();
        foreach (char c in s)
        {
            if (c == '(' || c == '[' || c == '{')
            {
                open.Push(c);
            }
            else if (c == ')' || c == ']' || c == '}')
            {
                if (open.Count == 0) return false;          // closer with no opener
                char top = open.Pop();
                if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{')) return false; // wrong kind
            }
        }
        return open.Count == 0;                             // leftovers are unclosed
    }

    static void Main()
    {
        string[] inputs = { "f(a[i], {x: 1})", "(]", "((a)", "a)b(", "" };
        foreach (string input in inputs)
        {
            Console.WriteLine("\"" + input + "\" -> " + IsBalanced(input));
        }
    }
}

출력:

"f(a[i], {x: 1})" -> True
"(]" -> False
"((a)" -> False
"a)b(" -> False
"" -> True

세 가지 실패 검사는 괄호가 틀릴 수 있는 세 가지 방식에 대응합니다. 열린 것이 없는 닫는 괄호(a)b(, Pop의 예외 대신 Count == 0으로 잡음), 종류가 틀린 닫는 괄호((]), 끝내 닫히지 않은 여는 괄호(((a), 마지막 검사로 잡음)입니다.

그 밖의 용도

깊이 우선 탐색. 너비 우선 탐색의 큐를 스택으로 바꾸면 순회가 넓게 가기 전에 깊게 갑니다. 명시적인 스택은 입력이 깊어서 잡을 수 없는 StackOverflowException이 날 위험이 있을 때 재귀를 대체하기도 합니다.
식 계산. 후위 표기법(3 4 + 2 *)은 숫자를 넣고 연산자마다 두 개를 꺼내서 계산합니다.
백트래킹. 탐색 기록, 미로 풀기, 파서 상태는 위치를 넣고 막다른 곳에서 그 위치로 꺼내 돌아갑니다.

선입선출 대응물은 Queue를 참고하세요.

Stack과 Queue와 List

	`Stack<T>`	`Queue<T>`	`List<T>`
나오는 순서	가장 새것부터	가장 오래된 것부터	인덱스로 아무것이나
추가	`Push`	`Enqueue`	`Add`, `Insert`
제거	`Pop`(맨 위)	`Dequeue`(앞)	`Remove`, `RemoveAt`
보기	`Peek`	`Peek`	`list[i]`
안전한 변형	`TryPop`, `TryPeek`	`TryDequeue`, `TryPeek`	필요 없음

여러 스레드에서는 System.Collections.Concurrent의 ConcurrentStack<T>가 잠금 없이 Push, TryPop, TryPeek을 제공합니다.

흔한 실수

확인하지 않고 꺼내기. 빈 스택은 InvalidOperationException을 던집니다. Count를 확인하거나 TryPop을 쓰세요.
foreach가 처음 넣은 항목부터 가리라 기대하기. 맨 위부터 갑니다.
new Stack<T>(stack)으로 복사하기. 복사본이 뒤집힙니다.
같은 스택에 대한 foreach 안에서 넣기. 예외가 발생합니다. while (stack.Count > 0) 루프를 쓰세요.

자주 묻는 질문

C#에서 Stack이란 무엇인가요?

System.Collections.Generic의 Stack<T>는 후입선출(LIFO) 컬렉션입니다. Push는 맨 위에 항목을 올리고, Pop은 맨 위 항목을 제거해 반환하며, Peek은 맨 위 항목을 제거하지 않고 반환합니다. 셋 모두 상수 시간에 실행됩니다.

C#에서 빈 스택에 Pop하면 어떻게 되나요?

스택이 비어 있으면 Pop과 Peek은 InvalidOperationException을 던집니다. 먼저 stack.Count > 0을 확인하거나, 예외 대신 false를 반환하는 TryPop(out var item)과 TryPeek(out var item)을 쓰세요(.NET Core 2.0 이상).

foreach는 Stack을 어떤 순서로 순회하나요?

위에서 아래로 순회합니다. 가장 최근에 넣은 항목이 먼저 나오며, Pop이 반환할 순서와 같습니다. ToArray()도 같은 순서를 씁니다. 그 결과 new Stack<T>(otherStack)은 뒤집힌 복사본을 만듭니다. 생성자가 열거하는 순서대로 항목을 넣기 때문입니다.

C#에서 Stack과 Queue의 차이는 무엇인가요?

Stack<T>는 가장 새로운 항목을 먼저 반환하고(후입선출), Queue<T>는 가장 오래된 항목을 먼저 반환합니다(선입선출). 실행 취소 기록, 중첩 구조, 깊이 우선 탐색에는 스택을, 도착 순서대로 작업을 처리하거나 너비 우선 탐색에는 큐를 쓰세요.

C#에서 괄호 짝이 맞는지 어떻게 확인하나요?

문자열을 한 번 훑습니다. 여는 괄호는 모두 Stack<char>에 넣습니다. 닫는 괄호마다 스택이 비어 있지 않아야 하고 맨 위가 짝이 맞는 여는 괄호여야 하며, 그 괄호를 꺼냅니다. 훑기가 끝났을 때 스택이 비어 있으면 짝이 맞습니다.