1. 📖 Stack 스택

데이터가 선입후출(First in Last out)의 구조로 쌓이는 개념입니다.

즉, 데이터를 추가할 땐 마치 탑을 쌓듯 차곡차곡 데이터가 쌓이게 되고,
데이터를 꺼내고자 할 때는 맨 마지막에 추가됐던 데이터를 받습니다.

가장 최신 입력된 데이터 순서대로 처리해야 하는 상황에 사용합니다.

1-1 🔖 스택의 기능

stack.Push();	// 데이터 추가
Stack.Pop();   	// 데이터 꺼내기
Stack.peek();  	// 꺼내지는 않고 어떤 데이터가 있는지 확인하는 용도

for (int i = 1; i < 5; i++)
{
    stack.Push(i);                          // 입력순서 : 1, 2, 3, 4, 5
}

Console.WriteLine(stack.Peek());            // 최상단 : 5


for (int i = 1; i < 4; i++)
{
    Console.WriteLine(stack.Pop());         // 출력순서 : 5, 4, 3
}

 for (int i = 6; i < 11; i++)
 {
     stack.Push(i);                          // 입력순서 : 6, 7, 8, 9, 10
 }

 while (stack.Count > 0)
 {
     Console.WriteLine(stack.Pop());         // 출력순서 : 10, 9, 8, 7, 6, 2, 1
 }

마지막 결과를 보면 5, 4, 3이 빠져있는데 중간에 pop을 통해 데이터가 꺼내져있는 상태라 출력을 안한 것입니다.

2. 📖 Queue 큐

큐는 스택과 달리 선입선출(First in First out)의 구조로 이루어져 있습니다.

그래서 입력된 데이터 순서대로 처리해야 하는 상황에서 사용합니다.

2-1 🔖 큐의 기능

스택과 비슷한데 조금은 다릅니다.

queue.Enqueue(); 데이터 추가
queue.Dequeue(); 데이터 꺼내기
queue.Peek(); 꺼내지는 않고 어떤 데이터가 있는지 확인하는 용도

 Queue<int> queue = new Queue<int>();

 for (int i = 0; i < 5; i++)
 {
     queue.Enqueue(i);                       // 입력순서 : 0, 1, 2, 3, 4
 }

 Console.WriteLine(queue.Peek());            // 다음순서 : 0
 

 for (int i = 0; i < 3; i++)
 {
     Console.WriteLine(queue.Dequeue());     // 출력순서 : 0, 1, 2
 }

 Console.WriteLine(queue.Peek());            // 다음순서 : 3
 

 for (int i = 5; i < 10; i++)
 {
     queue.Enqueue(i);                       // 입력순서 : 5, 6, 7, 8, 9
 }

 Console.WriteLine(queue.Peek());            // 다음순서 : 3
 

 while (queue.Count > 0)
 {
     Console.WriteLine(queue.Dequeue());     // 출력순서 : 3, 4, 5, 6, 7, 8, 9
 }

2-2 🔖 큐 구현 원리

2-2-1 ✔️ 데이터 추가 삽입

사실 간단히 데이터 삽입을 하는 경우 비어있는 가장 뒷쪽에 데이터를 배치를 하면 끝나기 때문에 큰 문제가 되지 않습니다.

2-2-2 ✔️ 데이터 삭제

2-2-2-1 ⭕ head와 tail

문제는 삭제 입니다.
가장 앞쪽 데이터를 출력하고 빈자리를 채우기 위해 나머지 데이터를 앞당기기 진행하는 데
결국 나머지 데이터를 앞당겨야하는 작업 발생하여 효율이 떨어집니다.

head와 tail을 설정하여 데이터를 앞당기지 않고 삽입할 위치와 삭제할 위치를 지정합니다.

삽입 : tail 위치에 데이터를 추가하고 tail을 한칸 뒤로 이동

   head        tail
    ↓           ↓
[ ][2][3][4][5][ ][ ][ ]


   head           tail
    ↓              ↓
[ ][2][3][4][5][6][ ][ ]

삭제 : head 위치에 데이터를 추가하고 head을 한칸 뒤로 이동

   head           tail
    ↓              ↓
[ ][2][3][4][5][6][ ][ ]


      head        tail
       ↓           ↓
[ ][ ][3][4][5][6][ ][ ]

2-2-2-2 ⭕ 순환배열

큐의 배열 마지막 위치까지 사용하는 경우 빈자리가 없어 저장을 할 수 없는 상황이 생길 수 있습니다.

배열의 끝까지 도달하여 빈자리가 없을 경우 처음으로 돌아가서 빈공간을 활용하는 원리를 이용하여 해결합니다.
            head     tail
             ↓        ↓
[ ][ ][ ][ ][5][6][7][ ]


tail       head        
 ↓           ↓           
[ ][ ][ ][ ][5][6][7][8]

2-2-2-3 ⭕ tail과 head가 같은 공간으로 될 경우

모든 공간이 비어있는 상황과 가득차 있는 상황을 구분할 수 없는 상황이 될 수 있습니다.

여기서 head와 tail이 일치하는 경우를 비어있는 경우로 판정합니다.
          head tail
             ↓↓
[ ][ ][ ][ ][ ][ ][ ][ ]

tail이 head 전 위치에 있는 경우에는 한자리가 비어있어도 가득찬 경우로 판정합니다.
        tail head        
          ↓  ↓           
[ ][ ][ ][ ][5][6][7][8]