[Data Structures & Algorithms] 큐(Queue)의 응용과 데크(Deque)

🎩 큐(Queue)의 응용_1) 운영체제의 작업 큐

💜 프린터 버퍼 큐 (Printer Buffer Queue)

: CPU에서 프린터로 보낸 데이터 순서대로 프린터에서 출력하기 위해 선입선출 구조의 큐 사용

 

---

 

💜 스케줄링 큐 (Scheduling Queue)

: CPU 사용을 요청한 프로세서들의 순서를 스케줄링하기 위해 큐 사용

 

---

🎩 큐(Queue)의 응용_2) 시뮬레이션에서의 큐잉 시스템

: 시뮬레이션을 위한 수학적 모델링에서 대기 행렬 및 대기 시간 등을 모델링하기 위해 큐잉 이론(Queue Theory)을 사용하기도 한다.

 

---

🎩 데크(Deque)란?

기존의 큐 2개 중 하나를 좌우로 뒤집에 결합시킨 구조로, 큐의 양쪽 끝에서 삽입과 삭제 연산을 모두 수행할 수 있도록 확장한 자료 구조를 데크(Deque)라고 한다.

 

---

 

💜 데크의 추상 자료형

ADT deque

    // 공백 상태인 데크 생성
    createDeque() ::= create an empty DQ;
    
    //데크가 공백 상태인지 검사
    isEmpty(DQ) ::= if (DQ is empty) then return true
                    else return false;
   
    //데크의 front 앞에 원소 삽입
    insertFront(DQ, item) ::= insert item at the front of DQ;
    
    //데크의 rear 뒤에 원소 삽입
    insertRear(DQ, item) ::= insert item at the rear of DQ;
    
    //데크의 front에 있는 원소 삭제
    deleteFront(DQ) ::= if (isEmpty(DQ)) then return NULL
                        else
                        {
                            delete and return the front item of DQ
                        };
    
    //데크의 rear에 있는 원소 삭제
    deleteRear(DQ) ::= if (isEmpty(DQ)) then return NULL
                       else
                       {
                            delete and return the rear item of DQ
                        };
    
    //데크의 front에 있는 원소 반환
     getFront(DQ) ::= if (isEmpty(DQ)) then return NULL
                        else
                        {
                            return the front item of DQ
                        };
    
    //데크의 rear에 있는 item 반환
    getRear(DQ) ::= if (isEmpty(DQ)) then return NULL
                       else
                       {
                            return the rear item of DQ
                        };
                        
End deque