[자료구조] 4강. 큐 - 큐의 개념 및 추상 자료형

큐의 정의 - 큐의 의미

택시를 타기 위해 서 있는 행렬

병원의 접수대

은행의 예금 인출기

백화점의 계산대 위에 놓인 상품들

작업 큐에 들어간 작업이 가장 처음에 처리되는 작업 스케줄(First-In-First-Service)

한쪽에서는 삽입연산만 발생 가능하고, 다른 한쪽에서는 삭제연산만 발생가능한 양쪽이 모두 터진 관

먼저 삽입된 원소가 먼저 삭제되므로 선입 선출(First-In-First-Out : FIFO) 또는 선착순 서브(First-Come-First-Serve : FCFS) 알고리즘을 갖는 순서 리스트

큐의 정의 - 큐의 정의

 

큐의 추상 자료형 - 큐의 삽입(Add_q) 연산

Queue Add_q(queue, item) ::=
    if (IsFull_q(queue))
        then { 
            ‘queueFull’을 출력한다; 
        }
    else { 
        큐의 rear에서 item을 삽입하고, 큐를 반환한다; 
    }

큐의 추상 자료형 - 큐의 삭제(Delete_q) 연산

Element Delete_q(queue) ::=
    if (IsEmpty_q(queue))
        then { 
            ‘queueEmpty’를 출력한다; 
        }
    else { 
        큐의 front에 있는 원소(element)를 삭제하고 반환한다; 
    }

큐의 추상 자료형 - 빈 큐 검사(IsEmpty_q) 연산

Boolean IsEmpty_q(queue) ::=
    if (rear == front)
        then {
            ‘TRUE’값을 반환한다; 
        }
    else { 
        ‘FALSE’ 값을 반환한다; 
    }

큐의 추상 자료형 - 큐의 만원 검사(IsFull_q) 연산

Boolean IsFull_q(queue, maxQueueSize) ::=
    if ( (queue의 elements의 개수) == maxQueueSize)
        then {
            ‘TRUE’ 값을 반환한다; 
        }
    else { 
            ‘FALSE’ 값을 반환한다; 
    }

큐의 추상 자료형 - Delete / Add 연산의 실행

① Create_q(4);

② Add_q(queue, ‘A’);

③ Add_q(queue, ‘B’);

④ Add_q(queue, ‘C’);

⑤ Delete_q(queue);

⑥ Delete_q(queue);

⑦ Delete_q(queue);

⑧ Add_q(queue, ‘D’);

큐의 추상 자료형 - Add / Delete 연산의 실행