[TIL 24.07.11] 09. 선형 자료구조 - Stack

.

 

목   차

 

확인 문제

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

Stack은 선입후출의 방식으로 작동하는 자료구조이다. 즉, 가장 마지막에 삽입된 데이터가 가장 먼저 배출된다. Stack의 기능은 주로 다음과 같다:

1. Push: 스택의 맨 위에 새로운 데이터 추가.
2. Pop: 스택의 맨 위의 데이터 제거 및 반환.
3. Peek / Top: 스택의 맨 위 데이터가 무엇인지 전달.
4. isEmpty: 스택이 비어있는지 여부를 bool값으로 전달.
5. size: 현재 스택에 있는 데이터의 개수를 반환.

 

2. Stack을 직접 구현해본 경험이 있을까요? 없다면 직접 구현해봅시다.

구현해본 경험이 있다. 아래는 아주아주 간단한 예이다:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Stack 선언 및 초기화
        Stack<int> stack = new Stack<int>();

        // 스택에 요소 추가 (Push)
        stack.Push(10);
        stack.Push(20);
        stack.Push(30);

        Console.WriteLine("스택에 요소 추가 후:");
        PrintStack(stack);

        // 스택에서 요소 제거 (Pop)
        int removedItem = stack.Pop();
        Console.WriteLine($"\nPop된 요소: {removedItem}");

        Console.WriteLine("Pop 후 스택 상태:");
        PrintStack(stack);

        // 스택의 맨 위 요소 읽기 (Peek)
        int topItem = stack.Peek();
        Console.WriteLine($"\nPeek한 요소: {topItem}");

        Console.WriteLine("Peek 후 스택 상태:");
        PrintStack(stack);

        // 스택이 비어있는지 확인 (isEmpty)
        bool isEmpty = stack.Count == 0;
        Console.WriteLine($"\n스택이 비어있는가? {isEmpty}");
    }

    static void PrintStack(Stack<int> stack)
    {
        foreach (int item in stack)
        {
            Console.WriteLine(item);
        }
    }
}

---

 

설명 문제

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

1. 선입후출 (LIFO)
2. 제한된 접근 방식 - 반드시 맨 위의 요소에만 접근할 수 있다.
3. 동적 크기조절
4. 상수 시간연산
5. 재귀적 특성

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

유리할 때.

1. DFS
2. 후위 표기법 계산
3. Undo / Redo 기능

불리할 때.

1. 중간에 있는 요소에 접근할 필요가 있을 떄.
2. 정렬된 데이터가 필요할 때.
3. 양방향 탐색이 필요할 때.
4. FIFO 구조(Queue)가 필요할 때.

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

스파르타 캠프의 C# 주간 팀프로젝트에서 TextRPG를 만들었었다. 이 프로젝트에서 각 Scene을 넘어갈 때 스택 구조를 활용하여 새로운 씬으로의 전환을 해주면서 Stack에 쌓았다가, 다시 뒤로 돌아갈 때 이 Stack에서부터 Pop을 해주면서 메인화면으로 돌아오도록 구성했다.

---

 

실습 문제

namespace _09.선형자료구조_stack_실습
{
    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();
                /* TODO : 현재 Screen을 Stack으로 부터 받아오는 기능 작성 */
                string currentScreen = screenStack.Peek();
                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;
        }
    }

}