Chapter 4-1. 스택과 큐

인프런에 있는 Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘 강의를 듣고 정리한 필기입니다. 😀
🌜 강의 들으러 가기 Click

Chapter 4. 그래프

🚖 스택과 큐

using System;
using System.Collections.Generic;

namespace Excercise
{
    class Program
    {
        static void Main(string[] args)
        {
            Stack<int> stack = new Stack<int>();

            stack.Push(101);
            stack.Push(102);
            stack.Push(103);
            stack.Push(104);
            stack.Push(105);

            int data1 = stack.Pop(); // 105 리턴 및 삭제 
            int data2 = stack.Peek(); // 104 리턴만

            Queue<int> queue = new Queue<int>();
            queue.Enqueue(101);
            queue.Enqueue(102);
            queue.Enqueue(103);
            queue.Enqueue(104);
            queue.Enqueue(105);

            int data3 = queue.Dequeue(); // 101 리턴 및 삭제
            int data4 = queue.Peek(); // 102 리턴
        }
    }
}

• 둘 다 선형 자료구조
  • 자료들이 일렬로 나열된 상태

스택

스택 👉 Last In Last Out (나중에 들어온 애가 먼저 나간다.)

• Push로 삽입
• Pop() 가장 최근에 들어온 애를 1️⃣ 리턴한 후 2️⃣ 삭제한다.
• Peek() 가장 최근에 들어온 애를 리턴한다.
• 📢 비어 있는 상태에서 Pop(), Peek() 하는건 위험
• 스택이 쓰이는 예
  • 중첩 팝업 (마지막으로 띄운 UI가 먼저 꺼짐)

큐

큐 👉 First In First Out (먼저 들어온 애가 먼저 나간다.)

• Enqueue로 삽입
• Dequeue() 들어온지 가장 오래된 애를 1️⃣ 리턴한 후 2️⃣ 삭제한다.
• Peek() 들어온지 가장 오래된 애를 리턴한다.
• 📢 비어 있는 상태에서 Dequeue(), Peek() 하는건 위험
• 큐가 쓰이는 예
  • 네트워크 패킷 (순차적으로 먼저 요청한 애부터 처리)

🚖 스택과 큐 관점에서 생각해보기

연결 리스트

            LinkedList<int> list = new LinkedList<int>();
            list.AddLast(101);
            list.AddLast(102);
            list.AddLast(103);

            int value1 = list.First.Value;
            list.RemoveFirst();

            int value2 = list.Last.Value;
            list.RemoveLast();

뒤에 추가할 수도 있고 앞, 뒤 값을 접근할 수 있다는 점에서 스택과 큐 기능을 둘 다 가지고 있다.

동적 배열

List<int> vector = new List<int>(); // 스택에 최적

• 동적 배열은 맨 앞 원소가 추가 혹은 삭제되면 그 뒤의 원소들도 다같이 한칸씩 옮겨야 하는 부담이 있으므로 스택에 최적화 되어 있다.
  • 그러나 실제 내부적으론 맨앞 원소의 추가 삭제가 이루어질 때마다 일일이 원소들을 한칸씩 이사시키진 않고 맨앞 원소 인덱스를 두번째 원소로 지정하던가 하는 꼼수를 쓴다. 성능을 위해.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Algorithm Lesson 2 카테고리 내 다른 글 보러가기