C# 자료구조 (큐)
큐 (Queue)
먼저 도착한 데이터들을 FIFO(Fist In Fist Out) 선입선출하는 선형구조
그림에서 보았듯이 Rear부분에 데이터를 넣고 데이터를 빼낼때는 Front부분을 먼저 빼낸다.
큐를 이용해서 사용하는 추상적 자료형인 우선순위 큐 와 데크가 있는데
우선 순위큐
큐는 일반적으로 FIFO인 선입선출인데 우선순위 큐는 가장 필요한 요소인 데이터를 먼저 빼내는 구조이다.
데크
큐는 일반적으로 Rear쪽에 데이터를 넣고 데이터를 뺄때는 Front쪽을 빼는데 데크는 그런거 상관없이 앞 뒤에다 데이터를 넣고 반대로 뺄수 있는 구조이다.
지금은 큐가 중요하기에
둘의 구조 구현은 나중을 미루겠습니다.
큐는 배열과 링크드리스트로 대부분 구현을 하는데 일단 배열로 구현을 해보겠다.
배열은 전에 배웠듯이 확정된 고정 크기가 존재하기에 두가지 방법을 사용할수 있는데
첫번째는 고정된 크기에 배열을 생성하고 큐에서 빼내올때마다 front를 앞으로 이동시켜 데이터를 출력하는 방식이지만 데이터의 크기는 이미 고정되어있고 front를 앞으로 이동시켜서 출력시키지만 배열안에는 데이터가 그대로 있기때문에 한정적이란것과
두번째는 front를 빼낼때마다 모든 데이터 요소들을 아래로 옮겨서 계속 증가시키는 형식으로도 할수있지만 이러면 메모리 낭비가 엄청 심해진다.
이렇게 단점인 많은 배열을 효과적으로 활용할수 있는게 바로 원형 배열 또는 원형 동적 배열을 이용하는것이다.
만약에 front가 마지막 요소로 갔다고 생각을 하면 front의 인덱스는 마지막 요소만 가리키고 있을것이다.
앞에 있는 배열의 데이터가 비어있다고 하더라도 말이다.
이걸 원형배열로 이용해 front가 마지막 요소에 다다를때 front를 0으로 되돌리면 해결되는 방법인것이다.
이런식으로 순환하는 원형 배열을 만들수있는데 마지막 인덱스에 도착할때 0번째로 순환하기 위해 나머지 연산자를 이용한다.
EX) rear = (rear + 1) % a.Length 이런식으로 말이다.
그러면 마지막 인덱스에 도달할때 0번째 인덱스로 순환할수 있는 구조이다.
일단 원형배열을 이용한 코드는 세가지가 있는데 일단 첫번째 방법 코드를 보여주겠다.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace QueueArray
{
public class QueueUsingCircularArray<T>
{
//모든 타입 메모리 활용을 위해 제네릭 T 사용
private T[] a;
private int front;
private int rear;
//디폴트 큐 크기는 16이지만 지정 가능
public QueueUsingCircularArray(int queueSize = 16)
{
a = new T[queueSize];
front = -1;
rear = -1;
}
public void Enqueue(T data)
{
//큐가 가득 찼는지 체크
if ((rear + 1) % a.Length == front)
{
//에러 처리 (또는 배열 확장)
T[] a1 = new T[a.Length * 2];
for(int i =0; i < a.Length; i++)
{
a1[i] = a[i];
}
a = a1;
}
else
{
//비어 있는 경우
if (front == -1)
{
front++;
}
// 데이타 추가
rear = (rear + 1) % a.Length;
a[rear] = data;
}
}
public object Dequeue()
{
// 큐가 비어있는지 체크
if (front == -1 && rear == -1)
{
throw new AccessViolationException("Empty");
}
else
{
// 데이타 읽기
T data = a[front];
// 마지막 요소를 읽은 경우
if (front == rear)
{
//특수값 -1로 설정
front = -1;
rear = -1;
}
else
{
//Front 이동
front = (front + 1) % a.Length;
}
return data;
}
}
}
class Program
{
static void Main(string[] args)
{
QueueUsingCircularArray<int> queue = new QueueUsingCircularArray<int>();
queue.Enqueue(5);
queue.Enqueue(2);
queue.Enqueue(3);
queue.Enqueue(3);
Console.WriteLine(queue.Dequeue());
Console.WriteLine(queue.Dequeue());
}
}
}
이 코드는 위에있는 그림을 이용한 방식인데
일단 큐에 요소가 없으니깐 Fornt , Rear 변수를 -1로 선언하고 크기가 지정된 배열을 생성한다.
이제 두개 기능인 Enqueue Dequeue 메서드를 설명하겠다.
Enqueue
큐에 마지막부분에 요소를 추가하는 메서드로 처음엔 큐가 가득찼는지 rear의 나머지 연산자가 front랑 같은지 체크하고
같다면 예외처리나 배열확장을 할수있는데 나는 크기를 2배로 확장하는 코드를 짜놨다.
같지 않다면 a배열에 rear인덱스에 요소를 추가하고 rear = (rear + 1 ) % rear 더해서 다음 인덱스에 추가할 rear를 구하고
front도 요소가 하나 추가됬으니 Dequeue할때 빼야하기 때문에 front도 ++연산을 한다.
Dequeue
처음엔 큐가 비어있는지 체크를하고 비어있으면 예외처리를 하고 비어있지 않다면 a 배열에 front인덱스에 있는 요소를 T data 변수에 할당하고 마지막 요소였다면 front와 rear 변수에 -1을 할당 비어있지않다면 front변수를 ++해서 다음 인덱스를 가리키게 한다.
두번째 방법은 빠르게 설명하겠다.
일단 코드를 보여주겠다.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace QueueArray2
{
public class QueueUsingCircularArray2<T>
{
private T[] a;
private int front = 0;
private int rear = 0;
public QueueUsingCircularArray2(int queueSize = 16)
{
a = new T[queueSize];
}
public void Enqueue(T data)
{
if ((rear + 1) % a.Length == front)//Full
{
throw new ApplicationException("Full");
}
else
{
a[rear] = data;
rear = (rear + 1) % a.Length;
}
}
public T Dequeue()
{
if (rear == front)
{
throw new ApplicationException("Emqty");
}
else
{
T data = a[front];
front = (front + 1) % a.Length;
return data;
}
}
}
class Program
{
static void Main(string[] args)
{
QueueUsingCircularArray2<int> queue = new QueueUsingCircularArray2<int>();
queue.Enqueue(5);
queue.Enqueue(2);
queue.Enqueue(3);
queue.Enqueue(3);
Console.WriteLine(queue.Dequeue());
Console.WriteLine(queue.Dequeue());
}
}
}
이 방법은 Rear부분을 선입력으로 마지막 요소를 추가한것보다 앞을 가리키는 방식이다.
이 방법은 앞 인덱스 공간이 비어있다는 단점이 있지만 굳이 특별한 숫자인 -1을 넣지않고 큐가 꽉찼거나 비어있는 상태를 쉽게 정의할수있다.
그것말고는 첫번째와 두번째 방식은 차이점이 별로 없다.
세번째 방법과 그리고 링크드리스트를 이용한 방법은 다음페이지에 설명하겠다.