Part 2-4-1. 그래프 : 스택과 큐

 

 

그래프

 

[스택과 큐]

둘 다 선형 자료구조이다. 선형 구조 자료란? 자료들이 일렬로 나열된 상태를 말한다.

 

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>(); // 스택에 최적

 

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