#스택(Stack) #큐(Queue)

---

스택 (Stack) : 배열 구조를 사용하나 index 기능은 막아놈

---

• 선입후출(FILO), 후입선출(LIFO) 방식의 자료구조
• 가장 최신 입력된 순서대로 처리해야 하는 상황에 이용

 <스택 구현>
 스택은 리스트를 사용법만 달리하여 구현 가능

 - 삽입 -
         top                      top
          ↓                        ↓
 ┌─┬─┬─┬─┬─┬─┬─┬─┐      ┌─┬─┬─┬─┬─┬─┬─┬─┐
 │1│2│3│4│5│ │ │ │  => │1│2│3│4│5│6│ │ │
 └─┴─┴─┴─┴─┴─┴─┴─┘      └─┴─┴─┴─┴─┴─┴─┴─┘

 - 삭제 -
           top                  top
            ↓                    ↓
 ┌─┬─┬─┬─┬─┬─┬─┬─┐      ┌─┬─┬─┬─┬─┬─┬─┬─┐
 │1│2│3│4│5│6│ │ │  => │1│2│3│4│5│ │ │ │
 └─┴─┴─┴─┴─┴─┴─┴─┘      └─┴─┴─┴─┴─┴─┴─┴─┘


static void Main(string[] args)
{
    Stack<int> stack = new Stack<int>(20);

    // srack 추가 : 0(1), 최악 (용량이 가득 찼었을 때) : 0(n)
    stack.Push(1);      
    stack.Push(2);
    stack.Push(3);
    stack.Push(4);
    stack.Push(5);

    // RJsorl : 0(1)
    Console.WriteLine(stack.Pop());     // 후입선출  5
    Console.WriteLine(stack.Pop());     // 4
    Console.WriteLine(stack.Pop());     // 3

    // 다음차례에 꺼내질 요소 확인, 넘어가진 않음. : 0(1)
    Console.WriteLine(stack.Peek());    // 2 
    Console.WriteLine(stack.Peek());    // 2
    Console.WriteLine(stack.Peek());    // 2


    stack.Push(6);
    stack.Push(7);
    stack.Push(8);
    stack.Push(9);

    if (stack.Count > 0)                    // 있으면 꺼냄.
    {
        Console.WriteLine(stack.Pop());     // 9
    }

    stack.TryPop(out int pop);
}

---

큐(Queue)

---

• 선입선출(FIFO), 후입후출(LILO) 방식의 자료구조
• 입력된 순서대로 처리해야 하는 상황에 이용

 <큐 구현>
 1. 배열 사용
 선입선출(FIFO), 후입후출(LILO) 을 구현하기 위해 배열을 생성하고 순차적으로 데이터를 배치
     ┌─┬─┬─┬─┬─┬─┬─┬─┐
  앞 │1│2│3│4│5│ │ │ │  뒤
     └─┴─┴─┴─┴─┴─┴─┴─┘

 - 삽입 -
 비어있는 가장 뒷쪽에 데이터를 배치
  ┌─┬─┬─┬─┬─┬─┬─┬─┐        ┌─┬─┬─┬─┬─┬─┬─┬─┐
  │1│2│3│4│5│ │ │ │   =>  │1│2│3│4│5│6│ │ │
  └─┴─┴─┴─┴─┴─┴─┴─┘        └─┴─┴─┴─┴─┴─┴─┴─┘

 - 삭제 -
 가장 앞쪽 데이터를 출력하고 빈자리를 채우기 위해 나머지 데이터를 앞당기기 진행
  ┌─┬─┬─┬─┬─┬─┬─┬─┐        ┌─┬─┬─┬─┬─┬─┬─┬─┐
  │1│2│3│4│5│6│ │ │   =>  │2│3│4│5│6│ │ │ │
  └─┴─┴─┴─┴─┴─┴─┴─┘        └─┴─┴─┴─┴─┴─┴─┴─┘

 - 문제발생 -
 큐의 삭제 과정시 나머지 데이터를 앞당겨야하는 N번의 작업 발생
  ┌─┬─┬─┬─┬─┬─┬─┬─┐        ┌─┬─┬─┬─┬─┬─┬─┬─┐        ┌─┬─┬─┬─┬─┬─┬─┬─┐
  │1│2│3│4│5│6│ │ │   =>  │ │2│3│4│5│6│ │ │   =>   │2│3│4│5│6│ │ │ │
  └─┴─┴─┴─┴─┴─┴─┴─┘        └─┴─┴─┴─┴─┴─┴─┴─┘        └─┴─┴─┴─┴─┴─┴─┴─┘


 2. 전단 & 후단
 삽입 & 삭제 시 데이터를 앞당기지 않고 head와 tail을 표시하여 삽입할 위치와 삭제할 위치를 지정

 - 삽입 -
 tail 위치에 데이터를 추가하고 tail을 한칸 뒤로 이동
     h       t                h         t
     ↓       ↓                ↓         ↓      
  ┌─┬─┬─┬─┬─┬─┬─┬─┐        ┌─┬─┬─┬─┬─┬─┬─┬─┐
  │ │2│3│4│5│ │ │ │   =>  │ │2│3│4│5│6│ │ │
  └─┴─┴─┴─┴─┴─┴─┴─┘        └─┴─┴─┴─┴─┴─┴─┴─┘

 - 삭제 -
 head 위치에 데이터를 추가하고 head을 한칸 뒤로 이동
     h         t                h       t
     ↓         ↓                ↓       ↓
  ┌─┬─┬─┬─┬─┬─┬─┬─┐        ┌─┬─┬─┬─┬─┬─┬─┬─┐
  │ │2│3│4│5│6│ │ │   =>  │ │ │3│4│5│6│ │ │
  └─┴─┴─┴─┴─┴─┴─┴─┘        └─┴─┴─┴─┴─┴─┴─┴─┘

 - 문제발생 -
 큐의 배열 마지막 위치까지 사용하는 경우 빈자리가 없어 저장 불가한 상황 발생
       h         t              h           t
       ↓         ↓              ↓           ↓
  ┌─┬─┬─┬─┬─┬─┬─┬─┐        ┌─┬─┬─┬─┬─┬─┬─┬─┐
  │ │ │3│4│5│6│7│ │   =>  │ │ │3│4│5│6│7│8│
  └─┴─┴─┴─┴─┴─┴─┴─┘        └─┴─┴─┴─┴─┴─┴─┴─┘


static void Main(string[] args)
{
    Queue<int> queue = new Queue<int>();

    // 추가 : 0(1), 최악의 경우 : 0(n)
    queue.Enqueue(1);
    queue.Enqueue(2);
    queue.Enqueue(3);
    queue.Enqueue(4);
    queue.Enqueue(5);

    // 꺼내기 : 0(1)
    Console.WriteLine(queue.Dequeue());     // 1
    Console.WriteLine(queue.Dequeue());     // 2
    Console.WriteLine(queue.Dequeue());     // 3

    // 꺼내지 않고 확인만!!
    Console.WriteLine(queue.Peek());     // 4

    queue.Enqueue(6);
    queue.Enqueue(7);
    queue.Enqueue(8);
    queue.Enqueue(9);

    while (queue.Count > 0)
    {
        Console.WriteLine(queue.Dequeue());     // 4, 5, 6, 7, 8, 9
    }
}