C# 자료구조 (큐2)
저번 페이지에서 배열을 이용한 큐 구현은 방법은 세가지인데 두가지를 설명했었다.
이번엔 마지막 방법과 링크드 리스트를 이용한 방법을 설명하겠다.
마지막 방법은 count변수를 추가해서 count가 a.Length가 갔다면 full count가 0이라면 empty를 처리하는 방법이다.
코드를 보여주겠다.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace QueueArray3
{
public class QueueUsingCircularArray3<T>
{
private int front = 0;
private int rear = 0;
private T[] a;
private int count = 0;
public QueueUsingCircularArray3(int queueSize = 16)
{
a = new T[queueSize];
}
public void Enqueue(T data)
{
if (count == a.Length)
{
throw new ApplicationException("Full");
}
else
{
a[rear] = data;
rear = (rear + 1) % a.Length;
count++;
}
}
public T Dequeue()
{
if (count == 0)
{
throw new ApplicationException("Empty");
}
else
{
T data = a[front];
front = (front + 1) & a.Length;
count--;
return data;
}
}
public int Count()
{
return count;
}
}
class Program
{
static void Main(string[] args)
{
QueueUsingCircularArray3<int> queue = new QueueUsingCircularArray3<int>();
queue.Enqueue(5);
queue.Enqueue(2);
queue.Enqueue(3);
queue.Enqueue(3);
Console.WriteLine(queue.Count());
Console.WriteLine(queue.Dequeue());
Console.WriteLine(queue.Dequeue());
Console.WriteLine(queue.Count());
}
}
}
저번에 방법 코드가 달라진건 큐의 요소가 몇개가 있는지 체크해주는 Count메서드가 추가되었고 count변수를 이용해서
요소를 추가할때 count를 ++하고 뺄때는 --식으로 이용해서 Full인지 비어있는지 체크해주는 기능이 생겼다.
이제는 링크드 리스트를 이용한 큐 구현을 해보겠다.
링크드 리스트의 장점은 배열과 같이 크기를 확정 안해도 무한정으로 추가할수 있다는 부분이다.
일단 코드를 보여주고 설명을 하겠다.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace QueueLinkedList
{
public class Node<T>
{
public T data { get; set; }
public Node<T> Next{ get; set;}
public Node(T data)
{
this.data = data;
Next = null;
}
}
public class QueueUsingLinkedList<T>
{
private Node<T> head = null;
private Node<T> tail = null;
private int count;
public void Enqueue(Node<T> data)
{
//Queue가 비어있을때
if (head == null)
{
head = data;
tail = data;
count++;
}
//비어있지 않을때;
else
{
tail.Next = data;
tail = tail.Next;
count++;
}
}
public T Dequeue()
{
if (count == 0)
{
throw new ApplicationException("Empty");
}
else
{
//C#은 GC가 자동으로 처리하기때문에 null처리를 안했음
T data = head.data;
head = head.Next;
count--;
return data;
}
}
public T Peek()
{
T data = head.data;
return data;
}
public int Count()
{
return count;
}
}
class Program
{
static void Main(string[] args)
{
QueueUsingLinkedList<int> queue = new QueueUsingLinkedList<int>();
queue.Enqueue(new Node<int>(5));
queue.Dequeue();
queue.Enqueue(new Node<int>(4));
queue.Enqueue(new Node<int>(3));
queue.Enqueue(new Node<int>(2));
Console.WriteLine(queue.Count());
Console.WriteLine(queue.Dequeue());
Console.WriteLine(queue.Dequeue());
Console.WriteLine(queue.Dequeue());
}
}
}
링크드 리스트는 내가 직접 구현을 해보았다.
일단 데이터를 보관하는 Node 클래스를 만들었다.
data는 말그대로 보관할 data이기 때문에 <T>로 만들었으며 Next 파라미터는 앞에 있는 노드를 가리키는 포인터이다.
이제 큐를 구현한 QueueUsingLinkedList 기능들을 설명하겠다.
일단 큐는 마지막요소를 추가하는것과 앞 요소를 빼내는 형식이다보니 로직을 간단하게 짤수 있다.
마지막 인덱스에 요소를 추가해야하니깐 마지막 요소인 tail객체를 선언하고 첫번째 요소인 head객체를 선언하였고
요소가 몇개 들어있는지 count변수를 만들었다.
Enqueue
마지막요소에 데이터를 추가하는 메서드로 처음엔 큐가 비어있다면 head, tail에 객체를 할당한다.
비어있지 않다면 마지막 요소인 tail.next에 데이터를 저장하고 tail도 tail.next로 포인터를 가리킨다.
Dequeue
첫번째요소인 데이터를 빼내는 메서드로 count가 0이면 예외요소 처리를 하였고 T데이터 담겨져있는 data변수를 선언하고 head.data를 할당시켰고 head는 head.Next로 포인터를 가리킨후 T data를 반환 시켰다.
Peek
이 메서드는 내가 현재 무슨 데이터가 빠지는지 첫번째 요소를 확인하는 메서드이다.
이것도 T데이터 담겨져있는 data변수를 선언하고 head.data를 할당시켜서 그걸 반환시키는 구조이다.
Count
현재 이 요소에 몇개가 있는지 count 변수를 반환하는 메서드이다.
이렇게 해서 배열과 링크드 리스트를 활용한 큐 구현을 마치겠다.