[C#] 선형자료구조 실습하기 2 - Stack

[확인문제]

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

스택은 LIFO(Last In, First Out 후입선출) 방식으로 동작하는 자료구조로 다음과 같은 방식으로 작동한다.

Push : 스택에 데이터를 삽입

Pop : 스택의 맨 위에 있는 데이터를 제거하고 반환

Peek : 스택의 맨 위에 있는 데이터를 확인한다.(제거하지 않고 확인만)

IsEmpty : 스택이 비어있는지 확인한다

 

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

 

클래스 및 주요 멤버 변수

• data
  • 타입: T[] (제네릭 타입 배열)
  • 역할: 스택의 요소를 저장하는 배열입니다. 스택의 최대 크기는 이 배열의 크기로 제한됩니다. 배열의 초기 크기는 1000으로 설정되어 있습니다.
• top
  • 타입: int
  • 역할: 스택의 가장 위에 있는 요소의 인덱스를 가리킵니다. 스택이 비어있을 때는 1입니다.
  • 초기값: 1
  • 동작:
    • 새로운 요소가 추가될 때마다 (Push 연산) top의 값이 1씩 증가합니다.
    • 요소가 제거될 때마다 (Pop 연산) top의 값이 1씩 감소합니다.

함수 명세

1. IsEmpty
   • 기능: 스택이 비어있는지 확인하는 함수입니다.
   • 입력: 없음.
   • 출력: bool 값. 스택이 비어있으면 true, 아니면 false.
   • 동작:
     • top 변수가 1인지 확인합니다.
     • 만약 top이 1이면, 스택이 비어있다고 판단하여 true를 반환합니다.
     • 그렇지 않으면 false를 반환합니다.
2. Push
   • 기능: 스택의 맨 위에 새로운 요소를 추가하는 함수입니다.
   • 입력: 추가할 요소 item (제네릭 타입 T).
   • 출력: 없음.
   • 동작:
     • 먼저, 스택이 가득 찼는지 확인합니다. (top이 data 배열의 길이보다 크거나 같으면 예외를 발생시킵니다)
     • top 변수를 1 증가시킵니다.
     • data 배열의 top 위치에 item을 저장합니다.
3. Pop
   • 기능: 스택의 맨 위에 있는 요소를 제거하고 그 값을 반환하는 함수입니다.
   • 입력: 없음.
   • 출력: 제거된 요소 item (제네릭 타입 T).
   • 동작:
     • 먼저, 스택이 비어있는지 확인합니다. (IsEmpty 함수를 호출하여 비어있으면 예외를 발생시킵니다)
     • data 배열의 top 위치에 있는 값을 임시로 저장합니다.
     • top 변수를 1 감소시킵니다.
     • 임시로 저장한 값을 반환합니다.
4. Count
   • 기능: 스택에 있는 요소의 개수를 반환하는 함수입니다.
   • 입력: 없음.
   • 출력: 스택에 있는 요소의 개수 (int 값).
   • 동작:
     • top의 값에 1을 더한 값을 반환합니다.
     • 스택의 요소 개수는 top의 값에 1을 더한 값입니다.
     •  

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

    public bool IsEmpty()
    {
        // ****** CODE HERE ******
        
        // ***********************
    }

    public void Push(T item)
    {
        // ****** CODE HERE ******

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

    public T Pop()
    {
        // ****** CODE HERE ******
        
        // ***********************
    }

    public int Count()
    {
        // ****** CODE HERE ******
        
        // ***********************
    }
}

// 구현 확인을 위한 코드입니다.
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("------------------------------------------------------");
        }
    }
}

    public bool IsEmpty()
    {
       return top == -1;
    }

    public void Push(T item)
    {
         if (top == data.Length - 1)
        {
            throw new Exception("Stack is full.");
        }

        top++;
        data[top] = item;
    }

    public T Pop()
    {
        if (IsEmpty())
        {
            throw new Exception("Stack is empty.");
        }

        T item = data[top];
        top--;
        return item;
    }

    public int Count()
    {
        return top + 1;
    }
}

 

 

