내일배움캠프 61일차 TIL - 선형 자료구조 - Queue
확인 문제
1. Queue가 무엇인지 알고 있나요? 어떤 방식으로 작동하는지 설명할 수 있을까요?
내 답:
Queue(큐)는 컴퓨터 과학에서 사용되는 기본적인 자료 구조 중 하나로, FIFO(First-In, First-Out, 선입선출) 원칙을 따르는 컬렉션입니다. 이는 첫 번째로 추가된 요소가 첫 번째로 제거되는 방식을 의미합니다. 즉, 요소들이 추가된 순서대로 처리됩니다.
작동 방식
1. Enqueue: 큐에 요소를 추가하는 작업입니다. 새 요소는 큐의 끝에 추가되며, 이는 큐에 들어온 마지막 요소가 됩니다.
2. Dequeue: 큐에서 요소를 제거하는 작업입니다. 큐의 맨 앞에 있는 요소가 제거되며, 이는 큐에 가장 오래 전에 추가된 요소입니다. 제거된 요소는 큐에서 소비되었다고 볼 수 있습니다.
3. Peek: 큐의 맨 앞에 있는 요소를 제거하지 않고 조회하는 작업입니다. 이를 통해 큐의 첫 번째 요소가 무엇인지 확인할 수 있지만, 큐의 상태는 변경되지 않습니다.
모범 답:
[선택] 2. Queue를 직접 구현해본 경험이 있을까요? 없다면 직접 구현해봅시다. 💡 **Queue 클래스**를 직접 구현해보세요.클래스 및 주요 멤버 변수
data- 타입:
T[](제네릭 타입 배열) - 역할: 큐의 요소를 저장하는 배열입니다. 큐의 최대 크기는 이 배열의 크기로 제한됩니다. 배열의 초기 크기는 1000으로 설정되어 있습니다.
- 타입:
head- 타입:
int - 역할: 큐의 첫 번째 요소의 인덱스를 가리킵니다. 큐가 비어있을 때는
0입니다. - 초기값:
0 - 동작:
- 요소가 제거될 때마다 (
Dequeue연산)head의 값이 1씩 증가합니다.
- 요소가 제거될 때마다 (
- 타입:
tail- 타입:
int - 역할: 큐의 마지막 요소의 인덱스를 가리킵니다. 큐가 비어있을 때는
1입니다. - 초기값:
1 - 동작:
- 새로운 요소가 추가될 때마다 (
Enqueue연산)tail의 값이 1씩 증가합니다.
- 새로운 요소가 추가될 때마다 (
- 타입:
함수 명세
IsEmpty- 기능: 큐가 비어있는지 확인하는 함수입니다.
- 입력: 없음.
- 출력:
bool값. 큐가 비어있으면true, 아니면false. - 동작:
head가tail보다 큰지 또는 같은지 확인합니다.- 만약
head가tail보다 크거나 같으면, 큐가 비어있다고 판단하여true를 반환합니다. - 그렇지 않으면
false를 반환합니다.
Enqueue- 기능: 큐의 맨 뒤에 새로운 요소를 추가하는 함수입니다.
- 입력: 추가할 요소
item(제네릭 타입T). - 출력: 없음.
- 동작:
- 먼저, 큐가 가득 찼는지 확인합니다. (
tail이data배열의 길이보다 크거나 같으면 예외를 발생시킵니다) tail변수를 1 증가시킵니다.data배열의tail위치에item을 저장합니다.
- 먼저, 큐가 가득 찼는지 확인합니다. (
Dequeue- 기능: 큐의 맨 앞에 있는 요소를 제거하고 그 값을 반환하는 함수입니다.
- 입력: 없음.
- 출력: 제거된 요소
item(제네릭 타입T). - 동작:
- 먼저, 큐가 비어있는지 확인합니다. (
IsEmpty함수를 호출하여 비어있으면 예외를 발생시킵니다) data배열의head위치에 있는 값을 임시로 저장합니다.head변수를 1 증가시킵니다.- 임시로 저장한 값을 반환합니다.
- 먼저, 큐가 비어있는지 확인합니다. (
Count
- 기능: 큐에 있는 요소의 개수를 반환하는 함수입니다.
- 입력: 없음.
- 출력: 큐에 있는 요소의 개수 (int값).
- 동작:
-tail의 값에서head의 값을 뺀 후 1을 더한 값을 반환합니다.
- 요소 개수는(tail - head + 1)입니다.
public class My_Queue<T>
{
private T[] data = new T[1000];
private int head;
private int tail;
public bool IsEmpty()
{
// ****** CODE HERE ******
// ***********************
}
public void Enqueue(T item)
{
// ****** CODE HERE ******
// ***********************
}
public T Dequeue()
{
// ****** CODE HERE ******
// ***********************
}
public int Count()
{
// ****** CODE HERE ******
// ***********************
}
}
// 구현 확인을 위한 코드입니다.
class Program
{
static void Main(string[] args)
{
Queue<int> q = new Queue<int>();
My_Queue<int> q_new = new My_Queue<int>();
for (int i = 0; i < 10; ++i)
{
q.Enqueue(i);
q_new.Enqueue(i);
}
while (q.Count > 0)
{
Console.WriteLine($"q => {q.Dequeue()} | q_new => {q_new.Dequeue()}");
Console.WriteLine($"size of q : {q.Count} | size of q_new : {q_new.Count}");
Console.WriteLine("------------------------------------------------------");
}
}
}
직접 구현 답안
public class My_Queue<T>
{
private T[] data = new T[1000];
private int head;
private int tail;
public bool IsEmpty()
{
// ****** CODE HERE ******
return head == tail;
// ***********************
}
public void Enqueue(T item)
{
// ****** CODE HERE ******
if ((tail + 1) % data.Length == head)
{
throw new InvalidOperationException("Queue overflow");
}
// 큐의 tail 위치에 항목을 추가하고 tail을 증가시킴
data[tail] = item;
tail = (tail + 1) % data.Length;
// ***********************
}
public T Dequeue()
{
// ****** CODE HERE ******
if (IsEmpty())
{
throw new InvalidOperationException("Queue is empty");
}
// 큐의 head 위치의 항목을 반환하고 head를 증가시킴
T item = data[head];
head = (head + 1) % data.Length;
return item;
// ***********************
}
public int Count()
{
// ****** CODE HERE ******
return (tail - head + data.Length) % data.Length;
// ***********************
}
}
// 구현 확인을 위한 코드입니다.
class Program
{
static void Main(string[] args)
{
Queue<int> q = new Queue<int>();
My_Queue<int> q_new = new My_Queue<int>();
for (int i = 0; i < 10; ++i)
{
q.Enqueue(i);
q_new.Enqueue(i);
}
while (q.Count > 0)
{
Console.WriteLine($"q => {q.Dequeue()} | q_new => {q_new.Dequeue()}");
Console.WriteLine($"size of q : {q.Count} | size of q_new : {q_new.Count()}");
Console.WriteLine("------------------------------------------------------");
}
}
}설명 문제
Queue의 특성을 설명해주세요.
내 답:
• FIFO(First-In, First-Out): 큐는 선입선출 구조를 가지고 있어, 먼저 추가된 요소가 먼저 제거됩니다.
• 정렬된 접근: 요소들은 추가된 순서대로 접근되며, 이는 순차적 처리에 유리합니다.
• 양방향 접근 불가: 큐는 맨 앞 또는 맨 뒤에서만 요소를 추가하거나 제거할 수 있으며, 중간 요소에 직접 접근하는 것은 일반적으로 허용되지 않습니다.
모범 답:
추가, 제거가 O(1)만큼 걸립니다. 선입 선출의 방식이기에 임의 접근이 불가능합니다.
Queue는 언제 사용하면 좋은 자료구조인가요? 반대로 언제 사용하기 불리할까요?
내 답:
언제 사용하면 좋은가?
• 순차적 처리가 필요할 때: 데이터가 들어온 순서대로 처리해야 하는 경우, 예를 들어, 프린터의 인쇄 대기열, 고객 서비스 센터의 대기열 등에서 큐를 사용하면 좋습니다.
• 자원 공유 관리: 여러 프로세스 또는 스레드가 한정된 자원을 사용해야 할 때, 큐를 사용하여 요청을 관리하고 순차적으로 자원에 접근하게 할 수 있습니다.
• 데이터 스트림 처리: 실시간 데이터 스트림을 순차적으로 처리해야 할 때, 예를 들어, 네트워크 패킷 처리나 이벤트 처리 시스템에서 큐를 활용할 수 있습니다.
언제 사용하기 불리한가?
• 임의 접근이 필요할 때: 큐는 맨 앞이나 맨 뒤의 요소에만 접근할 수 있기 때문에, 중간 요소에 대한 빠른 접근이 필요한 경우에는 사용하기 불리합니다.
• 데이터 수정이 빈번할 때: 큐는 추가와 제거에 최적화되어 있으며, 요소의 수정이나 중간 요소의 삭제와 같은 작업은 비효율적일 수 있습니다.
모범 답:
선입 선출의 방식이기에 일을 들어오는 순서대로 처리를 해야하고 앞에 내용을 처리할 때 뒤에 내용을 추가하거나 대기 시켜야할 때 좋습니다. 예를 들어 네트워크 라우터에서 큐잉을 통해 들어온 데이터 패킷을 패킷 스위칭 하기 전에 사용하거나, BFS로 탐색한 내용을 하나씩 살펴보며 나아가는 길찾기 알고리즘 등에서 사용합니다.
반대로 선입후출의 방식에서는 사용이 어렵고 임의 접근을 해야하는 데이터에서는 사용하기 안좋습니다.
Queue를 본인의 프로젝트에 적용해본 경험을 말해주세요.
내 답:
모범 답:
A* 알고리즘을 통해 길찾기를 하는 과정에서 BFS로 주변 지역을 탐색하고 탐색한 지역중에 이동 가능한 지역을 큐에 저장해두었다가, 이를 하나씩 꺼내서 그 주변을 탐색하는 방식을 사용할 때 큐를 사용했습니다.
실습 문제
💡 **[Stack으로 Queue 만들기]**Stack 두 개를 이용하여 Queue를 만들어봅시다.
Stack의 특성만을 이용하여 선입선출(FIFO; First-In First-Out)의 특성을 만족하는 Queue를 만들어야 합니다.
public class Queue_new<T>
{
Stack<T> stack1 = new Stack<T>();
Stack<T> stack2 = new Stack<T>();
public bool IsEmpty()
{
// ****** CODE HERE ******
// ***********************
}
public void Enqueue(T item)
{
// ****** CODE HERE ******
// ***********************
}
public T Dequeue()
{
// ****** CODE HERE ******
// ***********************
}
public int Count()
{
// ****** CODE HERE ******
// ***********************
}
}
// 구현 확인을 위한 코드입니다.
class Program
{
static void Main(string[] args)
{
Queue<int> q = new Queue<int>();
Queue_new<int> q_new = new Queue_new<int>();
for (int i = 0; i < 10; ++i)
{
q.Enqueue(i);
q_new.Enqueue(i);
}
while (q.Count > 0)
{
Console.WriteLine($"q => {q.Dequeue()} | q_new => {q_new.Dequeue()}");
Console.WriteLine($"size of q : {q.Count} | size of q_new : {q_new.Count}");
Console.WriteLine("------------------------------------------------------");
}
}
}
public class Queue_new<T>
{
Stack<T> stack1 = new Stack<T>();
Stack<T> stack2 = new Stack<T>();
public bool IsEmpty()
{
// ****** CODE HERE ******
return stack1.Count == 0 && stack2.Count == 0;
// ***********************
}
public void Enqueue(T item)
{
// ****** CODE HERE ******
stack1.Push(item);
// ***********************
}
public T Dequeue()
{
// ****** CODE HERE ******
if (IsEmpty())
{
throw new InvalidOperationException("Queue is empty");
}
if (stack2.Count == 0)
{
while (stack1.Count > 0)
{
stack2.Push(stack1.Pop());
}
}
return stack2.Pop();
// ***********************
}
public int Count()
{
// ****** CODE HERE ******
return stack1.Count + stack2.Count;
// ***********************
}
}
// 구현 확인을 위한 코드입니다.
class Program
{
static void Main(string[] args)
{
Queue<int> q = new Queue<int>();
Queue_new<int> q_new = new Queue_new<int>();
for (int i = 0; i < 10; ++i)
{
q.Enqueue(i);
q_new.Enqueue(i);
}
while (q.Count > 0)
{
Console.WriteLine($"q => {q.Dequeue()} | q_new => {q_new.Dequeue()}");
Console.WriteLine($"size of q : {q.Count} | size of q_new : {q_new.Count()}");
Console.WriteLine("------------------------------------------------------");
}
}
}