넣고 빼는 순서가 규칙이다
Esc

    넣고 빼는 순서가 규칙이다

    –C#자료구조

    지금까지 본 것들은 전부 어느 것을 꺼낼지 우리가 골랐습니다. 배열과 List 는 번호로, Dictionary 는 키로 골랐습니다.

    그런데 고르면 안 되는 경우가 있습니다.

    되돌리기(Undo)를 만든다고 해 봅시다. 사용자가 되돌리기를 누르면 가장 최근에 한 일을 취소해야 합니다. 세 번째로 한 일이 아니라요. 프린터 대기열이라면 반대입니다. 가장 먼저 넣은 것이 먼저 나와야 합니다.

    List 로도 됩니다. list[list.Count - 1] 을 꺼내고 지우면 최근 것입니다. 문제는 실수할 자리가 열려 있다는 것입니다. list[5] 를 꺼내는 코드를 누가 끼워 넣어도 컴파일이 됩니다.

    꺼낼 것을 자료구조가 정해 주면, 규칙을 어길 방법 자체가 없어집니다.

    Stack 은 나중에 넣은 것이 먼저 나온다

    책을 쌓아 올린 것과 같습니다. 위에 올리고, 위에서 꺼냅니다. 아래쪽 책을 빼려면 위를 다 치워야 합니다.

    1 2 3 Push Pop 넣는 자리와 꺼내는 자리가 같다 마지막에 넣은 3 이 맨 위에 있다. 1 은 위가 비워질 때까지 못 나온다.
    위로 쌓고 위에서 꺼낸다.
    using System.Collections.Generic;

Stack<int> stack = new Stack<int>();

stack.Push(1);
stack.Push(2);
stack.Push(3);

Console.WriteLine(stack.Pop());     // 3
Console.WriteLine(stack.Pop());     // 2
    • Push 넣기
    • Pop 꺼내면서 지우기
    • Peek 꺼내 보기만 하고 안 지우기
    • Count 몇 개 들어 있는지

    꺼낼 자리를 고르는 방법이 없습니다. 그게 이 자료구조의 요점입니다.

    이 성질을 후입선출, 나중에 들어온 것이 먼저 나온다고 합니다.

    어디에 쓰냐면, 되돌아가야 하는 일 전부입니다.

    • 되돌리기: 마지막에 한 일부터 취소
    • 브라우저 뒤로 가기: 마지막에 본 페이지부터
    • 괄호 짝 맞추기: 여는 괄호를 쌓아 두고, 닫는 괄호를 만나면 하나 꺼내 짝을 본다

    그리고 이미 쓰고 있었습니다. 메서드를 호출하면 돌아올 자리를 어딘가에 쌓아 두는데, 그 어딘가가 스택입니다. 그래서 그 메모리 영역 이름이 스택입니다.

    Queue 는 먼저 넣은 것이 먼저 나온다

    줄을 서는 것과 같습니다. 뒤로 서고 앞에서 빠집니다.

    1 2 3 Enqueue Dequeue 처음에 넣은 1 이 맨 앞에 있다. 넣는 자리와 꺼내는 자리가 반대편이다.
    뒤로 넣고 앞에서 꺼낸다.
    Queue<int> queue = new Queue<int>();

queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);

Console.WriteLine(queue.Dequeue());    // 1
Console.WriteLine(queue.Dequeue());    // 2
    • Enqueue 뒤에 넣기
    • Dequeue 앞에서 꺼내면서 지우기
    • Peek 앞에 있는 것을 보기만 하기

    이름이 Push / Pop 이 아닙니다. 넣는 쪽과 빼는 쪽이 다르니 이름도 다릅니다.

    이쪽은 선입선출, 먼저 들어온 것이 먼저 나옵니다.

    쓰는 곳은 순서대로 처리해야 하는 일입니다.

    • 프린터 대기열, 주문 처리
    • 게임에서 이번 프레임에 들어온 입력을 들어온 순서대로 처리
    • 너비 우선 탐색처럼 가까운 것부터 훑는 알고리즘

    List 로도 되는데 왜 쓰나

    List 로 흉내 낼 수 있습니다. 그런데 두 가지가 다릅니다.

    첫째, 규칙이 코드에 드러납니다.

    List<int> history = new List<int>();

    이 줄만 보고는 이게 순서대로 처리하는 것인지, 되돌리는 것인지, 그냥 목록인지 모릅니다.

    Stack<int> history = new Stack<int>();

    이 줄은 “마지막 것부터 꺼낼 것” 이라고 말하고 있습니다. 읽는 사람에게 알려 주고, 동시에 다르게 쓸 방법을 막습니다. 앞에서 이름을 붙이면 약속이 코드에 남는다고 했는데, 같은 이야기입니다. 여기서는 타입이 그 역할을 합니다.

    둘째, Queue 는 속도가 다릅니다.

    앞 글에서 List 의 맨 앞을 지우면 뒤가 전부 밀린다고 했습니다. Queue 를 List 로 만들면 Dequeue 마다 그 일이 일어납니다.

    Queue 는 그렇게 하지 않습니다. 값을 옮기는 대신 앞이 어디인지를 가리키는 표시를 옮깁니다. 배열을 원형으로 쓴다고 생각하면 됩니다. 끝에 닿으면 앞쪽 빈자리로 돌아옵니다. 앞에서 정수를 원으로 본 것과 같은 발상입니다.

    비었는데 꺼내면 터진다

    Stack<int> stack = new Stack<int>();

stack.Pop();     // InvalidOperationException

    배열에서 없는 칸, Dictionary 에서 없는 키를 건드렸을 때와 같습니다.

    그래서 꺼내기 전에 확인합니다.

    while (queue.Count > 0)
{
    Process(queue.Dequeue());
}

    TryPop / TryDequeue 도 있습니다. Dictionary 의 TryGetValue 와 같은 모양입니다. 성공했는지를 돌려주고 값은 따로 담아 줍니다.

    if (stack.TryPop(out int value))
{
    Console.WriteLine(value);
}

    정리

    • Stack 과 Queue 는 꺼낼 것을 우리가 고르지 않습니다. 자료구조가 정합니다.
    • Stack 은 나중에 넣은 것이 먼저 나옵니다. Push / Pop / Peek.
    • Queue 는 먼저 넣은 것이 먼저 나옵니다. Enqueue / Dequeue / Peek.
    • 되돌아가는 일은 Stack, 순서대로 처리하는 일은 Queue 입니다.
    • List 로도 되지만, 타입이 규칙을 드러내고 어길 방법을 막아 줍니다.
    • Queue 는 앞에서 빼도 뒤가 밀리지 않습니다. 표시만 옮깁니다.
    • 비었는데 꺼내면 예외입니다. Count 로 확인하거나 TryPop / TryDequeue 를 씁니다.