[설명문제]

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

LIFO : 마지막에 들어온 데이터가 가장 먼저 나온다.

선형 : 데이터가 한 방향으로만 이동한다. (삽입과 제거가 맨 위에서 일어난다.)

간단한 구현 : 배열이나 연결 리스트를 사용하여 간단하게 구현할 수 있다.

 

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

Stack은 데이터의 순서가 중요하지 않고, 마지막에 들어온 데이터가 가장 먼저 필요한 경우에 좋다.

1. 웹 브라우저의 백 버튼 기능은 방문한 페이지 순서를 스택에 저장하고, 사용자가 백 버튼을 클릭했을 때 스택을 이용하여 이전 페이지를 표시한다.

2. 재귀 알고리즘을 구현 시 스택을 사용하여 호출된 함수들의 정보를 저장하고, 관리하는데 효과적이다.

반면,

1. 데이터의 순서가 중요한 경우 원하는 데이터를 꺼내기 위해 여러 번의 Pop연산이 필요할 수 있어 비효율적이다.

2. 스택은 데이터 삽입/삭제 시 O(n)의 시간 복잡도를 가지고 있어, 자주 발생할 경우 비효율적이다. 이런 경우 Queue와 같은 자료구조를 사용하는 것이 더 적합하다.

 

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

게임 UI 관리 : 게임 화면은 여러 레이어로 구성되어 있으며, 상황에 따라 보여지는 UI가 다르다. 스택을 사용하여 현재 표시되고있는 화면들을 관리하고, 사용자 입력에 따라 화면을 전환하는 기능을 구현했다.

계산식 처리 : 수식 계산기 프로그램에서 스택을 사용하여 후위 표기식을 효율적으로 계산할 수 있다.

 * 후위 표기식 : 11+, 22+, 33+ 과 같이 연산자가 후위에 표시되는 방식

 

 

[실습문제]

 

💡  LinkedList와 Stack을 이용한 최상단 UI 표시 기능

게임을 만들다 보면 여러 UI가 겹쳐서 표시되는 상황이 많습니다.

가장 상단의 UI만 표시하고, 나머지는 따로 저장해놓을 수는 없을까요?

C# 콘솔에서 해당 상황을 가정하고 가장 상단의 화면만 표시해주는 기능을 제작해봅시다.

주요 멤버 변수

1. screenStack: 현재 화면의 순서를 관리하는 Stack<string>.
2. screens: 각 화면의 설명과 연결된 화면 옵션을 저장하는 Dictionary<string, ScreenOption>.
3. ScreenOption 구조체 : 화면의 설명을 저장하는 **Description(string)**과 다음 화면으로 이동할 수 있는 옵션을 저장하는 **Option(LinkedList<string>)**로 구성.

함수 명세

1. DisplayScreen
   • 기능: 현재 화면을 출력하고 사용자 입력을 처리합니다.
   • 입력: 없음.
   • 출력: 없음.
2. GetScreenByOptionNumber
   • 기능: 사용자가 입력한 옵션 번호에 해당하는 화면을 반환합니다.
   • 입력: 옵션 목록 options (LinkedList<string>), 옵션 번호 optionNumber (int).
   • 출력: 화면 이름 (string).

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 = /* 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을 제거 **************************
                
                // ****************************************************************
                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을 집어넣기 *****************
                        
                        // *********************************************************
                        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;
    }
}

string currentScreen = screenStack.Peek();

  if (input == "0")
            {
                if (screenStack.Count == 1)
                    Environment.Exit(0);
                else
                    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)
                    {
                        screenStack.Push(selectedScreen);
                        break;
                    }
                }
                Console.WriteLine("잘못된 입력입니다. 다시 시도해주세요.");
            }