[3.30] Queue

● 정의

  - 선입선출 방식의 자료구조(FIFO), 현실에서의 줄 서는 것과 비슷한 구조이다.

 

배열로 구현 (원형배열)

1. Queue의 초기 상태에서 Front와 Rear 인덱스는 -1로 설정
2. 데이터 추가 시, A[0]에 값을 넣고 Front와 Rear는 0이 된다.
3. 데이터를 추가할 때(Enqueue), Queue가 가득 찬 상태인지 체크하고, 가득차지 않았으면 (Rear+1)%Length 위치로 이동하여 데이터를 넣는다.
4. 가득 찬 경우는 (Rear+1) % Length == Front와 같이 표현할 수 있다.
5. 데이터를 제거 할 때(Dequeue), Queue가 비어 있는지 체크하고 비어있지 않으면 데이터를 읽고 Front를 하나 증가시킨다. Front = (Front+1)%Length로 표현이 가능하다. Queue의 모든 요소를 제거할 때 ( Front==Rear ), -1로 초기화한다.
6. mod 연산자는 +,- 보다 우선순위가 높다. 즉 먼저 실행되므로 괄호를 하지 않으면 잘못된 값이 들어감.

매우 귀찮다. 심지어 원형배열이라 헷갈린다. 그래서 Queue를 구현할 때는 Linked List로 구현하는 것이 훨씬 편하다.

 

연산	메서드	시간복잡도
삽입	void Enqueue(Element e)	O(1)
삭제	Element Dequeue()	O(1)
검색	Element Find(Elem e)	O(n)// n : 자료의 크기

• 삽입 및 삭제 연산은 특정한 인덱스나 특정 메모리에서만 이루어지기 때문에 상수시간이 소요된다.
• 하지만 검색은 컨테이너 안을 처음부터 싹 돌아봐야되기 때문에 선형시간이 소요된다.
• 그러므로 큐는 특정 위치에서의 삽입 삭제 연산이 빈번하게 일어나고, 검색을 자주 하지않는 곳에 사용하는 것이 좋다.

원형배열로 만든 Queue 예시

using System;

namespace Study01
{
    public class QueueCircularArray
    {
        //배열 및 변수 선언
        int[] arr;
        int front;
        int rear;

        public QueueCircularArray(int capacity = 10)
        {
            //배열 인스턴스화 및 변수 초기화
            this.arr = new int[capacity];
            this.front = this.rear = -1;
        }

        public void Enqueue(int data)
        {
            //배열이 가득 찼을 때
            if ((this.rear + 1) % this.arr.Length == this.front)
            {
                Console.WriteLine("Queue Fulled");
                //Exception or 확장
                throw new ApplicationException("Queue is full.");
            }
            else
            {
                if (this.front == -1)
                {
                    this.front++;
                }

                //데이터 삽입 후 rear 인덱스 증가
                this.arr[++this.rear % this.arr.Length] = data;
                Console.WriteLine("rear: {0}", this.rear);
            }   
        }

        public int Dequeue()
        {
            //Empty상태, 비어있다.
            if(front == -1 && rear == -1)
            {
                throw new ApplicationException("Queue is empty.");
            }
            else
            {
                //front인덱스로 요소를 가져오고 front 인덱스를 증가시킴
                int data = this.arr[this.front++ % this.arr.Length];

                //마지막 요소를 읽었는 경우 변수들 초기화
                if (this.front == this.rear)
                {
                    this.front = -1;
                    this.rear = -1;
                }
                return data;
            }  
        }
    }
}

 

 

연결리스트로 구현한 Queue 예시

using System;

namespace Study01
{
    public class Node
    {
        public string data;
        public Node next;

        public Node(string data)
        {
            this.data = data;
            this.next = null;
        }
    }

    public class QueueLinkedList
    {
        private Node head;              //리스트의 첫 원소
        private Node tail;              //리스트의 마지막 원소

        public QueueLinkedList()
        {
            this.head = null;
            this.tail = null;
        }

        public void Enqueue(string data)
        {
            //리스트가 비어있는 경우
            if (head == null)
            {
                head = new Node(data);
                tail = head;
            }
            else
            {
                tail.next = new Node(data);
                tail = tail.next;
            }
        }

        public string Dequeue()
        {
            string data = string.Empty;

            //리스트에 하나의 원소라도 남아있는 경우
            if(head != null)
            {
                data = head.data;
                head = head.next;
            }
            else
            {
                throw new ApplicationException("Queue is empty");
            }

            return data;
        }

        public override string ToString()
        {
            string result = string.Empty;
            for(Node discover = head; discover != null; discover = discover.next)
            {
                result += string.Format("{0} ", discover.data);
            }
            return result;
        }
    }
}