0330 Queue

도착한 순서대로 데이터를 꺼내서 사용하는 선형적인 자료 구조 (선입선출)

배열이나 연결 리스트를 사용해서 구현한다.

rear 인덱스에 데이터를 넣고, 데이터를 읽거나 제거할 땐 front 인덱스를 사용한다.

 

 

●Circular Queue

(고정배열) front 인덱스를 다음 요소로 이동 / 모든 배열 요소를 front 앞으로 당긴다.

원형 동적 배열을 사용해 고정 배열의 문제점을 해결할 수 있다.

1. front/rear 인덱스는 -1로 설정

2. front/rear 데이터는 0으로 설정

3. queue가 가득 찼는지 확인 후 (rear+1)%arr.Length로 데이터 삽입

3-1. rear+1 == front 인덱스인지 확인

4. 데이터 제거 시, 비어있지 않으면 데이터를 읽고 front 하나 증가

마지막 요소를 읽어낼 때 : front = (front+1)%arr.Length

 

front=rear=-1 이면 배열이 비어있다.

 

public class CircluarQueue
    {
        //배열
        private int[] arr;
        //front
        private int front;
        //rear
        private int rear;

        public CircluarQueue(int capacity) 
        {
            //배열 생성
            this.arr = new int[capacity];
            //초기화
            this.front = -1;
            this.rear = -1;
        }
        public void Enqueue(int data) 
        {
            //가득 찬 상태 확인
            if ((this.rear + 1) % this.arr.Length == this.front)
            {
                Console.WriteLine("가득 참");
                throw new InvalidOperationException();//또는 확장
            }
            else 
            {
                if (this.front == -1) 
                {
                    //empty 상태에서 0을 만든다
                    this.front++;
                }
                //다음 인덱스를 구함
                this.rear = (this.rear + 1) % this.arr.Length;
                //넣는다
                this.arr[this.rear] = data;
            };
        }
        public int Dequeue() 
        {
            //배열이 비어있는지 체크
            if (this.front == -1 && this.rear == -1) 
            {
                throw new InvalidOperationException("Queue is Empty");
            }
            else 
            {
                //front 인덱스로 요소를 가져옴
                int data = this.arr[this.front];

                //마지막 요소
                if (this.front == this.rear) 
                {
                    this.front = -1;
                    this.rear = -1;
                }
                else 
                {
                    //front 인덱스 증가
                    this.front = (this.front + 1) % this.arr.Length;
                }
                return data;
            }
        }
        public void Print()
        {
            for (int i = 0; i < this.arr.Length; i++)
            {
                Console.Write(this.arr[i]);
            }
        }
    }

public class App
    {
        public App() 
        {
            CircluarQueue circluarQueue = new CircluarQueue(4);
            circluarQueue.Enqueue(1);
            circluarQueue.Enqueue(2);
            circluarQueue.Enqueue(3);

            Console.WriteLine("result: {0}", circluarQueue.Dequeue());
            Console.WriteLine("result: {0}", circluarQueue.Dequeue());
            Console.WriteLine("result: {0}", circluarQueue.Dequeue());
        }
    }

 

 

●Linked List Queue

 

새 데이터를 추가하기 위해서는 연결 리스트의 마지막에 새 노드 추가,

데이터 꺼내오기 위해서는 연결 리스트의 첫 노드를 읽어오면 된다.

Tail(rear)을 통해서 데이터 추가, head(front)를 통해 데이터 제거

 

public class Node 
    {
        public string data;
        public Node next;
        public Node(string data) 
        {
            this.data = data;
        }
    }
    public class LinkedQueue
    {
        //head
        private Node head;
        //tail
        private Node tail;
        public LinkedQueue() 
        {
        }
        public void Enqueue(string data) 
        {
            //큐가 비어있을 경우
            if (this.head == null)
            {
                this.head = new Node(data);
                this.tail = this.head;
            }
            //큐가 비어있지 않은 경우
            else 
            {
                this.tail.next = new Node(data);
                this.tail = this.tail.next;
            }
        }
        public string Dequeue() 
        {
            string result = this.head.data;

            //큐가 비어있을 경우
            if (this.head == null)
            {
                throw new InvalidOperationException();
            }
            //하나만 남은 경우
            if (this.head == this.tail) 
            {
                //초기화
                this.head = null;
                this.tail = null;
            }
            //큐가 있을 경우
            else
            {
                //head 설정
                this.head = this.head.next;
            }
            return result;
        }
    }

public class App
    {
        public App() 
        {
            LinkedQueue linkedQueue = new LinkedQueue();
            linkedQueue.Enqueue("홍길동");
            linkedQueue.Enqueue("임꺽정");
            linkedQueue.Enqueue("장길산");

            var result = linkedQueue.Dequeue();
            Console.WriteLine(result);
        }
    }

제일 먼저 삽입된 홍길동이 디큐 했을 때 제일 먼저 빠져나간다.