Queue<T> 의 구현

선입선출 (Fast-in-first-out, FIFO) 형태의 자료를 다룰 때는 큐를 사용한다. 선착순으로 제일 먼저 들어온 자료가 제일 먼저 나가는 자료구조이다. 큐에 저장되는 값이 여러가지 일 수 있으므로 제네릭으로 정의하고, MyQueue<T> 클래스에는 큐의 맨 앞과 맨 뒤를 가지는 first와 last필드를 갖는다. 각각의 자료는 Node<T> 에 저장되고 MyQueue<T> 클래스에서는 값을 추가하는 EnQueue와 DeQueue가 있다. 

 

필드 또는 메소드	내용
first	큐의 첫번째 요소 가장 먼저들어온 데이터
last	큐의 가장 마지막 요소  가장 마지막에 들어온 데이터
EnQueue()	큐에 값을 추가한다.
DeQueue()	큐에 값을 삭제한다.
Print()	큐의 내용을 입력된 순서로 출력한다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace QueuePractice
{
    class Node<T>
    {
        internal T value;
        internal Node<T> next; //다음 노드 가리키는 부분
        public Node(T value) 
        {
            this.value = value;
            this.next = null;
        }
    }
    class MyQueue<T>
    {
        internal Node<T> first = null; //가장 첫 노드 (순서상)
        internal Node<T> last = null; //가장 마지막 노드 (순서상)

        internal void EnQueue(Node<T> node)
        {
            if (last == null) //가장 첫 노드라면
                first = last = node; //first last 모두 새로운 노드를 가리킨다.
            else
            {
                last.next = node; //기존 노드가 있다면 last 는 새로 들어온 데이터를 가리킨다.
                last = node;
            }
        }
        internal T DeQueue()
        {
            if(first ==null)
            {
                Console.WriteLine("Queue Empty");
                return default(T);
            }
            else
            {
                T value = first.value;
                first = first.next; //first가 가리키고 있는 부분을 내보내고
                return value;       //그 다음으로 들어온 데이터를 first가 가리킨다.
            }
        }
        internal void Print()
        {
            for (Node<T> t = first; t != null; t = t.next)
                Console.WriteLine(t.value + " -> ");
            Console.WriteLine();
        }

    }
    class Program
    {
        static void Main(string[] args)
        {
        }
    }
}

 

아무 노드도 없는 상태

 

첫 노드가 Enqueue된 상태

두번째 노드가 Enqueue된 상태

first는 그대로 첫번째로 들어온 노드를 가리키고 last는 새로 들어온 노드를 가리킨다. 그림을 잘못 그렸는데 빨간 박스는 Node2이다.

 

 

 

DeQueue

 

가장 먼저 들어왔던 Node1이 밖으로 출력되고, 제일 먼저 들어온 Node를 가리키고 있던 first는 next를 따라가서 그 다음 노드를 가리킨다. 따라서 다음 dequeue에는 first가 가리키고 있는 Node2가 나간다.