[자료구조] Stack

[Unity/C#] 스택 (Stack)

1. Stack가 무엇인지 알고 있나요? 어떤 방식으로 작동하는지 설명할 수 있을까요?

• Stack은 데이터를 저장하고 관라하는 자료구조 중 하나로, 데이터 추가와 삭제가 한 쪽 끝에서만 일어난다. 즉, LIFO (Last In First Out)로 작동된다.

2. Stack의 특성을 설명해주세요.

후입선출 (LIFO, Last In, First Out)

• 데이터가 스택에 추가될 때는 항상 맨 위에 쌓이고, 제거될 때는 가장 나중에 추가된 데이터부터 제거된다.

• 연산 속도
  • 스택은 한 쪽 끝에서만 삽입/삭제가 일어나기 때문에 Push, Pop, Peek 등을 사용할 때, 연산 속도가 빠르다
  • [ O(1) ]
• 제한된 접근
  • 스택에서는 가장 최근에 추가된 요소만 접근할 수 있으며, 중간에 있는 데이터에는 직접 접근할 수 없다.

3. Stack은 언제 사용하면 좋은 자료구조인가요? 반대로 언제 사용하기 불리할까요?

• 사용하면 좋은 경우
  • Memento 패턴: 행동들을 저장하는 자료구조에 쓰기 적합합니다.
  • 전 행동으로 돌아갈 때: 되돌리기 기능을 구현할 때 사용하면 좋습니다.
• 사용하기 불리한 경우
  • 중간 데이터를 조작해야 할 때: 마지막에 저장된 데이터 말고는 조작할 수 없으므로, 마지막이 아닌 다른 순서에 있는 데이터를 조작해야 할 때는 사용하기 어렵습니다.

4. Stack을 본인의 프로젝트에 적용해본 경험을 말해주세요.

• 따로 스택을 적용해본 경험은 없어 사용하면 좋을 것 같은 경우를 말하겠다.
• 되돌리기 기능을 만들 때, 스택을 사용하면 유용할 것 같다.
  • ex) 상점, 캐릭터 행동, 씬 전환 등

---

스택 예제 1

public class My_Stack<T>
{
    private T[] data = new T[1000];
    private int top = -1;

    public bool IsEmpty()
    {
        // ****** CODE HERE ******
        return top == -1;
        // ***********************
    }

    public void Push(T item)
    {
        // ****** CODE HERE ******
        top++;
        data[top] = item;
        // ***********************
    }

    public T Pop()
    {
        // ****** CODE HERE ******
        if (top == -1)
        {
            throw new InvalidOperationException("Stack is empty.");
        }

        T item = data[top];
        data[top] = default;
        top--;

        return item;

        // ***********************
    }

    public int Count()
    {
        // ****** CODE HERE ******
        return top + 1;
        // ***********************
    }
}

// 구현 확인을 위한 코드입니다.
class Program
{
    static void Main(string[] args)
    {
        Stack<int> s = new Stack<int>();
        My_Stack<int> s_new = new My_Stack<int>();

        for (int i = 0; i < 10; ++i)
        {
            s.Push(i);
            s_new.Push(i);
        }

        while (s.Count > 0)
        {
            Console.WriteLine($"s => {s.Pop()} | s_new => {s_new.Pop()}");
            Console.WriteLine($"size of q : {s.Count} | size of s_new : {s_new.Count}");
            Console.WriteLine("------------------------------------------------------");
        }
    }
}

 

스택 예제 2

class Program
{
    struct ScreenOption
    {
        public string Description;
        public LinkedList<string> Options;
    }

    static Stack<string> screenStack = new Stack<string>();
    static Dictionary<string, (string Description, LinkedList<string> Options)> screens = new Dictionary<string, (string, LinkedList<string>)>
    {
        { "MainScreen", ("메인 화면", new LinkedList<string>(new[] { "CharacterScreen", "InventoryScreen" })) },
        { "CharacterScreen", ("캐릭터 화면", new LinkedList<string>(new[] { "StatusScreen", "EquipmentScreen" })) },
        { "InventoryScreen", ("인벤토리 화면", new LinkedList<string>(new[] { "UseItemScreen", "DropItemScreen" })) },
        { "StatusScreen", ("상태 화면\n여기에는 캐릭터의 상태가 표시됩니다.", new LinkedList<string>()) },
        { "EquipmentScreen", ("장비 화면\n여기에는 캐릭터의 장비가 표시됩니다.", new LinkedList<string>()) },
        { "UseItemScreen", ("아이템 사용 화면\n여기에는 사용할 수 있는 아이템이 표시됩니다.", new LinkedList<string>()) },
        { "DropItemScreen", ("아이템 버리기 화면\n여기에는 버릴 수 있는 아이템이 표시됩니다.", new LinkedList<string>()) }
    };

    static void Main(string[] args)
    {
        // 초기 화면 설정
        screenStack.Push("MainScreen");

        // 화면 출력 루프 시작
        while (screenStack.Count > 0)
        {
            DisplayScreen();
        }
    }

    // 화면 출력 및 입력 처리 메서드
    static void DisplayScreen()
    {
        while (true)
        {
            Console.Clear();
            string currentScreen = screenStack.Peek();/* TODO : 현재 Screen을 Stack으로 부터 받아오는 기능 작성 */
            var screenData = screens[currentScreen];

            Console.WriteLine(screenData.Description);

            int optionNumber = 1;
            foreach (var option in screenData.Options)
            {
                Console.WriteLine($"{optionNumber}. {screens[option].Description.Split('\n')[0]}으로 이동");
                optionNumber++;
            }

            // 스택의 크기에 따라 "0. 종료" 또는 "0. 뒤로 돌아가기" 옵션 추가
            if (screenStack.Count == 1)
                Console.WriteLine("0. 종료");
            else
                Console.WriteLine("0. 뒤로 돌아가기");

            string input = Console.ReadLine();

            if (input == "0")
            {
                // TODO : 0을 입력받을 경우 전 화면으로 돌아가는 기능 작성 ********
                // screenStack의 가장 상단 screen을 제거 **************************
                screenStack.Pop();
                // ****************************************************************
                break;
            }
            else
            {
                int selectedOption;
                if (int.TryParse(input, out selectedOption) && selectedOption > 0 && selectedOption <= screenData.Options.Count)
                {
                    var selectedScreen = GetScreenByOptionNumber(screenData.Options, selectedOption);
                    if (selectedScreen != null)
                    {
                        // TODO : 다음으로 이동할 screen을 설정해주는 기능 작성 ****
                        // screenStack에 selectedScreen을 집어넣기 *****************
                        screenStack.Push(selectedScreen);
                        // *********************************************************
                        break;
                    }
                }
                Console.WriteLine("잘못된 입력입니다. 다시 시도해주세요.");
            }
        }
    }

    static string GetScreenByOptionNumber(LinkedList<string> options, int optionNumber)
    {
        if (optionNumber <= 0 || optionNumber > options.Count)
            return null;

        var currentNode = options.First;
        for (int i = 1; i < optionNumber; i++)
            currentNode = currentNode.Next;

        return currentNode.Value;
    }
}