내일배움캠프 60일차 TIL - 선형 자료구조 - Stack
0
확인 문제
Stack가 무엇인지 알고 있나요? 어떤 방식으로 작동하는지 설명할 수 있을까요?
내 답:
스택은 선형 자료구조의 일종입니다. LIFO 방식으로 리스트에 들어온 자료를 관리합니다. 자료를 스택 맨 위에 넣는 Push, 맨 위 요소를 반환하는 Pop, 맨 위에 있는 요소를 확인하는 Peek, 스택이 비어있는지 확인하는 IsEmpty등으로 작동시킬 수 있습니다.
모범 답:
[선택] 2. Stack을 직접 구현해본 경험이 있을까요? 없다면 직접 구현해봅시다. 💡 **Stack 클래스**를 직접 구현해보세요.클래스 및 주요 멤버 변수
data- 타입:
T[](제네릭 타입 배열) - 역할: 스택의 요소를 저장하는 배열입니다. 스택의 최대 크기는 이 배열의 크기로 제한됩니다. 배열의 초기 크기는 1000으로 설정되어 있습니다.
- 타입:
top- 타입:
int - 역할: 스택의 가장 위에 있는 요소의 인덱스를 가리킵니다. 스택이 비어있을 때는
1입니다. - 초기값:
1 - 동작:
- 새로운 요소가 추가될 때마다 (
Push연산)top의 값이 1씩 증가합니다. - 요소가 제거될 때마다 (
Pop연산)top의 값이 1씩 감소합니다.
- 새로운 요소가 추가될 때마다 (
- 타입:
함수 명세
IsEmpty- 기능: 스택이 비어있는지 확인하는 함수입니다.
- 입력: 없음.
- 출력:
bool값. 스택이 비어있으면true, 아니면false. - 동작:
top변수가1인지 확인합니다.- 만약
top이1이면, 스택이 비어있다고 판단하여true를 반환합니다. - 그렇지 않으면
false를 반환합니다.
Push- 기능: 스택의 맨 위에 새로운 요소를 추가하는 함수입니다.
- 입력: 추가할 요소
item(제네릭 타입T). - 출력: 없음.
- 동작:
- 먼저, 스택이 가득 찼는지 확인합니다. (
top이data배열의 길이보다 크거나 같으면 예외를 발생시킵니다) top변수를 1 증가시킵니다.data배열의top위치에item을 저장합니다.
- 먼저, 스택이 가득 찼는지 확인합니다. (
Pop- 기능: 스택의 맨 위에 있는 요소를 제거하고 그 값을 반환하는 함수입니다.
- 입력: 없음.
- 출력: 제거된 요소
item(제네릭 타입T). - 동작:
- 먼저, 스택이 비어있는지 확인합니다. (
IsEmpty함수를 호출하여 비어있으면 예외를 발생시킵니다) data배열의top위치에 있는 값을 임시로 저장합니다.top변수를 1 감소시킵니다.- 임시로 저장한 값을 반환합니다.
- 먼저, 스택이 비어있는지 확인합니다. (
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 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 ******
if (top == data.Length - 1)
{
throw new InvalidOperationException("Stack overflow");
}
data[++top] = item;
// ***********************
}
public T Pop()
{
// ****** CODE HERE ******
if (IsEmpty())
{
throw new InvalidOperationException("Stack is empty");
}
return data[top--];
// ***********************
}
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("------------------------------------------------------");
}
}
}설명 문제
1. Stack의 특성을 설명해주세요.
내 답:
• 후입선출(LIFO, Last In First Out): Stack의 가장 기본적인 특성으로, 마지막에 추가된 요소가 가장 먼저 제거됩니다.
• 접근 제한: Stack에서는 오직 맨 위의 요소에만 접근할 수 있으며, 맨 위의 요소를 제외한 나머지 요소들은 직접 접근할 수 없습니다. 이는 데이터의 삽입(push), 삭제(pop), 조회(peek) 작업을 통해서만 가능합니다.
• 단순성: Stack은 구현이 간단하며, 사용하기 쉬운 인터페이스를 제공합니다.
모범 답:
스택(Stack)은 후입선출(LIFO) 방식의 자료구조로, 요소는 한쪽 끝에서만 삽입되고 삭제된다. 연산이 단순하며 빠르다. 함수 호출 관리, 괄호 검사, 깊이 우선 탐색 등 다양한 용도로 사용된다. 메모리를 효율적으로 사용하며, 요소에 무작위 접근은 불가능하다.
2. Stack은 언제 사용하면 좋은 자료구조인가요? 반대로 언제 사용하기 불리할까요?
내 답:
유리한 경우:
• 역순 처리가 필요한 경우: 데이터를 역순으로 처리해야 할 때 Stack을 사용하면 효율적입니다. 예를 들어, 브라우저의 뒤로 가기 기능이나 문서의 Undo 기능 등이 있습니다.
• 재귀 알고리즘: 재귀적인 함수 호출에 대한 정보를 저장하는 데 Stack이 사용됩니다. 함수 호출 시 마다 호출 정보를 Stack에 저장하고, 반환 시 Stack에서 정보를 꺼내어 이전 상태로 돌아갑니다.
• 문자열 또는 수식의 괄호 검사: 괄호의 짝이 맞는지 검사할 때 Stack을 사용하여 여는 괄호를 만날 때마다 push하고, 닫는 괄호를 만날 때마다 pop하여 짝을 맞출 수 있습니다.
불리한 경우:
• 임의 접근이 필요한 경우: Stack은 맨 위의 요소에만 접근할 수 있으므로, 임의 위치의 데이터에 빠르게 접근해야 하는 경우에는 적합하지 않습니다.
• 중간 데이터의 삽입 및 삭제: Stack은 맨 위의 요소만을 추가하거나 제거할 수 있으므로, 리스트 중간에 데이터를 삽입하거나 삭제하는 작업에는 비효율적입니다.
모범 답:
유리한 경우 :
함수의 호출을 관리할 때(C#의 호출스택), 괄호 검사 및 수식을 계산할 때, 탐색 알고리즘에서 경로를 추적할 때, 데이터를 역순화 할 때 등을 사용할 경우 유리하다
불리한 경우 :
무작위 접근이 필요할 때, 순서가 중요할 때, 대용량 데이터를 처리해야 할 때, 선입선출형 자료구조가 필요할 때, 양방향 접근이 필요할 때 등을 사용할 경우 불리하다.
3. Stack을 본인의 프로젝트에 적용해본 경험을 말해주세요.
내 답:
모범 답:
텍스트 RPG를 만들때 씬 전환에 이용했다. 정확히는 스텍형 코드를 사용한 것이 아니라 함수 호출이 스택으로 관리된다는 것을 이해하고, 씬을 전환할 때 코드로 전환하는게 아니라 스택의 호출 흐름을 이해하여 해당 함수 종료시 자연스럽게 어떤 씬으로 전환되도록 코드를 구성 하였다.
실습 문제
💡 **[LinkedList와 Stack을 이용한 최상단 UI 표시 기능]**게임을 만들다 보면 여러 UI가 겹쳐서 표시되는 상황이 많습니다.
가장 상단의 UI만 표시하고, 나머지는 따로 저장해놓을 수는 없을까요?
C# 콘솔에서 해당 상황을 가정하고 가장 상단의 화면만 표시해주는 기능을 제작해봅시다.
주요 멤버 변수
screenStack: 현재 화면의 순서를 관리하는Stack<string>.screens: 각 화면의 설명과 연결된 화면 옵션을 저장하는Dictionary<string, ScreenOption>.ScreenOption구조체 : 화면의 설명을 저장하는 Description(string)과 다음 화면으로 이동할 수 있는 옵션을 저장하는 Option(LinkedList<string>)로 구성.
함수 명세
DisplayScreen- 기능: 현재 화면을 출력하고 사용자 입력을 처리합니다.
- 입력: 없음.
- 출력: 없음.
GetScreenByOptionNumber
- 기능: 사용자가 입력한 옵션 번호에 해당하는 화면을 반환합니다.
- 입력: 옵션 목록options(LinkedList), 옵션 번호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;
}
}
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("잘못된 입력입니다. 다시 시도해주세요.");
}
}
}
스터디 로그